Approximate Voronoi cells for lattices, revisited

Thijs Laarhoven

arxiv: 1907.04630 · v1 · pith:JXBJ4SNXnew · submitted 2019-07-10 · 💻 cs.DS · cs.CG· cs.CR· cs.DM

Approximate Voronoi cells for lattices, revisited

Thijs Laarhoven This is my paper

Pith reviewed 2026-05-24 23:36 UTC · model grok-4.3

classification 💻 cs.DS cs.CGcs.CRcs.DM

keywords approximate Voronoi cellsclosest vector problemGaussian heuristicCVPPrandomized iterative slicertime-memory tradeoffslatticespreprocessing

0 comments

The pith

The volumes of approximate Voronoi cells for high-dimensional lattices follow precise asymptotics under the Gaussian heuristic, settling an open problem and improving CVPP algorithms.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper determines the exact asymptotic volume of approximate Voronoi cells in lattices using the Gaussian heuristic. A sympathetic reader would care because this resolves uncertainty in complexity estimates for solving the closest vector problem with preprocessing. The result directly yields tighter upper bounds on the running time of the randomized iterative slicer when memory is limited to less than 2^{0.076d + o(d)}. It further establishes continuous time-memory trade-offs even with smaller memory amounts and shows that subexponential advice leads to query times scaling like d^{d/2 + o(d)}, matching worst-case enumeration bounds.

Core claim

We settle the open problem of determining exact asymptotics on the volume of approximate Voronoi cells under the Gaussian heuristic. As a result, we obtain improved upper bounds on the time complexity of the randomized iterative slicer when using less than 2^{0.076d + o(d)} memory, and we show how to obtain time-memory trade-offs even when using less than 2^{0.048d + o(d)} memory. We also settle the open problem of obtaining a continuous trade-off between the size of the advice and the query time complexity, as the time complexity with subexponential advice in our approach scales as d^{d/2 + o(d)}, matching worst-case enumeration bounds.

What carries the argument

The approximate Voronoi cell construction for CVPP, whose volume is analyzed via the Gaussian heuristic to derive complexity bounds for the randomized iterative slicer.

If this is right

Improved upper bounds on time complexity of the randomized iterative slicer with memory less than 2^{0.076d + o(d)}
Time-memory trade-offs are possible even with memory less than 2^{0.048d + o(d)}
Continuous trade-off between advice size and query time complexity
With subexponential advice the query time scales as d^{d/2 + o(d)}, matching worst-case enumeration bounds

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The continuous trade-off may allow tuning preprocessing resources to specific memory constraints in applications
The matching to enumeration bounds suggests the method saturates known scaling in the subexponential-advice regime

Load-bearing premise

The Gaussian heuristic accurately predicts the volume of approximate Voronoi cells in high-dimensional lattices.

What would settle it

An exact computation or simulation of the volume of an approximate Voronoi cell for a concrete lattice in dimension 80-120 that deviates from the asymptotic formula derived under the Gaussian heuristic.

Figures

Figures reproduced from arXiv: 1907.04630 by Thijs Laarhoven.

read the original abstract

We revisit the approximate Voronoi cells approach for solving the closest vector problem with preprocessing (CVPP) on high-dimensional lattices, and settle the open problem of Doulgerakis-Laarhoven-De Weger [PQCrypto, 2019] of determining exact asymptotics on the volume of these Voronoi cells under the Gaussian heuristic. As a result, we obtain improved upper bounds on the time complexity of the randomized iterative slicer when using less than $2^{0.076d + o(d)}$ memory, and we show how to obtain time-memory trade-offs even when using less than $2^{0.048d + o(d)}$ memory. We also settle the open problem of obtaining a continuous trade-off between the size of the advice and the query time complexity, as the time complexity with subexponential advice in our approach scales as $d^{d/2 + o(d)}$, matching worst-case enumeration bounds, and achieving the same asymptotic scaling as average-case enumeration algorithms for the closest vector problem.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Laarhoven settles the 2019 open problem on exact asymptotics for approximate Voronoi cell volumes under the Gaussian heuristic and tightens the low-memory CVPP bounds.

read the letter

The main thing to know is that this paper resolves the explicit open question from Doulgerakis-Laarhoven-De Weger on the exact volume asymptotics of approximate Voronoi cells, then uses that to improve the time upper bounds for the randomized iterative slicer at memory levels below 2^{0.076d + o(d)} and even below 2^{0.048d + o(d)}. It also delivers a continuous time-memory trade-off where subexponential advice yields query time scaling as d^{d/2 + o(d)}, matching enumeration bounds. These are the concrete advances over the prior state of the art. The work stays within standard lattice techniques and the Gaussian heuristic without introducing new fitted parameters or circular reductions, which keeps the argument clean. The citation pattern is direct and the settlement of the listed open problem is stated plainly. The central limitation is the same one the abstract flags: the results are conditional on the Gaussian heuristic accurately describing the cell volumes. That assumption is common in the area, but any looseness in how it applies to the approximate cells would propagate to the claimed improvements. The o(d) terms and error analysis are not visible in the abstract, so the practical sharpness in moderate dimensions remains to be checked in the full derivations. This is for people working on CVPP algorithms, lattice crypto security estimates, or asymptotic analysis of high-dimensional lattice problems. A reader who needs updated complexity expressions for low-memory regimes or continuous trade-offs will get direct value. The paper shows clear engagement with the literature and resolves a documented gap without internal contradictions, so it merits a serious referee even if revisions are needed on the heuristic justification or concrete tightness.

Referee Report

0 major / 3 minor

Summary. The manuscript revisits approximate Voronoi cells for the closest vector problem with preprocessing (CVPP) on high-dimensional lattices. It settles the open problem of Doulgerakis-Laarhoven-De Weger by deriving exact asymptotics for the volume of these cells under the Gaussian heuristic. This yields improved upper bounds on the time complexity of the randomized iterative slicer for memory budgets below 2^{0.076d + o(d)}, time-memory trade-offs below 2^{0.048d + o(d)}, and a continuous trade-off in which subexponential advice produces query time d^{d/2 + o(d)}, matching worst-case enumeration bounds.

Significance. If the derivations hold, the work improves the best known asymptotic bounds for CVPP algorithms under the standard Gaussian heuristic and resolves two open questions in the area. The explicit, parameter-free character of the volume asymptotics (resting only on the external heuristic rather than fitted constants) and the matching of enumeration scaling are concrete strengths.

minor comments (3)

[§4] §4 (volume asymptotics): the transition from the Gaussian heuristic to the claimed exact leading-term expression should include an explicit statement of the o(·) error term and the dimension range in which the approximation is asserted to become exact.
[§5] The time-memory trade-off curves in §5 are presented only asymptotically; a short table or plot of the concrete exponents for d = 100…200 would help readers assess practical relevance.
Notation: the symbol V_approx is introduced without an immediate forward reference to its precise definition in terms of the covering radius and the number of lattice points; a one-line reminder in the introduction would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, significance assessment, and recommendation of minor revision. The report contains no enumerated major comments, so we have no specific points to address point-by-point. We are pleased that the work is viewed as settling the open problems from Doulgerakis-Laarhoven-De Weger and improving the CVPP bounds under the Gaussian heuristic.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The central claim settles an open problem by deriving exact volume asymptotics explicitly under the external Gaussian heuristic (a standard lattice assumption, not fitted or defined inside the paper). No load-bearing step reduces a prediction to a self-defined parameter, fitted input, or self-citation chain; the derivation chain remains independent of the target result. The provided abstract and context show no equations that equate outputs to inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the Gaussian heuristic as the modeling assumption for cell volumes; no free parameters or invented entities are mentioned in the abstract.

axioms (1)

domain assumption Gaussian heuristic holds for the distribution of lattice points and thus for the volume of approximate Voronoi cells
Invoked to obtain the exact asymptotics that settle the open problem.

pith-pipeline@v0.9.0 · 5704 in / 1155 out tokens · 20593 ms · 2026-05-24T23:36:20.146307+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

42 extracted references · 42 canonical work pages

[1]

362–371, 2004

Dorit Aharonov and Oded Regev, Lattice problems in NP∩ coNP, in: FOCS, pp. 362–371, 2004

work page 2004
[2]

284–293, 1997

Miklós Ajtai and Cynthia Dwork, A public-key cryptosyst em with worst- case/average-case equivalence, in: STOC, pp. 284–293, 1997

work page 1997
[3]

601–610, 2001

Miklós Ajtai, Ravi Kumar and Dandapani Sivakumar, A siev e algorithm for the shortest lattice vector problem, in: STOC, pp. 601–610, 2001

work page 2001
[4]

Albrecht, Léo Ducas, Gottfried Herold, Elena K irshanova, Eamonn Postlethwaite and Marc Stevens, The general sieve kernel an d new records in lat- tice reduction, in: EUROCRYPT, pp

Martin R. Albrecht, Léo Ducas, Gottfried Herold, Elena K irshanova, Eamonn Postlethwaite and Marc Stevens, The general sieve kernel an d new records in lat- tice reduction, in: EUROCRYPT, pp. 717–746, 2019

work page 2019
[5]

Nguyên, Random sampling revi sited: lattice enumer- ation with discrete pruning, in: EUROCRYPT, pp

Y oshinori Aono and Phong Q. Nguyên, Random sampling revi sited: lattice enumer- ation with discrete pruning, in: EUROCRYPT, pp. 65–102, 2017

work page 2017
[6]

Nguyen and Yixin Shen, Quantum l attice enumeration and tweaking discrete pruning, in: ASIACRYPT, pp

Y oshinori Aono, Phong Q. Nguyen and Yixin Shen, Quantum l attice enumeration and tweaking discrete pruning, in: ASIACRYPT, pp. 405–434, 2018

work page 2018
[7]

10–24, 2016

Anja Becker, Léo Ducas, Nicolas Gama and Thijs Laarhoven , New directions in nearest neighbor searching with applications to lattice si eving, in: SODA, pp. 10–24, 2016

work page 2016
[8]

Bernstein, Johannes Buchmann and Erik Dahmen ( eds.), Post-quantum cryptography, Springer, 2009

Daniel J. Bernstein, Johannes Buchmann and Erik Dahmen ( eds.), Post-quantum cryptography, Springer, 2009

work page 2009
[9]

Ward Beullens, Thorsten Kleinjung and Frederik V ercaut eren, CSI-FiSh: Efﬁ- cient isogeny based signatures through class group computa tions, Cryptology ePrint Archive, Report 2019/498 (2019)

work page 2019
[10]

295–314, 2015

Nicolas Bonifas and Daniel Dadush, Short paths on the Vo ronoi graph and the closest vector problem with preprocessing, in: SODA, pp. 295–314, 2015

work page 2015
[11]

98–109, 2014

Daniel Dadush, Oded Regev and Noah Stephens-Davidowit z, On the closest vector problem with a distance guarantee, in: CCC, pp. 98–109, 2014

work page 2014
[12]

Emmanouil Doulgerakis, Thijs Laarhoven and Benne de We ger, Finding closest lat- tice vectors using approximate Voronoi cells, in: PQCrypto, 2019

work page 2019
[13]

125–145, 2018

Léo Ducas, Shortest vector from lattice sieving: a few d imensions for free, in: EU- ROCRYPT, pp. 125–145, 2018

work page 2018
[14]

The European Telecommunications Standards Institute (ETSI), Quantum-Safe Cryp- tography, 2019

work page 2019
[15]

Ulrich Fincke and Michael Pohst, Improved methods for c alculating vectors of short length in a lattice, Mathematics of Computation 44 (1985), 463–471

work page 1985
[16]

Nguyên and Oded Regev, Lattice en umeration using ex- treme pruning, in: EUROCRYPT, pp

Nicolas Gama, Phong Q. Nguyên and Oded Regev, Lattice en umeration using ex- treme pruning, in: EUROCRYPT, pp. 257–278, 2010. 14 T. Laarhoven

work page 2010
[17]

170–186, 2007

Guillaume Hanrot and Damien Stehlé, Improved analysis of Kannan’s shortest lattice vector algorithm, in: CRYPTO, pp. 170–186, 2007

work page 2007
[18]

407–436, 2018

Gottfried Herold, Elena Kirshanova and Thijs Laarhove n, Speed-ups and time- memory trade-offs for tuple lattice sieving, in: PKC, pp. 407–436, 2018

work page 2018
[19]

193–206, 1983

Ravi Kannan, Improved algorithms for integer programm ing and related lattice prob- lems, in: STOC, pp. 193–206, 1983

work page 1983
[20]

3–22, 2015

Thijs Laarhoven, Sieving for shortest vectors in latti ces using angular locality- sensitive hashing, in: CRYPTO, pp. 3–22, 2015

work page 2015
[21]

523–542, 2016

Thijs Laarhoven, Sieving for closest lattice vectors ( with preprocessing), in: SAC, pp. 523–542, 2016

work page 2016
[22]

292–311, 2018

Thijs Laarhoven and Artur Mariano, Progressive lattic e sieving, in: PQCrypto, pp. 292–311, 2018

work page 2018
[23]

Thijs Laarhoven, Michele Mosca and Joop van de Pol, Find ing shortest lattice vec- tors faster using quantum search, Designs, Codes and Cryptography 77 (2015), 375– 400

work page 2015
[24]

Daniele Micciancio, The hardness of the closest vector problem with preprocessing, IEEE Transactions on Information Theory 47 (2001), 1212–1215

work page 2001
[25]

351–358, 2010

Daniele Micciancio and Panagiotis V oulgaris, A determ inistic single exponential time algorithm for most lattice problems based on Voronoi ce ll computations, in: STOC, pp. 351–358, 2010

work page 2010
[26]

1468–1480, 2010

Daniele Micciancio and Panagiotis V oulgaris, Faster e xponential time algorithms for the shortest vector problem, in: SODA, pp. 1468–1480, 2010

work page 2010
[27]

276–294, 2015

Daniele Micciancio and Michael Walter, Fast lattice po int enumeration with minimal overhead, in: SODA, pp. 276–294, 2015

work page 2015
[28]

Nguyên and Thomas Vidick, Sieve algorithms for the shortest vector prob- lem are practical, Journal of Mathematical Cryptology 2 (2008), 181–207

Phong Q. Nguyên and Thomas Vidick, Sieve algorithms for the shortest vector prob- lem are practical, Journal of Mathematical Cryptology 2 (2008), 181–207

work page 2008
[29]

The National Institute of Standards and Technology (NI ST), Post-Quantum Cryp- tography, 2017

work page 2017
[30]

685–716, 2019

Alice Pellet-Mary, Guillaume Hanrot and Damien Stehlé , Approx-SVP in ideal lat- tices with pre-processing, in: EUROCRYPT, pp. 685–716, 2019

work page 2019
[31]

Peter Pivovarov, V olume thresholds for Gaussian and sp herical random polytopes and their duals, Studia Mathematica 183 (2007), 15–34

work page 2007
[32]

thesis, 2010

Peter Pivovarov, V olume distribution and the geometry of high-dimensional r andom polytopes, Ph.D. thesis, 2010

work page 2010
[33]

84–93, 2005

Oded Regev, On lattices, learning with errors, random l inear codes, and cryptogra- phy, in: STOC, pp. 84–93, 2005. Approximate V oronoi cells for lattices, revisited 15

work page 2005
[34]

Shannon, Probability of error for optimal cod es in a Gaussian channel, Bell System Technical Journal 38 (1959), 611–656

Claude E. Shannon, Probability of error for optimal cod es in a Gaussian channel, Bell System Technical Journal 38 (1959), 611–656

work page 1959
[35]

Maria Shcherbina and Brunello Tirozzi, On the volume of the intersection of a sphere with random half spaces, Comptes Rendus Mathematique 334 (2002), 803–806

work page 2002
[36]

Shor, Algorithms for quantum computation: dis crete logarithms and factor- ing, in: FOCS, pp

Peter W. Shor, Algorithms for quantum computation: dis crete logarithms and factor- ing, in: FOCS, pp. 124–134, 1994

work page 1994
[37]

Naftali Sommer, Meir Feder and Oﬁr Shalvi, Finding the c losest lattice point by iterative slicing, SIAM Journal of Discrete Mathematics 23 (2009), 715–731

work page 2009
[38]

617–635, 2009

Damien Stehlé, Ron Steinfeld, Keisuke Tanaka and Keita Xagawa, Efﬁcient public key encryption based on ideal lattices, in: ASIACRYPT, pp. 617–635, 2009

work page 2009
[39]

Noah Stephens-Davidowitz, A time-distance trade-off for GDD with preprocessing - Instantiating the DLW heuristic, in: CCC, 2019

work page 2019
[40]

Michel Talagrand, Intersecting random half-spaces: t oward the Gardner–Derrida for- mula, The Annals of Probability 28 (2000), 725–758

work page 2000
[41]

thesis, 2019

Nicola Turchi, High-dimensional asymptotics for random polytopes , Ph.D. thesis, 2019

work page 2019
[42]

J. G. Wendel, A problem in geometric probability, Mathematica Scandinavica 11 (1962), 109–112. A The Sommer–Feder–Shalvi iterative slicer We brieﬂy describe some more details on previous, related wo rk in these appen- dices, starting with the iterative slicer of Sommer–Feder– Shalvi [37]. This algo- rithm provides an elementary, greedy strategy to attempt...

work page 1962

[1] [1]

362–371, 2004

Dorit Aharonov and Oded Regev, Lattice problems in NP∩ coNP, in: FOCS, pp. 362–371, 2004

work page 2004

[2] [2]

284–293, 1997

Miklós Ajtai and Cynthia Dwork, A public-key cryptosyst em with worst- case/average-case equivalence, in: STOC, pp. 284–293, 1997

work page 1997

[3] [3]

601–610, 2001

Miklós Ajtai, Ravi Kumar and Dandapani Sivakumar, A siev e algorithm for the shortest lattice vector problem, in: STOC, pp. 601–610, 2001

work page 2001

[4] [4]

Albrecht, Léo Ducas, Gottfried Herold, Elena K irshanova, Eamonn Postlethwaite and Marc Stevens, The general sieve kernel an d new records in lat- tice reduction, in: EUROCRYPT, pp

Martin R. Albrecht, Léo Ducas, Gottfried Herold, Elena K irshanova, Eamonn Postlethwaite and Marc Stevens, The general sieve kernel an d new records in lat- tice reduction, in: EUROCRYPT, pp. 717–746, 2019

work page 2019

[5] [5]

Nguyên, Random sampling revi sited: lattice enumer- ation with discrete pruning, in: EUROCRYPT, pp

Y oshinori Aono and Phong Q. Nguyên, Random sampling revi sited: lattice enumer- ation with discrete pruning, in: EUROCRYPT, pp. 65–102, 2017

work page 2017

[6] [6]

Nguyen and Yixin Shen, Quantum l attice enumeration and tweaking discrete pruning, in: ASIACRYPT, pp

Y oshinori Aono, Phong Q. Nguyen and Yixin Shen, Quantum l attice enumeration and tweaking discrete pruning, in: ASIACRYPT, pp. 405–434, 2018

work page 2018

[7] [7]

10–24, 2016

Anja Becker, Léo Ducas, Nicolas Gama and Thijs Laarhoven , New directions in nearest neighbor searching with applications to lattice si eving, in: SODA, pp. 10–24, 2016

work page 2016

[8] [8]

Bernstein, Johannes Buchmann and Erik Dahmen ( eds.), Post-quantum cryptography, Springer, 2009

Daniel J. Bernstein, Johannes Buchmann and Erik Dahmen ( eds.), Post-quantum cryptography, Springer, 2009

work page 2009

[9] [9]

Ward Beullens, Thorsten Kleinjung and Frederik V ercaut eren, CSI-FiSh: Efﬁ- cient isogeny based signatures through class group computa tions, Cryptology ePrint Archive, Report 2019/498 (2019)

work page 2019

[10] [10]

295–314, 2015

Nicolas Bonifas and Daniel Dadush, Short paths on the Vo ronoi graph and the closest vector problem with preprocessing, in: SODA, pp. 295–314, 2015

work page 2015

[11] [11]

98–109, 2014

Daniel Dadush, Oded Regev and Noah Stephens-Davidowit z, On the closest vector problem with a distance guarantee, in: CCC, pp. 98–109, 2014

work page 2014

[12] [12]

Emmanouil Doulgerakis, Thijs Laarhoven and Benne de We ger, Finding closest lat- tice vectors using approximate Voronoi cells, in: PQCrypto, 2019

work page 2019

[13] [13]

125–145, 2018

Léo Ducas, Shortest vector from lattice sieving: a few d imensions for free, in: EU- ROCRYPT, pp. 125–145, 2018

work page 2018

[14] [14]

The European Telecommunications Standards Institute (ETSI), Quantum-Safe Cryp- tography, 2019

work page 2019

[15] [15]

Ulrich Fincke and Michael Pohst, Improved methods for c alculating vectors of short length in a lattice, Mathematics of Computation 44 (1985), 463–471

work page 1985

[16] [16]

Nguyên and Oded Regev, Lattice en umeration using ex- treme pruning, in: EUROCRYPT, pp

Nicolas Gama, Phong Q. Nguyên and Oded Regev, Lattice en umeration using ex- treme pruning, in: EUROCRYPT, pp. 257–278, 2010. 14 T. Laarhoven

work page 2010

[17] [17]

170–186, 2007

Guillaume Hanrot and Damien Stehlé, Improved analysis of Kannan’s shortest lattice vector algorithm, in: CRYPTO, pp. 170–186, 2007

work page 2007

[18] [18]

407–436, 2018

Gottfried Herold, Elena Kirshanova and Thijs Laarhove n, Speed-ups and time- memory trade-offs for tuple lattice sieving, in: PKC, pp. 407–436, 2018

work page 2018

[19] [19]

193–206, 1983

Ravi Kannan, Improved algorithms for integer programm ing and related lattice prob- lems, in: STOC, pp. 193–206, 1983

work page 1983

[20] [20]

3–22, 2015

Thijs Laarhoven, Sieving for shortest vectors in latti ces using angular locality- sensitive hashing, in: CRYPTO, pp. 3–22, 2015

work page 2015

[21] [21]

523–542, 2016

Thijs Laarhoven, Sieving for closest lattice vectors ( with preprocessing), in: SAC, pp. 523–542, 2016

work page 2016

[22] [22]

292–311, 2018

Thijs Laarhoven and Artur Mariano, Progressive lattic e sieving, in: PQCrypto, pp. 292–311, 2018

work page 2018

[23] [23]

Thijs Laarhoven, Michele Mosca and Joop van de Pol, Find ing shortest lattice vec- tors faster using quantum search, Designs, Codes and Cryptography 77 (2015), 375– 400

work page 2015

[24] [24]

Daniele Micciancio, The hardness of the closest vector problem with preprocessing, IEEE Transactions on Information Theory 47 (2001), 1212–1215

work page 2001

[25] [25]

351–358, 2010

Daniele Micciancio and Panagiotis V oulgaris, A determ inistic single exponential time algorithm for most lattice problems based on Voronoi ce ll computations, in: STOC, pp. 351–358, 2010

work page 2010

[26] [26]

1468–1480, 2010

Daniele Micciancio and Panagiotis V oulgaris, Faster e xponential time algorithms for the shortest vector problem, in: SODA, pp. 1468–1480, 2010

work page 2010

[27] [27]

276–294, 2015

Daniele Micciancio and Michael Walter, Fast lattice po int enumeration with minimal overhead, in: SODA, pp. 276–294, 2015

work page 2015

[28] [28]

Nguyên and Thomas Vidick, Sieve algorithms for the shortest vector prob- lem are practical, Journal of Mathematical Cryptology 2 (2008), 181–207

Phong Q. Nguyên and Thomas Vidick, Sieve algorithms for the shortest vector prob- lem are practical, Journal of Mathematical Cryptology 2 (2008), 181–207

work page 2008

[29] [29]

The National Institute of Standards and Technology (NI ST), Post-Quantum Cryp- tography, 2017

work page 2017

[30] [30]

685–716, 2019

Alice Pellet-Mary, Guillaume Hanrot and Damien Stehlé , Approx-SVP in ideal lat- tices with pre-processing, in: EUROCRYPT, pp. 685–716, 2019

work page 2019

[31] [31]

Peter Pivovarov, V olume thresholds for Gaussian and sp herical random polytopes and their duals, Studia Mathematica 183 (2007), 15–34

work page 2007

[32] [32]

thesis, 2010

Peter Pivovarov, V olume distribution and the geometry of high-dimensional r andom polytopes, Ph.D. thesis, 2010

work page 2010

[33] [33]

84–93, 2005

Oded Regev, On lattices, learning with errors, random l inear codes, and cryptogra- phy, in: STOC, pp. 84–93, 2005. Approximate V oronoi cells for lattices, revisited 15

work page 2005

[34] [34]

Shannon, Probability of error for optimal cod es in a Gaussian channel, Bell System Technical Journal 38 (1959), 611–656

Claude E. Shannon, Probability of error for optimal cod es in a Gaussian channel, Bell System Technical Journal 38 (1959), 611–656

work page 1959

[35] [35]

Maria Shcherbina and Brunello Tirozzi, On the volume of the intersection of a sphere with random half spaces, Comptes Rendus Mathematique 334 (2002), 803–806

work page 2002

[36] [36]

Shor, Algorithms for quantum computation: dis crete logarithms and factor- ing, in: FOCS, pp

Peter W. Shor, Algorithms for quantum computation: dis crete logarithms and factor- ing, in: FOCS, pp. 124–134, 1994

work page 1994

[37] [37]

Naftali Sommer, Meir Feder and Oﬁr Shalvi, Finding the c losest lattice point by iterative slicing, SIAM Journal of Discrete Mathematics 23 (2009), 715–731

work page 2009

[38] [38]

617–635, 2009

Damien Stehlé, Ron Steinfeld, Keisuke Tanaka and Keita Xagawa, Efﬁcient public key encryption based on ideal lattices, in: ASIACRYPT, pp. 617–635, 2009

work page 2009

[39] [39]

Noah Stephens-Davidowitz, A time-distance trade-off for GDD with preprocessing - Instantiating the DLW heuristic, in: CCC, 2019

work page 2019

[40] [40]

Michel Talagrand, Intersecting random half-spaces: t oward the Gardner–Derrida for- mula, The Annals of Probability 28 (2000), 725–758

work page 2000

[41] [41]

thesis, 2019

Nicola Turchi, High-dimensional asymptotics for random polytopes , Ph.D. thesis, 2019

work page 2019

[42] [42]

J. G. Wendel, A problem in geometric probability, Mathematica Scandinavica 11 (1962), 109–112. A The Sommer–Feder–Shalvi iterative slicer We brieﬂy describe some more details on previous, related wo rk in these appen- dices, starting with the iterative slicer of Sommer–Feder– Shalvi [37]. This algo- rithm provides an elementary, greedy strategy to attempt...

work page 1962