Wednesday October 18, 11am-12pm, Klaus 1116: Introduction to Lattices;
---
In this lecture, we will give a brief introduction to the lattices and discuss the seminal result
of Micciancio and Voulgaris (2010) that gives a 2^O(n) time algorithm for computing a closest vector.
We will also discuss the result by Dadush and Vempala (2012) to enumerate all the lattice points
in a general convex body K in time 2^O(n) times the maximum number of points that any translate may contain.
Thursday October 19, 11am-12pm Klaus 2447: The Reverse Minkowski Theorem
---
We explain the Reverse Minkowski Theorem due to Regev and Stephens-Davidowitz (2017). Formally the
result states that for any lattice Lambda that does not contain a sublattice of determinant less than 1,
the sum of Gaussian weights satisfies rho_1/t(Lambda) <= 3/2 where t = Theta(log n).
In particular this implies that, any such lattice contains at most a quasi-polynomial number of vectors of length at most O(1).
The result is based on advanced concepts from convex geometry.
Friday October 20, 1pm-2pm, Skiles 005: The Subspace Flatness Conjecture and Faster Integer Programming
---
In a seminal paper, Kannan and Lovász (1988) considered a quantity μ_KL(Λ,K) which denotes the best volume-based
lower bound on the covering radius μ(Λ,K) of a convex body K with respect to a lattice Λ.
Kannan and Lovász proved that μ(Λ,K)≤n⋅μ_KL(Λ,K) and the Subspace Flatness Conjecture by Dadush (2012) claims a O(log(n)) factor suffices,
which would match the lower bound from the work of Kannan and Lovász.
We settle this conjecture up to a constant in the exponent by proving that μ(Λ,K)≤O(log^3(n))⋅μ_KL(Λ,K).
Our proof is based on the Reverse Minkowski Theorem due to Regev and Stephens-Davidowitz (2017).
Following the work of Dadush (2012, 2019), we obtain a (log(n))^O(n)-time randomized algorithm to solve
integer programs in n variables. Another implication of our main result is a near-optimal flatness constant of O(n*log^3(n)).
