Math of Computing According to Lattices (2023)

The 15 talks of the symposium presented a wide array of topics related to complexity theory in general and lattices, in areas including analysis, algebra, physics and number theory. About half of the talks were directly and intimately related to the topic of lattices. The topic of the other half of the talks were indirectly related to lattices, suggesting new possible connections between areas such as communication complexity and hardness of approximation to lattices.

1. Cryptography: we had two talks whose primary focus was cryptographic applications:
   1. Vinod Vaikuntanathan told us about his work about fully homomorphic encryption (FHE) and about how modern constructions of fully homomorphic encryptions rely on the complexity of lattice problems.
   2. Noah Stephens-Davidowitz told us about his recent work about the reverse Minkowski theorem, asserting that lattices that are locally dense (containing many lattice points in balls around the center) must has a sub-lattice that is globally dense (i.e., small determinant). He also told us about applications of this result to cryptography and some ideas in the proof inspired by convex geometry. Finally, Noah Stephens-Davidowitz mentioned some recent applications of their theorem to classical algorithms, getting a better asymptotic algorithm for integer programming.
2. Quantum Computation and Quantum Algorithms: we had three talks whose primary focus was quantum computation.
   1. Oded Regev told us about a polynomial time algorithm for factoring integers into primes. His algorithm improves on Shor’s well known algorithm in that fewer quantum gates are required. However, the algorithm requires more quantum memory bits, and its correctness also relies on conjectures from number theory. Oded’s talk inspired a discussion among the number theory experts in the audience about the correctness of the conjecture needed.
   2. A. Yaron Oz told us about the notion of entropy of entanglement and about the model of random quantum circuit, which seems like an efficient way to generate a quantum state with a high entropy of entanglement. Proving it is an outstanding and important open problem.
   3. Omri Shmueli told us about the idea of quantum money and about his new ideas of constructing quantum money using lattices and lattice based cryptographic ideas.
3. Algorithms: we had three talks whose primary focus was algorithms.
   1. Avi Wigderson told us about the rank of symbolic matrices and tensors, which arises naturally when studying problems such as the approximation of the permanent, finding perfect matchings, proving functional inequalities and so on. Avi Wigderson explained the relationship between this notion and areas such as geometry and submodular optimization.
   2. Or Ordentlich told us about analog-to-digital conversion of signals and an operation which offers a more efficient conversion scheme. Or  Ordentlich told us that so long as the sampling rate of the converter is sufficiently large, the modulo operation may be unwrapped (i.e., undone), and that to do so one has to use ideas from lattices and computational problems over lattices.
   3. Joseph Silverman told us about the discrete Fourier transform, which is a very powerful tool in algorithms. He also told us about the problem of inverting the discrete Fourier transform and how it relates to the closest vector problem over lattices.
4. Number theory: we had two talks whose primary focus was number theory.
   1. Zeev Rudnick told us about the problem of counting lattice problems in balls, and how understanding accurate estimates of them relates to problems in random matrix theory and quantum chaos.
   2. Barak Weiss presented the notions of packing and covering radiuses of a convex body and discussed his recent work establishing almost optimal upper bounds on the covering radius of a convex body.
5. Analysis and Complexity: we had five talks whose primary focus was analytical problems directly inspired from classical applications from theoretical computer science.
   1. Shachar Lovett told us about his new result establishing explicit separation between randomized and deterministic multi-party communication complexity. The underlying proof technique seems to be much more versatile. His result builds on a recent breakthrough result of Kelley and Meka about the problem of finding 3-term arithmetic progressions in dense sets of integers.
   2. Elchanan Mossel told us about discrete Fourier analysis on probability measures that go beyond product measures, such as the Ising model. Mossel told us about his recent new result establishing an analog of the Kahn-Kalai-Linial theorem for measures satisfying a log-Sobolev inequality and correlation decay.
   3. Dor Minzer told us about his result about 3-wise correlations of functions and its relation to probabilistically check proofs, multi-party parallel repetition and additive combinatorics. He mentioned a case where their technique fails, which has to do with analyzing objects related to a certain lattice over the integers.
   4. Tamar Ziegler told us about a new notion of randomness of collections of polynomials called the relative rank of a collection, which refines existing notions of ranks and admits a more efficient regularity lemma. The new notion is motivated from additive combinatorics, number theory and algebra.
   5. Muli Safra told us about the SVP and CVP problems, as well as possible relations he suspects regarding the connection between their complexity and the complexity of 2-to-1 games with perfect completeness.

Eitan Bachmat
Ben Gurion University

Modular Dualities in Queues

Duality and self-duality of modular forms plays a key role in number theory and string theories. In this talk, we consider two systems of queues, one displaying an exact duality of the same type (express line queues) and another displaying an approximate form of this duality (airplane boarding). Eitan Bachmat will show how Riemann’s work on the functional equation can not only help us understand the performance of these systems but also how the queueing setting raises interesting questions in number theory with computational aspects.
 

Emmanuel Breuillard
University of Oxford

Dynamics on the Space of Lattices and the Subspace Theorem

Schmidt’s subspace theorem is a fundamental result in Diophantine approximation regarding linear forms with algebraic coefficients. In joint work with N. de Saxcé, Emmanuel Breuillard has recast this result in the framework of dynamics of diagonal flows on the space of lattices, where the study of successive minima acquires a concrete geometrical meaning. It turns out that old ideas of Grayson and Stuhler on Harder-Narasimhan filtrations and its related slope formalism play a key role in geometric description of the subspace theorem. Combining this with work of Kleinbock-Margulis and Kleinbock-Lindenstrauss-Weiss yields new results on metric Diophantine approximation on manifolds and Lie groups.
 

Pravesh Kothari
Carnegie Mellon University

The Sum-of-Squares Approach to Learning Mixtures of Gaussians

In the past five years, a new approach has emerged for the century-old problem of learning the parameters of a mixture of Gaussians from an independent sample. This new approach uses the sum-of-squares semidefinite programs to reduce the problem to verifying basic analytic properties such as concentration and anti-concentration of probability distributions from an independent sample. The resulting approach gives the fastest known algorithms for learning Gaussian mixtures, extends to significantly more general mixture models and can even handle adversarial corruptions in samples.

Recent works on continuous variants of the learning-with-errors problem have shown a basic connection between solving natural problems in integer lattices to learning mixtures of Gaussians. A tantalizing direction for future work is to investigate whether the new sum-of-squares-based approach can give a line of attack on foundational algorithmic problems on integer lattices.

In this talk, Pravesh Kothari will explain the conceptual foundations of the sum-of-squares approach to learning mixtures with an eye for potential applications to lattice problems.
 

Shachar Lovett
University of California, San Diego

Number-on-Forehead Separations

The number-on-forehead (NOF) model in communication complexity poses significant challenges when it comes to proving lower bounds. Strong lower bounds in this model are notoriously difficult to establish and are intimately linked to famous open problems in additive combinatorics. A huge breakthrough in additive combinatorics was recently made by Kelley and Meka, who vastly improved the bounds on sets without 3-term arithmetic progressions. Building on and extending their techniques, Shachar Lovett and collaborators have constructed an explicit 3-player function such that randomized protocols can easily solve it, but deterministic protocols require a polynomial amount of communication. The approach hinges on a new method that reduces the analysis of cylinder intersections (which are the combinatorial core of NOF protocols) to cubes, assuming the underlying function is pseudorandom enough.

Based on joint work with Zander Kelley and Raghu Meka.
 

Dor Minzer
Massachusetts Institute of Technology

Approximability, Parallel Repetition, Additive Combinatorics and Lattices (?)

Dor Minzer will present a recent line work that aims to characterize precise approximability thresholds for approximating NP-hard constraint satisfaction problems on satisfiable instances. The analytic tools developed so far have found applications to the linearity testing problem, the 3-player parallel repetition theorem, additive combinatorics and potentially more. At the center of this work lies a new notion of Abelian embedding of predicates. While Minzer has been able to handle embeddings into finite groups so far, embeddings into the set of integers and more generally into integer lattices seems to be the current hurdle being faced.

Subhash Khot and Dor Minzer. Based on joint works with Amey Bhangale, Mark Braverman and Noam Lifshitz.
 

Elchanan Mossel
Massachusetts Institute of Technology

Beyond Lattices — Two Examples

Elchanan Mossel will give two recent examples where results that are known for lattices were extended to less rigid structures. The first example relates random walks on the 1D lattices to the games of war and the second talks about the KKL theorem for spin systems.

Based on joint works with M. Bhatia, B. Chin, N. Mani and with F. Koehler, N. Lifshitz and D. Minzer.
 

Or Ordentlich
Hebrew University of Jerusalem

Unwrapping of Modulo Reduced Signals
View Slides (PDF)

Modulo analog-to-digital converters (ADCs) form a novel paradigm for data acquisition, where temporal and spatial correlations between the analog signals to be digitized are exploited for reducing the burden of the ADCs, without sacrificing resolution. Such ADCs quantize a modulo wrapped version of their input signal rather than the signal itself. Or Ordentlich will discuss the advantages of this approach and illustrate how the modulo operation can be unwrapped in various settings using the statistical dependencies within the acquired process. Ordentlich will show that for signals whose Fourier transform is supported on a bounded interval, modulo reduction entails no loss of information, as long as the sampling rate is above the Nyquist rate. Ordentlich will also discuss algorithms for recovering Gaussian vectors from their modulo wrapped measurements in the case where the joint statistics are known, as well as in the “blind” case, where the joint statistics are not known.

Bases on joint work with Elad Romanov, Amir Weiss, Everest Huang and Gregory W. Wornell.
 

Yaron Oz
Tel-Aviv University

Quantum Computation
View Slides (PDF)

Yaron Oz will discuss various aspects of quantum computation, including quantum entanglement and quantum chaos.
 

Oded Regev
New York University

An Efficient Quantum Factoring Algorithm

We show that \(n\)-bit integers can be factorized by independently running a quantum circuit with \(\tilde{O}(n^{3/2})\) gates for \(\sqrt{n}+4\) times, and then using polynomial-time classical post-processing. The correctness of the algorithm relies on a number-theoretic heuristic assumption reminiscent of those used in subexponential classical factorization algorithms. It is currently not clear if the algorithm can lead to improved physical implementations in practice.
 

Zeev Rudnick
Tel-Aviv University

Statistics of Lattice Points and Energy Levels
View Slides (PDF)

Counting lattice points in expanding regions is a classical topic in number theory, with many applications. Zeev Rudnick will survey old and new problems about the statistical study of such lattice point counts, and their connections to quantum chaos, random matrix theory and Teichmüller theory.
 

Omri Shmueli
Tel-Aviv University

Lattice-Based Quantumness

Quantum unclonable states are one of the fundamental objects in quantum cryptography. It is known how to generate unclonable states based on cryptographic objects like post-quantum one-way functions (or when needing less properties from the states, even with no assumptions at all), and it is also known how to generate unclonable states which are publicly verifiable, using newer techniques based on subspace states and post-quantum indistinguishability obfuscation.

One of the central open problems in current quantum cryptography is constructing a scheme where unclonable states are not only publicly verifiable, but publicly generatable, that is, given a common reference string (CRS), anyone can generate an unclonable state, which is not only publicly verifiable to everyone, but also unclonable to everyone, including that generating computer.

While there is no proven construction, there is a lattice-based scheme in folklore, where the unclonable states are generated from a random lattice. In this talk, Omri Shmueli will explore some of the known facts in this sub-field and suggest open questions.
 

Joseph Silverman
Brown University

Lattices Associated to Partial Discrete Fourier Transforms
View Slides (PDF)

Let F be the finite field with q elements. The discrete Fourier transform (DFT) is an F-linear map from F^N to F^N that changes convolution products into coordinate-wise products, and it exhibits a Heisenberg-type behavior in the sense that it is difficult to find a vector with many small coordinates whose DFT-image also has many small coordinates. Joseph Silverman will discuss the closest vector problem associated with inverting the DFT, if one is given partial image information and asked to find a small pre-image. Silverman will describe a classical digital signature scheme based on this problem and discuss some recent work on a formal reduction proof from the signature scheme to the underlying lattice problem.
 

Noah Stephens- Davidowitz
Cornell University

A Reverse Minkowski Theorem
View Slides (PDF)

Minkowski’s celebrated first theorem is one of the foundational results in the study of the geometry of numbers, and it has innumerable applications from basic number theory to convex geometry to cryptography. It tells us that a lattice (i.e., a linear transformation of Z^n) that is globally dense (i.e., has low determinant) must be locally dense (i.e., must have many short vectors). Noah Stephens-Davidowitz will show a proof of a nearly tight converse to Minkowski’s theorem, originally conjectured by Daniel Dadush — a lattice with many short points must have a sublattice with small determinant. This “reverse Minkowski theorem” has numerous applications in, e.g., complexity theory, additive combinatorics, cryptography, the study of Brownian motion on flat tori, algorithms for lattice problems, etc. Just recently, it was used by Reis and Rothvoss to give the first asymptotic improvement to integer programming in nearly forty years.

Based on joint work with Oded Regev.
 

Andrew Sutherland
Massachusetts Institute of Technology

Lattices in Computational Number Theory and Arithmetic Geometry
View Slides (PDF)

Number theory has long been a rich source of lattices with interesting structure that have applications to other fields such as coding theory and cryptography, but in this talk, Andrew Sutherland will discuss the role lattices as computational tools in number theory and arithmetic geometry. The factorization of integer polynomials is perhaps the most well-known example, but Sutherland will also discuss some examples that are less well known, including algorithms to identify number fields and algorithms to find small solutions to Diophantine equations.
 

Vinod Vaikuntanathan
Massachusetts Institute of Technology

Lattices, Continuous Learning with Errors and Applications
View Slides (PDF)

Vinod Vaikuntanathan will describe the continuous learning with errors (CLWE) problem, its connection to lattices, and its applications to problems in statistics. In particular, Vaikuntanathan will show how the hardness of the CLWE problem directly implies the nearly optimal hardness of the long-studied Gaussian mixture learning problem.
 

Barak Weiss
Tel Aviv University

New Bounds on Lattice Covering Volumes, and Nearly Uniform Covers

Let L be a lattice in R^n and let K be a convex body. The covering volume of L with respect to K is the minimal volume of a dilate rK, such that L+rK = R^n, normalized by the covolume of L. Pairs (L,K) with small covering volume correspond to efficient coverings of space by translates of K, where the translates lie in a lattice. Finding upper bounds on the covering volume as the dimension n grows is a well-studied problem in the so-called “geometry of numbers,” with connections to practical questions arising in computer science and electrical engineering. In a recent paper with Or Ordentlich and Oded Regev, Barak Weiss obtained substantial improvements to bounds of Rogers from the 1950s. In another recent paper, Weiss obtained bounds on the minimal volume of nearly uniform covers (to be defined in the talk). The key to these results are recent breakthroughs by Dvir and others regarding the discrete Kakeya problem. Weiss will give an overview of the questions and results.
 

Avi Wigderson
Institute for Advanced Study and Princeton University

The Rank of Symbolic Matrices
View Slides (PDF)

Avi Wigderson will define the rank of symbolic matrices and explain why understanding and computing it is a fundamental problem in several areas of math and computer science. Wigderson will present two related (indeed, special cases) of this problem – the perfect matching in bipartite graphs, and the non-commutative rank of symbolic matrices. Wigderson will discuss one line of algorithms for both, which has led to a rich theory of geodesically convex algorithms for certain problems with symmetries. Finally, Wigderson will discuss different algorithms for these problems. In particular, he will sketch the ideas of one which employs submodular optimization on modular lattices, and convexity in CAT(0) spaces. Wigderson will state several open problems and directions for further research.

A large part of this talk is based on joint works with Zeyuan Allen-Zhu, Peter Burgisser, Cole Franks, Ankit Garg, Leonid Gurvits, Pavel Hrubes, Yuanzhi Li, Visu Makam, Rafael Oliveira and Michael Walter over the past decade.
 

Tamar Ziegler
Hebrew University

Relative Rank and Regularity

The notion of Schmidt rank/strength for a collection of m polynomials plays an important role in additive combinatorics, number theory and commutative algebra; high rank collections of polynomials are “pseudorandom.” An arbitrary collection of polynomials is not necessarily of high rank, but via a regularity procedure is contained in an ideal generated by a huge (depending on m) high rank collection of polynomials. Tamar Ziegler will describe a refined notion of rank/strength that allows for a new regularization procedure with polynomial dependence on m, while maintaining the pseudorandomness properties.