# Abstracts

### Monday, January 30th, 2017

9:30 am10:15 am
Randomness is widely used in various areas of computer science, and many of the applications require uniform, uncorrelated bit. However, most  sources of randomness in nature are defective and at best, only contain some amount of entropy. This leads to the area of randomness extraction, where an extractor is a deterministic procedure to produce pure random bits from a weak source. A central open problem (from the 80's) in this area is to extract from 2 independent weak sources (it is known that it is impossible to extract from just 1 weak source). In joint work with David Zuckerman, we resolve this problem. I will discuss the main ideas we use to solve this problem.

As a corollary of our 2-source  extractor, we obtain exponential improvements in explicit constructions of Ramsey graphs, a central object in extremal combinatorics. This is in a line of work spanning the last 70 years in an attempt to meet Erdos' challenge of matching the probabilistic method.
10:25 am11:10 am

Pivotal to recent exciting progress in randomness extractors is a pair of new pseudo-random objects - correlation breakers, and independence-preserving mergers. In this talk, we discuss these objects, their constructions, and applications.

11:40 am12:25 pm

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}.

2:00 pm2:45 pm

This talk will give a high level overview of (deterministic/seedless) extractors for random sources that are defined algebraically. These include sources distributed uniformly over an affine subspace or variety and sources sampled by polynomial maps. I will attempt to survey the various techniques that go into known constructions and the many open problems.

2:55 pm3:40 pm
Speaker:

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.

4:10 pm4:55 pm

This talk will review two different results regarding the existence of Ramanujan graphs. While both methods employ the method of interlacing polynomials, they are thematically quite different. The goal will be to highlight some of the commonalities and differences. This represents joint work with Dan Spielman and Nikhil Srivastava.

### Tuesday, January 31st, 2017

9:30 am10:15 am

No abstract available.

10:25 am11:10 am
I will describe a notion of high dimensional expansion called "agreement expansion", that can be described as a "sheaf cohomology". Agreement expansion captures certain PCP questions and in particular abstracts low degree tests such as plane vs. plane or line vs. line.
I will then describe an agreement question on the finite-field Grassmannian which is a high dimensional version of the Raz-Safra plane vs. plane low degree test. We will discuss a hypothesis regarding agreement expansion on the Grassmannian. This hypothesis, if true, implies NP-hardness of 2:1 games, a variant of the unique games conjecture.

Based on joint works with Tali Kaufman, Subhash Khot, Guy Kindler, Dor Mintzer, and Muli Safra.
11:40 am12:25 pm

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.

2:00 pm2:45 pm

Some thirty years ago, Lubotzky, Phillips and Sarnak used deep number-theoretic insights to construct the first Ramanujan graphs, as well as optimal pseudo-random generators for the rotation group SO(3). In the last decade their work has seen several developments: On the discrete side, in the study of Ramanujan complexes, which are finite simplicial complexes with the spectral behavior of infinite buildings. On the continuous side, in the study of pseudo random generators for U(n), motivated by the problem of constructing optimal gates for fault-tolerant quantum computation. Results on both the continuous and discrete sides draw on the study of Ramanujan digraphs, which seem to be of independent interest. Based on joint works with Eyal Lubetzky, Alex Lubotzky and Peter Sarnak.

2:55 pm3:40 pm

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.

4:10 pm4:55 pm

Markoff triples are integer solutions to the equation $x^2+y^2+z^2=3xyz$ which arose in Markoff's spectacular and fundamental work on diophantine approximation and has been henceforth ubiquitous in a tremendous variety of different fields in mathematics and beyond. We will review some of these and will then discuss recent joint work with Bourgain and Sarnak on the connectedness of the set of solutions of the Markoff equation modulo primes under the action of the group generated by Vieta involutions. We show in particular that for almost all primes the induced graph is connected. Similar results for composite moduli enable us to establish certain new arithmetical properties of Markoff numbers, for instance the fact that almost all of them are composite.

### Wednesday, February 1st, 2017

9:30 am10:15 am

Expander graphs have been studied intensively in the last 40 years. In recent years a theory of high dimensional expanders is emerging. We will describe some aspects of this theory such as topological expanders, coboundry expanders and the search for a random model.

10:25 am11:10 am

Expander graphs are widely studied, and various methods are known to obtain bounded degree expander graphs. Recently, there is a growing interest in understanding combinational expansion in higher dimensions (higher dimensional simplicial complexes). However, bounded degree combinatorial expanders (random or explicit) were not known till our work. We present a local to global criterion on a complex that implies combinatorial expansion. We use our criterion to present explicit bounded degree high dimensional expanders. This solves in the affirmative an open question raised by Gromov, who asked whether bounded degree high dimensional expanders could at all exist. Gromov has shown that high dimensional expansion of a $d$-dimensional complex, implies that the complex has a topological overlapping property; Namely, every continuous mapping of such a complex to $R^d$ must have a point in $R^d$ that is covered by a constant fraction of the topological $d$-simplices obtained by the mapping. Gromov has asked whether there exist bounded degree complexes with the topological overlapping property. Our work provides an affirmative answer to this question. Based on joint works with David Kazhdan and Alex Lubotzky, and with Shai Evra.

11:40 am12:25 pm

We will discuss the sharp transition in the time it takes simple random walk on regular Ramanujan graphs to approach the uniform distribution (known as the cutoff phenomenon), and geometric consequences (such as typical distances between vertices) that this implies for such graphs. We will then discuss how these ideas can be extended to regular Ramanujan digraphs, and consequently, to any d-dimensional Ramanujan complexes for d>1 associated with a simple group, with analogous geometric implications for these objects.

Base on joint works with Y. Peres and with A. Lubotzky and O. Parzanchevski.

### Thursday, February 2nd, 2017

9:30 am10:15 am

We will discuss some recent developments in several directions of spectral graph theory, including spectral bounds for graphs with general degree distribution and some variations of Ramanujan graph, satisfying vertex and edge expansion properties.

10:25 am11:10 am

One approach to studying properties of random walks on groups with random generators is to study word-measures on these groups. This approach was proven useful for the study of symmetric groups and random regular graphs. In the current work we focus on the unitary groups U(n). For example, if w is a word in F_2 = <x,y>, sample at random two elements from U(n), A for x and B for y, and evaluate w(A,B). The measure of this random element is called the w measure on U(n). We study the expected trace (and other invariants) of a random unitary matrix sampled from U(n) according to the w-measure, and find surprising algebraic properties of w that determine these quantities. This is joint work with Michael Magee.

11:40 am12:25 pm

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.

2:00 pm2:45 pm

In error-correcting codes, list-decoding (and related properties) are intimately related to pseudorandom objects like expanders and extractors.  As with many pseudorandom notions, list-decodability is not well-understood: It's easy to see that completely random codes have excellent list-decodability properties, and we have some very nice explicit constructions, but we still don't really understand this for many families of codes that we know and love.  One example is random linear codes; this has been well-studied, especially in the past few years, but there are still gaps in our knowledge.  In this talk, I'll discuss some recent work with Atri Rudra about the (average-radius) list decodability (and recovery) of random linear codes; along the way I'll highlight connections to and applications in expanders and extractors.

2:55 pm3:40 pm
Speaker:

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.

4:10 pm4:55 pm

A celebrated result by Impagliazzo and Wigderson is that under complexity theoretic hardness assumptions, every randomized algorithm can be transformed into one that uses only logarithmically many bits, with polynomial slowdown. Such algorithms can then be completely derandomized, with polynomial slowdown. In the talk I will discuss recent work attempting to extend this approach to: 1. Randomized algorithms that err with probability $1-\epsilon$ for small $\epsilon$. (Here, the goal is to minimize the number of random bits/slowdown as a function of $\epsilon$). 2. Known SAT-solving randomized algorithms. (Here, polynomial slowdown is a deal breaker as it gives trivial algorithms that run in super exponential time). 3. Randomized algorithms that sample from probability distributions. (Here, the goal is to sample a statistically-close distribution using only few random bits). Based on joint work with Artemenko, Impagliazzo and Kabanets.

### Friday, February 3rd, 2017

9:30 am10:15 am

We present an approach to show the existence of large expanders in locally sparse graphs and in sparse (including super-critical) random graphs, as well as its consequences for extremal questions and positional games.

10:25 am11:10 am

Spectral gaps of matrices are related to many basic properties, like mixing times, expansion, isoperimetry and more. We will see a connection between spectral gaps and sign-rank. The sign-rank of a boolean matrix is the minimum dimension of real space in which the matrix can be realized as a point-halfspace incidence matrix. Sign-rank is deeply related to learning theory and communication complexity. We will see that regular matrices with large spectral gaps have high sign-rank; roughly speaking, this means that a matrix with large spectral gap can not be realized in low dimensional real space using halfspaces. This is another aspect in which matrices with a large spectral gap are pseudo-random. Based on work with Noga Alon and Shay Moran.

11:40 am12:25 pm

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.

2:00 pm2:45 pm

Given a finite group $G$ and a set $A$ of generators, the diameter $\diam(\Gamma(G,A))$ of the Cayley graph $\Gamma(G,A)$ is the smallest $\ell$ such that every element of $G$ can be expressed as a word of length at most $\ell$ in $A \cup A^{-1}$. We are concerned with bounding $\diam(G):= \max_A\diam(\Gamma(G,A))$. It has long been conjectured that the diameter of the symmetric group of degree $n$ is polynomially bounded in $n$. In 2011, Helfgott and Seress gave a quasipolynomial bound (exp((log n)^(4+epsilon))). We will discuss a recent, much simplified version of the proof.