Symplectic homology for a Liouville cobordism (possibly filled at the negative end) generalizes simultaneously the symplectic homology of Liouville domains and the Rabinowitz-Floer homology of their boundaries. I intend to explain a conceptual framework within which one can understand it, and give a sample application which shows how it can be used in order to obstruct cobordisms between contact manifolds.
Cr closing lemma is an important statement in the theory of dynamical systems, which implies that for a Cr generic system the union of periodic orbits is dense in the nonwondering domain. C1 closing lemma is proved in many classes of dynamical systems, however Cr closing lemma with r > 1 is proved only for few cases. In this talk, I'll prove C∞ closing lemma for Reeb flows on closed contact three-manifolds. The proof uses recent developments in quantitative aspects of embedded contact homology (ECH). In particular, the key ingredient of the proof is a result by Cristofaro-Gardiner, Hutchings and Ramos, which claims that the asymptotics of ECH spectral invariants recover the volume of a contact manifold. Applications to closed geodesics on Riemannian two-manifolds and Hamiltonian diffeomorphisms of symplectic two-manifolds (joint work with M. Asaoka) will be also presented.
Given a finite group G and a set A of generators, the diameter diam(Γ(G,A)) of the Cayley graph Γ(G,A) is the smallest 𝓁 such that every element of G can be expressed as a word of length at most 𝓁 in A ⋃ A-1. We are concerned with bounding diam(G):= maxA diam(Γ(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+ε). We will discuss a recent, much simplified version of the proof.
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.
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.
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.
The standard WDVV equations are PDEs in the potential function that generates Gromov-Witten invariants. These equations imply relations on the invariants, and sometimes allow computations thereof, as demonstrated by Kontsevich-Manin (1994). We prove analogous equations for open Gromov-Witten invariants that we defined in a previous work. For (ℂPn,ℝPn), the resulting relations allow the computation of all invariants. The formulation of the open WDVV requires a lift of the big quantum product to relative cohomology. Surprisingly, this brings us to use moduli spaces of disks with geodesic conditions. No prior knowledge of the subjects mentioned above will be assumed.
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-ε for small ε. (Here, the goal is to minimize the number of random bits/slowdown as a function of ε). 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).
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.
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 F2 = <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.
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.
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.
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, coboundary expanders and the search for a random model.
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.
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 behaviour 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.
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 PGL2(ℤ/qℤ) with respect to Lubotzky, Phillips and Sarnak generators and navigation problem for diagonal vertices of LPS Ramanujan graphs. 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 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.
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.
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.
