things I learned last week

  • 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 t, there is a sample space of size polyn of permutations \{ 1,\ldots,n \} \rightarrow \{ 1,\ldots, n \} such that a uniformly sampled permutation from the sample space is t-wise independent. This was open even for t=4.
  • That proving the following “quadratic uncertainty principle” is an open question, and probably a very difficult one: suppose that q_1,\ldots,q_m are n-variate polynomials of total degree at most 2 and c_1,\ldots,c_m are real coefficients such that for every (x_1,\ldots,x_n) \in \{ 0,1\}^n we have

    x_1 \cdot x_2 \cdots x_n = \sum_i c_i \cdot (-1)^{q_i(x_1,\ldots,x_n)}

    prove that m must be exponentially large in n. (If the q_i are all linear, then the standard uncertainty principle gives us m \geq 2^n.)

  • 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 thoughts on “things I learned last week

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s