- 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

2 comments
Comments feed for this article
February 13, 2012 at 12:46 pm
Klim
Here you probably mean $x_i \in \{-1, 1\}$ and not in $\{0,1\}$
February 13, 2012 at 1:32 pm
luca
No, the
are in
, otherwise you can get their product with one degree-one polynomial