This is a followup to the previous post on program obfuscation written jointly with Guy Rothblum.The problem of program obfuscation is fascinating.  The question at hand is whether one can transform a program (say, described as a Boolean circuit) into a form that is executable (i.e., has the same input/output behavior), but is otherwise completely … Continue reading Progress and Challenges in Code Obfuscation: Part II

(joint post by Yael Kalai and Guy Rothblum) It feels especially appropriate to write about recent developments in cryptography and code obfuscation while basking in the afterglow of a wonderful workshop at the Weizmann Institute of Science, celebrating the work of Shafi Goldwasser and Sivio Micali---this year’s Turing Award recipients. Shafi and Silvio repeatedly demonstrated … Continue reading Progress and Challenges in Code Obfuscation (part I/II)

The various MSR labs are looking for postdocs and full-time researchers in many scientific fields, including all areas of theoretical Computer Science. You can apply via this website. Please don’t forget to specify in the form all the labs you may be interested in. For Microsoft Research Silicon Valley applications submitted by December first will … Continue reading Microsoft Research SVC Application Deadline – December 1st

The 15th ACM conference on Economics and Computation (EC'14, formally known as “ACM conference on Electronic Commerce”) will be held June 8-12, 2014 at Stanford University, Palo Alto, California, United States. The CFP is now public and can be found here. EC'14 will be co-located with a meeting of the NBER Market Design working group, … Continue reading ACM EC 2014 Call For Papers

While this blog is mostly about theory, today I would like to talk about a real auction and how it relates to theory. I’ll focus on a fundraising auction for my child’s elementary school. As is common around here, the school has an annual community event called a “Walk-a-Thon” in which donations are collected towards … Continue reading Walk-a-Thon auction design

In this post I’d like to report a new and simple proof we found for theorem by Berenbrink, Czumaj, Steger, Vöcking on the imbalance of the balls-into-bins process known as the multiple choice scheme. Full details could be found in the paper. Probably many are familiar with this process, Kunal blogged about some variations of it a few months … Continue reading Balls-and-Bins made simpler

In this guest post, Sanjeev Arora will share some thoughts about the future of scientific publishing in our community. This is not unrelated to our last post, and is also aimed at initiating discussion towards FOCS 2013 that is starting in the coming weekend. As always, comments are most welcomed with the reminder that WindowsOnTheory … Continue reading Sanjeev Arora: Thoughts on Paper Publishing in the Digital Age

The business meeting of STOC/FOCS is usually rather tedious, but it is also an opportunity to raise and debate issues that the community should be concerned about. One such issue is the inconsistency between our publication norms and the norms of other communities. This is becoming more and more important as TCS megalomaniacally adopt the … Continue reading Umesh Vazirani: should publishing in STOC/FOCS and Science/Nature be mutually exclusive?