FOCS 2011
TechTalks from event: FOCS 2011
We will be uploading the videos for FOCS 2011 during the week of Nov 28th 2011. If you find any discrepancy, please let us know by clicking on report error link on talk page. If you did not permit the video to be published and by mistake we have published your talk, please notify us immediately at support AT weyond.com
9B

Lexicographic Products and the Power of NonLinear Network CodingWe introduce a technique for establishing and amplifying gaps between parameters of network coding and index coding. The technique uses linear programs to establish separations between combinatorial and codingtheoretic parameters and applies hypergraph lexicographic products to amplify these separations. This entails combining the dual solutions of the lexicographic multiplicands and proving that they are a valid dual of the product. Our result is general enough to apply to a large family of linear programs. This blend of linear programs and lexicographic products gives a recipe for constructing hard instances in which the gap between combinatorial or codingtheoretic parameters is polynomially large. We find polynomial gaps in cases in which the largest previously known gaps were only small constant factors or entirely unknown. Most notably, we show a polynomial separation between linear and nonlinear network coding rates. This involves exploiting a connection between matroids and index coding to establish a previously unknown separation between linear and nonlinear index coding rates. We also construct index coding problems with a polynomial gap between the broadcast rate and the trivial lower bound for which no gap was previously known.

Quadratic GoldreichLevin TheoremsDecomposition theorems in classical Fourier analysis enable us to express a bounded function in terms of few linear phases with large Fourier coefficients plus a part that is pseudorandom with respect to linear phases. The GoldreichLevin algorithm can be viewed as an algorithmic analogue of such a decomposition as it gives a way to efficiently find the linear phases associated with large Fourier coefficients. In the study of "quadratic Fourier analysis", higherdegree analogues of such decompositions have been developed in which the pseudorandomness property is stronger but the structured part correspondingly weaker. For example, it has previously been shown that it is possible to express a bounded function as a sum of a few quadratic phases plus a part that is small in the $U^3$ norm, defined by Gowers for the purpose of counting arithmetic progressions of length 4. We give a polynomial time algorithm for computing such a decomposition. A key part of the algorithm is a local selfcorrection procedure for ReedMuller codes of order 2 (over $\F_2^n$) for a function at distance $1/2\epsilon$ from a codeword. Given a function $f:\F_2^n \to \{1,1\}$ at fractional Hamming distance $1/2\epsilon$ from a quadratic phase (which is a codeword of ReedMuller code of order 2), we give an algorithm that runs in time polynomial in $n$ and finds a codeword at distance at most $1/2\eta$ for $\eta = \eta(\epsilon)$. This is an algorithmic analogue of Samorodnitsky's result, which gave a tester for the above problem. To our knowledge, it represents the first instance of a correction procedure for any class of codes, beyond the listdecoding radius. In the process, we give algorithmic versions of results from additive combinatorics used in Samorodnitsky's proof and a refined version of the inverse theorem for the Gowers $U^3$ norm over $\F_2^n$.

Optimal testing of multivariate polynomials over small prime fieldsWe consider the problem of testing if a given function f:F_q^n > F_q is close to a nvariate degree d polynomial over the finite field F_q of q elements. The natural, lowquery, test for this property would be to pick the smallest dimension t = t_{q,d}~ d/q such that every function of degree greater than d reveals this feature on some tdimensional affine subspace of F_q^n and to test that f when restricted to a random tdimensional affine subspace is a polynomial of degree at most d on this subspace. Such a test makes only q^t queries, independent of n. Previous works, by Alon et al. (AKKLR), and Kaufman & Ron and Jutla et al., showed that this natural test rejected functions that were \Omega(1)far from degree dpolynomials with probability at least \Omega(q^{t}) (the results of Kaufman & Ron hold for all fields F_q, while the results of Jutla et al. hold only for fields of prime order). Thus to get a constant probability of detecting functions that were at constant distance from the space of degree d polynomials, the tests made q^{2t} queries. Kaufman & Ron also noted that when q is prime, then q^t queries are necessary. Thus these tests were off by at least a quadratic factor from known lower bounds. It was unclear if the soundness analysis of these tests were tight and this question relates closely to the task of understanding the behavior of the Gowers Norm. This motivated the work of Bhattacharyya et al., who gave an optimal analysis for the case of the binary field and showed that the natural test actually rejects functions that were \Omega(1)far from degree dpolynomials with probability at least \Omega(1). In this work we give an optimal analysis of this test for all fields showing that the natural test does indeed reject functions that are \Omega(1)far from degree $d$ polynomials with \Omega(1)probability. Our analysis thus shows that this test is optimal (matches known lower bounds) when q is prime. (It is also potentially best possible for all fields.) Our approach extends the proof technique of Bhattacharyya et al., however it has to overcome many technical barriers in the process. The natural extension of their analysis leads to an O(q^d) query complexity, which is worse than that of Kaufman and Ron for all q except 2! The main technical ingredient in our work is a tight analysis of the number of ``hyperplanes'' (affine subspaces of codimension $1$) on which the restriction of a degree d polynomial has degree less than $d$. We show that the number of such hyperplanes is at most O(q^{t_{q,d}})  which is tight to within constant factors.

Tight lower bounds for 2query LCCs over finite fieldsA Locally Correctable Code (LCC) is an error correcting code that has a probabilistic selfcorrecting algorithm that, with high probability, can correct any coordinate of the codeword by looking at only a few other coordinates, even if a fraction $\delta$ of the coordinates are corrupted. LCC's are a stronger form of LDCs (Locally Decodable Codes) which have received a lot of attention recently due to their many applications and surprising constructions.In this work we show a separation between 2query LDCs and LCCs over finite fields of prime order. Specifically, we prove a lower bound of the form $p^{\Omega(\delta d)}$ on the length of linear $2$query LCCs over $\F_p$, that encode messages of length $d$. Our bound improves over the known bound of $2^{\Omega(\delta d)}$ \cite{GKST06,KdW04, DS07} which is tight for LDCs. Our proof makes use of tools from additive combinatorics which have played an important role in several recent results in Theoretical Computer Science. We also obtain, as corollaries of our main theorem, new results in incidence geometry over finite fields. The first is an improvement to the SylvesterGallai theorem over finite fields \cite{SS10} and the second is a new analog of Beck's theorem over finite fields.