Lattices: Geometry, Algorithms and Hardness 2020
2020-02-18..2020-02-21
Berkeley, United States
[The Mathematics of Modern Cryptography, Quantum and Lattices Joint Reunion Workshop, Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017), Interactive Complexity 2018, Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015), Beyond the Boolean Cube 2023]
| title | author | length |
|---|---|---|
| A Reverse Minkowski Theorem | Noah Stephens-Davidowitz | 01h 00m |
Proves a precise reverse Minkowski: local → sublattice density statement: if every sublattice has det ≥1 then any ball has at most 2^{O(n)} Gaussian mass (and… | ||
| Successive Minima-Type Inequalities | Martin Henk | 33m |
Defines and works with successive minima and proves volume and counting analogues: classical bounds like volume≥2^n ⇒ nontrivial lattice point and Minkowski's… | ||
| Short Simplex Paths in Lattice Polytopes | Alberto del Pia | 31m |
Algorithms produce explicit simplex edge paths on lattice polytopes in a box, with a first constructive method giving a path length bounded roughly by n^4 · K… | ||
| The n by n by n Cube and a Hyperplane | Imre Bárány | 30m |
Imre Barany, Rényi Institute
https://simons.berkeley.edu/talks/n-n-n-cube-and-hyperplane-0
Lattices: Geometry, Algorithms and Hardness | ||
| New Bounds on the Covering Density | Barak Weiss | 52m |
Proves a concrete improvement: random lattices have exponentially small probability of large covering density once body volume reaches about n^2 (replacing… | ||
| An LLL Algorithm for Module Lattices | Alice Pellet-Mary | 52m |
An LLL-style algorithm produces short vectors in module lattices over any number field, giving an approximation factor roughly 2^{rank} (quasi‑polynomially… | ||
| Algorithms for the k-List Problems | Elena Kirshanova | 01h 06m |
Reduction shows LWE samples map to extended dihedral-coset states when the number of shifts M and sample count L satisfy L ≈ Q^n / M, so small M forces many… | ||
| New Reductions and Algorithms for Ideal Lattices via Arakelov Random Walks | Léo Ducas, Benjamin Wesolowski | 59m |
Shows a worst-case to average-case reduction for Hermite-ideal SVP: if an oracle solves random ideal lattices of a ring, the reduction solves any ideal lattice… | ||
| Challenges in Evaluating Costs of known Lattice Attacks | Tanja Lange, Daniel J. Bernstein | 57m |
Claims that commonly used cost formulas for lattice attacks are unreliable: experiments and SAGE-scripted tests show the BKZ-beta delta is unreliable and the… | ||
| On the Concrete Security of LWE with Small Secret | Lynn Chua | 30m |
Experimental evaluation embeds LWE into a larger lattice and reduces LWE→BDD→USVP, then runs BKZ 2.0 (fplll) for dimensions n=40–200, block sizes… | ||
| Integer Programming and Convolution, with Applications | Klaus Jansen | 38m |
Provides an algorithm for integer programs Ax=b, x≥0 with m constraints and coefficients ≤Δ that replaces the dependence on the right-hand side B by log B, and… | ||
| On Minimal Support for Lattices and Semigroups | Timm Oertel | 31m |
Assumes Ax = b, x ≥ 0, gcd of minors = 1 and asks how small the support of an integer solution can be. Results give explicit bounds: for Hilbert-basis matrices… | ||
| Distance-Sparsity Transference for Lattice Points in Knapsack Polytopes | Iskander Aliev | 28m |
Proves a quantitative transference: a concrete inequality that converts a distance-to-vertex bound for a knapsack polytope into an explicit sparsity bound on… | ||
| PPP-completeness with connections to Cryptography | Aikaterini Sotiraki | 37m |
Shows a reduction from Minkowski-style lattice search to PPP and proves a constrained SIS variant (solutions x in {−1,0,1}^n or infinity-norm ≤1 with m… | ||
| Provable Sieving Algorithms for SVP and CVP in the l_p norm | Priyanka Mukhopadhyay | 19m |
Presents provable sieving methods for SVP and CVP in lp norms that replace AKS-style ball covers with partitions of the LP ball into hypercubes, allowing… | ||
| When Cryptography Meets Modern Channel Coding | Joseph J. Boutros | 01h 09m |
Constructive families of lattices (Construction A with LDPC/GLD codes) reach the Poltyrev threshold, with Sigma_max = V^{2/n}/(2πe), by letting the alphabet… | ||
| Lattice Packings: An Upper Bound on the Number of Perfect Lattices | Wessel van Woerden | 30m |
Gives a geometric proof that the number of non-similar perfect lattices PD has an upper bound exp(O(d^2 log d)) improving previous exp(O(d^3 log d)). Uses… | ||
| A Simplex-Type Voronoi Algorithm Based on Short Vector Computations of Copositive Quadratic Forms | Achill Schurmann | 27m |
An adaptation of the Voronoi simplex algorithm traverses the cone of completely positive matrices to produce explicit certificates writing an input matrix as a… | ||
| Coloring the Voronoi Tessellation of Lattices | Mathieu Dutour Sikiric | 40m |
The talk studies coloring the Voronoi tessellation of Euclidean lattices: assigning colors to Voronoi cells so adjacent cells differ. It focuses on algorithmic… | ||
| On Approximating the Covering Radius and Finding Dense Lattice Subspaces | Daniel Dadush | 01h 00m |
Links covering-radius approximation to integer programming by reducing to lattice enumeration using M-ellipsoids and Voronoi connectivity, gives… | ||
| nothing matches | ||