52 citations · 131 across the 29 of their papers we have counts for
Showing 2014 · cs.DSShow all
3 papers · 2 filters
cs.DS2014
On the Shadow Simplex Method for Curved Polyhedra
Daniel Dadush, Nicolai Hähnle
We study the simplex method over polyhedra satisfying certain "discrete curvature" lower bounds, which enforce that the boundary always meets vertices at sharp angles. Motivated by…
cs.DS2014
Short Paths on the Voronoi Graph and the Closest Vector Problem with Preprocessing
Nicolas Bonifas, Daniel Dadush
Improving on the Voronoi cell based techniques of Micciancio and Voulgaris (SIAM J. Comp. 13), and Sommer, Feder and Shalvi (SIAM J. Disc. Math. 09), we give a Las Vegas $\tilde{O}…
cs.DS2014★ 11 cited
On the Closest Vector Problem with a Distance Guarantee
Daniel Dadush, Oded Regev, Noah Stephens-Davidowitz
We present a substantially more efficient variant, both in terms of running time and size of preprocessing advice, of the algorithm by Liu, Lyubashevsky, and Micciancio for solving…