TY - GEN
T1 - Towards Strong Reverse Minkowski-Type Inequalities for Lattices
AU - Dadush, Daniel
AU - Regev, Oded
N1 - Publisher Copyright:
© 2016 IEEE.
PY - 2016/12/14
Y1 - 2016/12/14
N2 - We present a natural reverse Minkowski-type inequality for lattices, which gives upper bounds on the number of lattice points in a Euclidean ball in terms of sublattice determinants, and conjecture its optimal form. The conjecture exhibits a surprising wealth of connections to various areas in mathematics and computer science, including a conjecture motivated by integer programming by Kannan and Lovasz (Annals of Math. 1988), a question from additive combinatorics asked by Green, a question on Brownian motions asked by Saloff-Coste (Colloq. Math. 2010), a theorem by Milman and Pisier from convex geometry (Ann. Probab. 1987), worst-case to average-case reductions in lattice-based cryptography, and more. We present these connections, provide evidence for the conjecture, and discuss possible approaches towards a proof. Our main technical contribution is in proving that our conjecture implies the l2 case of the Kannan and Lovasz conjecture. The proof relies on a novel convex relaxation for the covering radius, and a rounding procedure based on 'uncrossing' lattice subspaces.
AB - We present a natural reverse Minkowski-type inequality for lattices, which gives upper bounds on the number of lattice points in a Euclidean ball in terms of sublattice determinants, and conjecture its optimal form. The conjecture exhibits a surprising wealth of connections to various areas in mathematics and computer science, including a conjecture motivated by integer programming by Kannan and Lovasz (Annals of Math. 1988), a question from additive combinatorics asked by Green, a question on Brownian motions asked by Saloff-Coste (Colloq. Math. 2010), a theorem by Milman and Pisier from convex geometry (Ann. Probab. 1987), worst-case to average-case reductions in lattice-based cryptography, and more. We present these connections, provide evidence for the conjecture, and discuss possible approaches towards a proof. Our main technical contribution is in proving that our conjecture implies the l2 case of the Kannan and Lovasz conjecture. The proof relies on a novel convex relaxation for the covering radius, and a rounding procedure based on 'uncrossing' lattice subspaces.
KW - Geometry
KW - Lattices
KW - Minkowski's first theorem
UR - http://www.scopus.com/inward/record.url?scp=85009376175&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85009376175&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2016.55
DO - 10.1109/FOCS.2016.55
M3 - Conference contribution
AN - SCOPUS:85009376175
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 447
EP - 456
BT - Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
PB - IEEE Computer Society
T2 - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
Y2 - 9 October 2016 through 11 October 2016
ER -