The breakthrough result of Chattopadhyay and Zuckerman \cite{CZ15} gives a reduction from the construction of explicit non-malleable extractors to the construction of explicit two-source extractors and bipartite Ramsey graphs. However, even assuming the existence of optimal explicit non-malleable extractors only gives a two-source extractor (or a Ramsey graph) for $\poly(\log n)$ entropy, rather than the optimal $O(\log n)$. In this paper we modify the construction to solve the above barrier. Using the currently best explicit non-malleable extractors we get an explicit bipartite Ramsey graphs for sets of size $2^k$, for $k=O(\log n \log\log n)$. Any further improvement in the construction of non-malleable extractors would immediately yield a corresponding two-source extractor. Intuitively, Chattopadhyay and Zuckerman use an extractor as a sampler, and we observe that one could use a weaker object -- a \emph{somewhere-random condenser} with a small entropy gap and a very short seed. We also show how to explicitly construct this weaker object using the Raz \etal error reduction technique \cite{RRV99}, and the constant degree dispersers of Zuckerman that also work against extremely small tests \cite{Zuc06}.

The breakthrough work of Marcus, Spielman, and Srivastava showed that every bipartite Ramanujan graph has a bipartite Ramanujan double cover. Chris Hall, Doron Puder, and I generalized this to covers of arbitrary degree. I will explain the proof, with emphasis on how group theory and representation theory are useful for this problem.

We discuss our p-adic version of the best known quantum compiling algorithm on a single qubit that is developed by Ross and Selinger. Two main applications of our algorithm are computing optimally the discrete log of diagonal matrices of $PGL_2(\mathbb{Z}/q\mathbb{Z})$ with respect to Lubotzky, Phillips and Sarnak generators and navigation problem for diagonal vertices of LPS Ramanujan graphs \cite{LPS}. My algorithm and Ross and Selinger's algorithm are conditional on assuming one can factor quickly, and a natural conjecture on the distribution of integers representable as a sum of two squares. 

I will report on the latest results on super-approximation. Roughly super-approximation gives us the right condition in order to get a family of expanders out of the Cayley graphs of the congruence quotients of a group generated by finitely many rational matrices. I will mention a sum-product phenomenon in number fields which is used in the proof of super-approximation. Some of the applications of super-approximation will be mentioned at the end.

Quite a few people are trying to answer the question in the title. Various interesting approaches are being proposed based on algebraic, geometric and topological notions. In this talk I will advocate a combinatorial approach that is based on sparsity and regularity and focuses on notions of low discrepancy. This approach makes it particularly desirable to investigate random high-dimensional combinatorial objects.

Locally testable and locally decodable codes are special families of error-correcting codes that admit highly efficient algorithms that detect and correct errors in transmission in sublinear time, probing only a small number of entries of the corrupted codeword. In recent years, there have been new developments on the construction of locally testable and locally decodable codes using graph-based/combinatorial constructions that exploit the power of expander graphs. These eventually led to the construction of asymptotically good locally testable and locally decodable codes with small (sub-polynomial) query complexity, and with near-optimal error-correction capabilities (approaching the Singleton and Gilbert-Varshamov bounds). In this talk I will survey some of these constructions and highlight the role of expander graphs in their development.

A Santha-Vazirani (SV) source is a sequence of random bits where the conditional distribution of each bit, given the previous bits, can be partially controlled by an adversary. Santha and Vazirani showed that deterministic randomness extraction from these sources is impossible. Recently, Beigi, Etesami and Gohari (ICALP 2015) studied the generalization of SV sources for non-binary sequences and showed that unlike the binary case, deterministic randomness extraction in the generalized case is sometimes possible. Beigi, Etesami and Gohari presented a necessary condition and a sufficient condition for the possibility of deterministic randomness extraction. These two conditions coincide in ?non-degenerate? cases and completely characterize the randomness extraction problem for non-degenerate cases. In this work, we continue the study of deterministic randomness extraction from non-binary SV sources and obtain following results. 1) We completely characterize the randomness extraction problem for both non-degenerate and degenerate cases by providing a necessary and sufficient condition for the possibility of randomness extraction from SV sources. This condition reduces to the condition of Beigi, Etesami and Gohari when the SV source is non-degenerate and fills the gap in the degenerate case. 2) We further improve both the output length and the error of the extractor of Beigi, Etesami and Gohari from a single bit with inverse polynomial error to linear number of bits with exponential error. As a corollary, in the non-degenerate case, a linear number of bits can be extracted and with exponentially small error when randomness extraction is possible. 3) We show that for any extractable SV source one can always extract a random bit with inverse polynomial error. And we show the error cannot be improved beyond inverse polynomial for a specific degenerate source. Joint work with Salman Beigi, Andrej Bogdanov, Omid Etesami.