Simons Symposium: Monday

Today was the first day of the 2012 Simons Symposium on Analysis of Boolean Functions. We had five speakers today.

First, I spoke about a few of the open problems mentioned in the below post. David Ellis also contributed the following open problem at the end of the session: Given any $A \subseteq \{0,1\}^n$ of fixed cardinality $a$, Harper’s Edge Isoperimetric inequality tells us the maximum the edge boundary $|\partial A|$ is minimized when $A$ is the first $a$ strings in lexicographical order. Now suppose $\partial A|$ is at most the minimal value plus $\ell$. Is it true that $A$’s symmetric difference from the nearest minimizer has cardinality at most $\ell$? Failing that, at most $O(\ell)$? Several other people had open problems they wanted to discuss, but we were running low on time; I think/hope we will have another open problems session later in the week.

Next up was Madhu Sudan who gave a survey on testing of linear and affine-invariant properties of functions ${\mathbb F}_q^n \to {\mathbb F}_q$, described some connections to coding theory, and mentioned several interesting open problems. Full details will be in the scribe notes (which will hopefully be posted soon), but one interesting open problem I remember was: Suppose $P$ is a linear and affine-invariant property of functions ${\mathbb F}_{2^n} \to {\mathbb F}_2$ which contains (but does not equal) the set of degree-1 polynomials, and is contained in (but does not equal) the set of degree-2 polynomials. If $P$ is testable with constantly many queries, is it true that $P$ is “sparse”; i.e., $|P| \leq \mathrm{poly}(q^n)$? (I hope I got that question right.)

Following Madhu was Avi Wigderson, who talked about a problem with applications in many different areas: matrix scaling. Here one is given a nonnegative matrix $A$ and the task is to find multipliers for each of the rows and columns so that the resulting matrix $B$ is doubly-stochastic (or at least, arbitrarily close to doubly-stochastic). The relevant theorem, first proved by Sinkhorn in 1964, is that this is possible if and only if $A$’s permanent is strictly positive. Avi proved this result via the simplest imaginable algorithm: scale the rows of $A$ so that it’s stochastic, then scale the columns so that it’s stochastic, then do the rows again, and the columns again, etc. This algorithm works in the limit, but is not efficient; on the other hand, Avi, Nati Linial, and Alex Samorodnitsky gave an efficient algorithm for finding the multipliers.

The next speaker was Rocco Servedio. He talked about recent joint work with Anindya De, Ilias Diakonikolas, and Vitaly Feldman on the “Chow parameters problem”. It is an old, easy theorem of Chow that if $f$ is a linear threshold function (LTF) then no other boolean function $g$ can satisfy $\widehat{f}(S) = \widehat{g}(S)$ for all $|S| \leq 1$. Thus given the degree-0 and degree-1 Fourier coefficients of an LTF, in principle one can recover the LTF. However the proof of Chow’s theorem is nonconstructive. Rocco described how to give a nearly optimal, efficient (approximate) solution to this LTF reconstruction problem by combining a variety of tools from Fourier analysis, linear algebra, probability, and learning theory.

Our last speaker was Alex Samorodnitsky. Alex reviewed some known combinatorial and analytic edge-isoperimetric statements about the boolean cube; he then moved on to talk about the quest to obtain sharp constant in the KKL and Talagrand influence theorems. He suggested that to get sharp constants we need to investigate statements which are fundamentally about combinatorics of the boolean cube rather than analysis of Gaussian space. He presented a couple of concrete conjectures which would lead to sharp constants for the Talagrand influence theorem.

Rocco Servedio lecturing on Chow Parameters

Daniel Kane, like the rest of us, amused by the wildlife at Caneel Bay

Shachar Lovett betting El Mossel (not pictured) that scalable quantum computers will exist in 20 years

5 comments to Simons Symposium: Monday

Leave a Reply




You can use most standard LaTeX, as well as these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>