- How the graph construction of Barak, Gopalan, Hastad, Meka, Raghavendra and Steurer (which shows the near-optimality of the “Cheeger-type” bound in Arora-Barak-Steurer) works.
- That Kuperberg, Lovett and Peled finally showed that, for every constant , there is a sample space of size poly of permutations such that a uniformly sampled permutation from the sample space is -wise independent. This was open even for .
- That proving the following “quadratic uncertainty principle” is an open question, and probably a very difficult one: suppose that are n-variate polynomials of total degree at most 2 and are real coefficients such that for every we have
prove that must be exponentially large in . (If the are all linear, then the standard uncertainty principle gives us .)

- That women can be real men, and that they should so aspire.
- That the rich really are different from you and me

More here.

## 2 comments

Comments feed for this article

February 13, 2012 at 12:46 pm

KlimHere you probably mean $x_i \in \{-1, 1\}$ and not in $\{0,1\}$

February 13, 2012 at 1:32 pm

lucaNo, the are in , otherwise you can get their product with one degree-one polynomial