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/ |