Tag - Graph theory

Irit Dinur: High Dimensional Expanders and PCPs

31st January, 2017

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.

Adam Marcus: Two Existence Proofs of Ramanujan Graphs

30th January, 2017

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.

Will Sawin: Ramanujan Covers

30th January, 2017

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.

Zeev Dvir: Extractors for Algebraic Sources

30th January, 2017

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.

Amnon Ta-Shma: An Efficient Reduction from Non-Malleable Extractors to Two-Source Extractors, and Explicit Two-Source Extractors with Near-Logarithmic Min-Entropy

30th January, 2017

The breakthrough result of Chattopadhyay and Zuckerman 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 2k, 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 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 et al. error reduction technique, and the constant degree dispersers of Zuckerman that also work against extremely small tests.

Eshan Chattopadhyay: Explicit Constructions of Two-Source Extractors and Ramsey Graphs

30th January, 2017

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 80s) 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 Erdős's challenge of matching the probabilistic method.