2 papers
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}…
math.CO2011
On sub-determinants and the diameter of polyhedra
Nicolas Bonifas, Marco Di Summa, Friedrich Eisenbrand +2
We derive a new upper bound on the diameter of a polyhedron P = {x \in R^n : Ax <= b}, where A \in Z^{m\timesn}. The bound is polynomial in n and the largest absolute value of a su…