52 citations · 131 across the 29 of their papers we have counts for
Showing 2012Show all
2 papers · 1 filter
cs.DS2012
Lattice Sparsification and the Approximate Closest Vector Problem
Daniel Dadush, Gabor Kun
We give a deterministic algorithm for solving the (1+eps)-approximate Closest Vector Problem (CVP) on any n dimensional lattice and any norm in 2^{O(n)}(1+1/eps)^n time and 2^n pol…
cs.CC2012★ 22 cited
Near-Optimal Deterministic Algorithms for Volume Computation and Lattice Problems via M-Ellipsoids
Daniel Dadush, Santosh Vempala
We give a deterministic 2^{O(n)} algorithm for computing an M-ellipsoid of a convex body, matching a known lower bound. This has several interesting consequences including improved…