52 citations · 131 across the 29 of their papers we have counts for
6 papers · 1 filter
On the Complexity of Branching Proofs
Daniel Dadush, Samarth Tiwari
We consider the task of proving integer infeasibility of a bounded convex in using a general branching proof system. In a general branching proof, one constructs…
On the Lattice Smoothing Parameter Problem
Kai-Min Chung, Daniel Dadush, Feng-Hao Liu +1
The smoothing parameter of a Euclidean lattice , introduced by Micciancio and Regev (FOCS'04; SICOMP'07), is (informally) the smallest amount of Gau…
A Deterministic Polynomial Space Construction for eps-nets under any Norm
Daniel Dadush
We give a deterministic polynomial space construction for nearly optimal eps-nets with respect to any input n-dimensional convex body K and norm |.|. More precisely, our algorithm…
On the existence of 0/1 polytopes with high semidefinite extension complexity
Jop Briët, Daniel Dadush, Sebastian Pokutta
In Rothvoß it was shown that there exists a 0/1 polytope (a polytope whose vertices are in \{0,1\}^{n}) such that any higher-dimensional polytope projecting to it must have 2^{Ω(n)…
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…
Deterministic Construction of an Approximate M-Ellipsoid and its Application to Derandomizing Lattice Algorithms
Daniel Dadush, Santosh Vempala
We give a deterministic O(log n)^n algorithm for the {\em Shortest Vector Problem (SVP)} of a lattice under {\em any} norm, improving on the previous best deterministic bound of n^…