In the previous posts we talked about various discrepancy questions and saw a proof of the six standard deviations suffice result. Besides being of interest in combinatorics, discrepancy theory has several remarkable applications in algorithms. Check this excellent book for a taste of these results. Here I will briefly discuss two (one old and one … Continue reading Discrepancy and Rounding Linear Programs

In the last post we discussed some questions about discrepancy and the 'Six Standard Deviations Suffice' theorem stated below (without the $latex {6}&fg=000000$, which is not too important, but makes for a great title): Theorem 1 For vectors $latex {a^1,\ldots,a^n \in \{1,-1\}^n}&fg=000000$, there exists $latex {\epsilon \in \{1,-1\}^n}&fg=000000$ such that for every $latex {j \in … Continue reading Discrepancy Bounds from Convex Geometry

This blog post is an introduction to the ``Sum of Squares'' (SOS) algorithm from my biased perspective. This post is rather long - I apologize. You might prefer to view/print it in pdf format. If you'd rather "see the movie", I'll be giving a TCS+ seminar about this topic on Wednesday, February 26th 1pm EST. … Continue reading Fun and Games with Sums of Squares

[Update 5/20/14: Feel free to borrow or adapt any part of this text for future conferences. In retrospect, perhaps I should have given some more concrete guidance: in a typical TCS paper, by page 5 or 6 you should be done with the introduction, which means that you have already clearly stated your main result, explained why … Continue reading Advice for FOCS authors

Today, we have a guest post from Frank McSherry talking about a clever approach to using Differential Privacy for handling pesky dependencies that get in the way of proving measure concentration results. --------------------- In this post I'll explain a cute use of differential privacy as a tool in probabilistic analysis. This is a great example … Continue reading Differential Privacy for Measure Concentration

This week's post touches on subjects spanning almost 2000 years — we start with a cryptographic problem and go back in time to discover a theorem that could be known to the Greeks. Its content is based on a paper co-authored with Anton Mityagin and Kobbi Nissim that appeared in ANTS VII in 2006. The … Continue reading From Discrete Logarithm Problem to Menelaus Theorem

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