CSDM Seminars

There are two important measures of the complexity of a boolean function: the sensitivity and block sensitivity. Whether or not they are polynomial related remains a major open question. In this talk I will survey some known results on this conjecture, and its connection with various combinatorial problems.

I will continue the exposition of different derandmization techniques for probabilistic logspace algorithms. The material of this talk will assume only little knowledge from the first talk.

Since the foundational results of Thomason and Chung-Graham-Wilson on quasirandom graphs over 20 years ago, there has been a lot of effort by many researchers to extend the theory to hypergraphs. I will present some of this history, and then describe our recent results that provide such a generalization and unify much of the previous work. One key new aspect in the theory is a systematic study of hypergraph eigenvalues. If time permits I will show some applications to Sidorenko's conjecture and the certification problem for random k-SAT. This is joint work with John Lenz.

I will survey some of the basic approaches to derandomizing Probabilistic Logspace computations, including the "classical" Nisan, Impagliazzo-Nisan-Widgerson and Reingold-Raz generators, the Saks-Zhou algorithm and some more recent approaches. We'll see why each falls short of complete derandomization, BPL=L, hopefully motivating further work on this basic problem.

Polar codes have recently emerged as a new class of low-complexity codes achieving Shannon capacity. This talk introduces polar codes with emphasis on the probabilistic phenomenon underlying the code construction. New results and connections to randomness extraction for structured sources are discussed.

I will describe the very recent breakthrough result by Gupta, Kamath, Kayal and Saptharishi which shows that every polynomial P in n variables, of degree d which is polynomial in n, and which can be computed by a polynomial sized arithmetic circuit over the complex numbers, can be also computed by a *depth 3* arithmetic circuit of size sub exponential in d; specifically size 2^{sqrt d polylog n} (the actual paper gives a more precise bound depending on the degree of the polynomial and size of the arithmetic circuit).

Expander graphs, in general, and Ramanujan graphs, in particular, have been objects of intensive research in the last four decades. Many application came out, initially to computer science and combinatorics and more recently also to pure mathematics (number theory, geometry, group theory ). In recent years, there has been an interest in generalizing this theory to higher dimensional simplical complexes. We plan to survey first the classical theory and then describe the more recent developments.

I will describe some recent results and problems regarding influence of sets of variables on Boolean functions: In 1989 Benny Chor conjectured that a balanced Boolean function with n variables has a subset S of size 0.4n with influence (1-c^n) where c0 follows from a theorem by Kahn, Kalai and Linial (KKL).I will present a recent counterexample by Kahn and me showing that up to the identity of c, the KKL bound cannot be improved.

http://math.ias.edu/files/seminars/MendelAbst.pdf