Daniel Dadush
Office: Room M234
Phone: +31 20 592 4210
Email: dadush AT cwi DOT nl
I am currently a tenure track researcher at CWI
in the Networks & Optimization group. Previously, I was a
Simons
Postdoctoral Fellow for 2 years at the
Courant Institute of Mathematical Sciences at New York
University. I completed my PhD in 2012 within the ACO (Algorithms, Combinatorics, and
Optimization) program at Georgia Tech under Santosh Vempala
(Professor of Computer Science).
Teaching:
- Spring 2016: Algorithms Beyond the Worst-Case (link) (joint with Bodo Manthey, University
of Twente). Course webpage: link.
- Spring 2013: Lattices, Convexity and Algorithms @ New York University (graduate: CSCI-GA 3033-013)
N&O Optimization Seminar:
I am the organizer for the Networks & Optimization Seminar at CWI.
Please visit the seminar website for the
current schedule.
Feel free to drop me a line if you would like to give a talk.
Here's my curriculum vitae (CV).
Research Interests:
- Lattice Algorithms and the Geometry of Numbers
- Linear Programming and the Simplex Method
- Extended Formulations
- Algorithms for Integer Programming, Cutting Plane Methods
- Convex Optimization
- Asymptotic Convex Geometry
(properties of convex bodies as dimension tends to infinity)
Research Grants:
- NWO Veni Grant: New Frontiers in Lattice Algorithms and Design, 2015 - 2018.
Research Awards:
- A.W. Tucker Prize for Best Thesis in Mathematical Optimization, 2015.
Citation: link.
- Informs Optimization Society Student Paper Prize, 2011.
- Informs JFIG Paper Competition, Finalist, 2010 & 2011.
Research Publications:
- Towards Strong Reverse Minkowski Type Inequalities for Lattices
D. Dadush, O. Regev. To appear in FOCS 2016.
- An Algorithm for the Komlós Conjecture Matching Banaszczyk's Bound
N. Bansal, D. Dadush, S. Garg. To appear in FOCS 2016.
- Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem
D. Dadush, S. Garg, S. Lovett, A. Nikolov. To appear in RANDOM 2016.
- On the Lattice Distortion Problem
H. Bennett, D. Dadush, N. Stephens-Davidowitz. ESA 2016.
- Solving the Closest Vector Problem
in 2^n Time: The Discrete Gaussian Strikes Again! (slides)
D. Aggarwal, D. Dadush, N. Stephens-Davidowitz. FOCS 2015.
- Solving the Shortest Vector Problem
in 2^n Time via Discrete Gaussian Sampling (slides)
D. Aggarwal, D. Dadush, O.
Regev, N. Stephens-Davidowitz. STOC 2015.
- Faster Deterministic Volume Estimation in
the Oracle Model via Thin Lattice Coverings (slides)
D. Dadush. SOCG 2015.
- On the Shadow Simplex Method for Curved
Polyhedra (slides)
D. Dadush, N. Hähnle. Discrete & Computational Geometry, 1-28, 2016.
Preliminary version in SOCG 2015.
- Short Paths on the Voronoi Graph and the Closest
Vector Problem with Preprocessing (slides)
N. Bonifas, D. Dadush. SODA 2015.
- On the Closest Vector Problem with
a Distance Guarantee
D. Dadush, O. Regev, N. Stephens-Davidowitz. CCC 2014.
- On the existence of 0/1 polytopes with
High Semidefinite Extension Complexity (slides)
J. Briet, D. Dadush, S.
Pokutta. Mathematical Programming, Series B, 153, 179-199, 2015.
Preliminary version in ESA 2013.
- On the Lattice Smoothing Parameter
Problem (slides)
K.M. Chung, D. Dadush, F.H. Liu, C. Peikert. CCC 2013.
- Lattice Sparsification and the
Approximate Closest Vector Problem (slides)
D. Dadush, G. Kun. Theory of Computing, 12, 1-34, 2016. Preliminary version in SODA 2013.
- Algorithms for the Densest Sublattice Problem
D. Dadush, D. Micciancio. SODA 2013
- Near-Optimal Deterministic Algorithms
for Volume Computation via M-Ellipsoids (slides)
D. Dadush, S. Vempala.
Proceedings of the National Academy of Sciences, 110, 19237-19245, 2013.
- A Randomized Sieving Algorithm for Approximate Integer Programming
(slides)
D. Dadush. Algorithmica, 70, 208–244, 2014.
Preliminary version in LATIN 2012.
- Deterministic Construction of an Approximate M-Ellipsoid and its
Applications to Derandomizing Lattice Algorithms
D. Dadush, S. Vempala. SODA 2012.
- On the Chvátal-Gomory Closure of a
Compact Convex Set (slides)
D. Dadush, S.S. Dey, J.P. Vielma. Mathematical Programming, Series B, 145, 1, 327-348, 2014.
Preliminary version in IPCO 2011.
Optimization Society Student Paper Prize, 2011.
- The Split Closure of a Strictly Convex Body
D. Dadush, S.S. Dey, J.P. Vielma. Operations Research Letters, vol. 39, p. 121-126, 2011.
- The Chvátal-Gomory Closure of a Strictly Convex Body
D. Dadush, S.S. Dey, J.P. Vielma. Mathematics of Operations Research, vol. 36, p. 227-239, 2011.
INFORMS JFIG Paper Competition Finalist.
- Enumerative Lattice Algorithms in Any
Norm via M-Ellipsoid Coverings (slides)
D. Dadush, C. Peikert, S. Vempala. FOCS 2011.
- Thin Partitions: Isoperimetric Inequalities and a Sampling Algorithm for Star Shaped Bodies
D. Dadush, C. Chandresekaran, S. Vempala. SODA 2010.
