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 depen

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.

With the notion of interaction with oracles as a unifying theme of much of my dissertation work, I discuss novel models and results for property testing and computational learning, with the use of Fourier analytic and probabilistic methods.

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

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.

A linear property of Banach spaces is called "local" if it depends on finite number of vectors and is invariant under renorming (i.e., distorting the norm by a finite factor). A famous theorem of Ribe states that local properties are invariant under (non linear) uniform-homeomorphisms, suggesting that local properties should have purely metric characterizations.
The Ribe program attempts to uncover explicit metric characterizations of local properties, and study them in the context of metric spaces. More broadly it attempts to apply ideas from Banach

We study the problem of constructing extractors for independent weak random sources. The probabilistic method shows that such an extractor exists for two sources on n bits with min-entropy k >= 2 log n. On the other hand, explicit constructions are far from optimal. Previously the best known extractor for (n,k) sources requires O(log n/log k) independent sources [Rao06, Barak-Rao-Shaltiel-Wigderson06]. In this talk I will give a new extractor that uses only O(log (log n/log k))+O(1) independent sources. This improves the previous best result exponentially.

Abstract:
We give near-tight lower bounds for the sparsity required in several dimensionality reducing linear maps. In particular, we show:
(1) The sparsity achieved by [Kane-Nelson, SODA 2012] in the sparse Johnson-Lindenstrauss lemma is optimal up to a log(1/eps) factor.
(2) RIP_2 matrices preserving k-space vectors in R^n with the optimal number of rows must be dense as long as k < n / polylog(n).