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.
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.
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.
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.
After introducing Hamiltonian homeomorphisms and recalling some of their properties, I will focus on fixed point theory for this class of homeomorphisms. The main goal of this talk is to present the outlines of a C0 counterexample to the Arnold conjecture in dimensions four and higher.
We shall give a construction of the quantized sheaf of a Lagrangian submanifold in T∗N and explain a number of features and applications.
I will recall the construction of the space of states in a gauged topological A-model. Conjecturally, this gives the quantum cohomology of Fano symplectic quotients: in the toric case, this is Batyrev's presentation of quantum cohomology of toric varieties. Time permitting, I will discuss the role of 'Coulomb branches' in gauge theory in relation to equivariant quantum and symplectic cohomology.
Let n > 1. Given two maps of an n-dimensional sphere into Euclidean 2n-space with disjoint images, there is a ℤ/2 valued linking number given by the homotopy class of the corresponding Gauss map. We prove, under some restrictions on n, that this vanishes when the components are immersed Lagrangian spheres each with exactly one double point of high Maslov index.
Singular algebraic (sub)varieties are fundamental to the theory of smooth projective manifolds. In parallel with his introduction of pseudo-holomorphic curve techniques into symplectic topology 30 years ago, Gromov asked about the feasibility of introducing notions of singular (sub)varieties suitable for this field. I will describe a new perspective on this question and motivate its appropriateness in the case of normal crossings singularities. It leads to multifold versions of symplectic sum and cut constructions expected by Gromov and notions of one-parameter families of degenerations of symplectic manifolds and logarithmic tangent bundles in the spirit of the Gross-Siebert program. In our category, the standard triple point condition of algebraic geometry is the only obstruction to the smoothability of NC singularities.
Initiated by Langlands, the problem of computing the Hasse-Weil zeta functions of Shimura varieties in terms of automorphic L-functions has received continual study. We will discuss how recent progress in various aspects of the field has allowed the extension of the project to some Shimura varieties not treated before. In the particular case of orthogonal Shimura varieties, we discuss the computation of the Frobenius-Hecke traces on the intersection cohomology of their minimal compactifications, and the comparison to the Arthur-Selberg trace formula via the process of stabilization. Key ingredients include comparing Harish Chandra character formulas to Kostant's theorem on Lie algebra cohomology, and a comparison between different normalizations of the transfer factors for real endoscopy to get all the signs right.
