Student Seminar - Fall 2012

Date Speaker Title/Abstract
December 6, 2012 Gil Cohen Title: Non-Malleable Extractors

December 13, 2012 Avishay Tal Title: On the Minimal Fourier Degree of Symmetric Boolean Functions

Abstract: The talk will use basic Discrete Fourier tools. I will also discuss the learning juntas problem which was the main motivation for this work, and the special case of learning symmetric juntas. The article and abstract can be found here: http://eccc.hpi-web.de/report/2010/178/

December 20, 2012 Ilan Komargodski Title: The Spectrum of DeMorgan Formulas

Abstract: We will prove that every Boolean function that can be computed by a deMorgan formula of size $s$, can be approximated (in $L_2$ norm) by a polynomial of degree $\sqrt{s}$. We sill also talk about a relation between noise stability and the size of deMorgan formulas. The talk will be based on this paper.

December 27, 2012 Elazar Goldenberg Title: Clustering in the presence of adversarial noise

The talk is based on a joint work with Irit Dinur.

January 3, 2013 Shlomo Jozeph Title: Universal Factor Graphs

Abstract: The factor graph of an instance of a symmetric constraint satisfaction problem on $n$ Boolean variables and $m$ constraints (CSPs such as k-SAT, k-AND, k-LIN) is a bipartite graph describing which variables appear in which constraints. The factor graph describes the instance up to the polarity of the variables, and hence there are $2^{km}$ instances of the CSP that share the same factor graph. It is well known that factor graphs with certain structural properties make the underlying CSP easier to either solve exactly (e.g., for tree structures) or approximately (e.g., for planar structures). We are interested in the following question: is there a factor graph for which if one can solve every instance of the CSP with this particular factor graph, then one can solve every instance of the CSP regardless of the factor graph (and similarly, for approximation)? We call such a factor graph {\em universal}. As one needs different factor graphs for different values of $n$ and $m$, this gives rise to the notion of a family of universal factor graphs.
We initiate a systematic study of universal factor graphs, and present some results for max-$k$SAT. Our work has connections with the notion of preprocessing as previously studied for closest codeword and closest lattice-vector problems, with proofs for the PCP theorem, and with tests for the long code. Many questions remain open. Joint work with Uri Feige.

January 17, 2013 Igor Shinkar Title: Two-Sided Error Proximity Oblivious Testing

This is a joint work with Oded Goldreich. The paper can be found here http://eccc.hpi-web.de/report/2012/021/