Daniel Dadush
Office: Room M234
Phone: +31 20 592 4210
Email: dadush AT cwi DOT nl
I am currently a tenured 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).
Announcements:
- I was awarded an ERC Starting grant for the project "Towards a Quantitative
Theory of Integer Programming" (see link
for the press release). I am now looking for one PhD student and one Postdoc. Please see the
official openings here: Phd
Position and Postdoc
Position. I will review applications starting November 19th, however the application process will remain open until the positions are filled.
Events:
Students and Interns:
- Ph.D.:
- Huck Bennett
(joint with Chee Yap). Graduated August 2017. Currently Postdoc @ Northwestern University.
- M.Sc.:
- Sophie Huiberts. Graduated December 2017.
- Interns:
Teaching:
- Fall 2019: Continuous Optimization.
Mastermath
website.
- Spring 2019: Geometric Functional Analysis and its Applications.
Co-Instructor: Jop Briet. Mastermath
announcement. Course webpage: link.
- Spring 2018: Introduction to Lattice Algorithms and Cryptography.
Co-Instructor: Leo Ducas. Mastermath
announcement. Course webpage: link.
- Spring 2017: Advanced Topics in Semidefinite Programming. Co-Instructor:
Nikhil Bansal. Mastermath
announcement. Course webpage: link.
- Spring 2016: Algorithms Beyond the Worst-Case. Co-Instructor: Bodo
Monthey. Mastermath
Announcement. Course webpage: link.
- Spring 2013: Lattices, Convexity and Algorithms. Co-Instructor: Oded
Regev. 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:
Conference & Journal Publications:
- On Approximating the Covering Radius and
Finding Dense Lattice Subspaces (slides) D. Dadush. STOC 2019.
- AWGN-Goodness is Enough: Capacity-Achieving Lattice Codes based on Dithered Probabilistic Shaping
A. Campello, D. Dadush, C. Long. IEEE Transactions on
Information Theory, 2018.
- Balancing Vectors in Any Norm.
D. Dadush, S. Nikolov, K. Talwar, N. Tomczak-Jaegermann. FOCS 2018.
- A Friendly Smoothed Analysis of the
Simplex Method
D. Dadush, S. Huiberts. STOC 2018 (invited to SICOMP special edition).
- The Gram-Schmidt Walk: A Cure for
the Banaszczyk Blues
N. Bansal, D. Dadush, S. Garg, S. Lovett. STOC 2018 (invited to TOC).
- Lattice based Locality Sensitive Hashing
is Optimal (extended abstract)
C. Chandrasekaran, D. Dadush, E. Grigorescu, V. Gandikota. ITCS 2018.
- Geometric Rescaling Algorithms
for Submodular Function Minimization
D. Dadush, L. Végh, G. Zambelli. SODA 2018.
- Fast, Deterministic and Sparse
Dimensionality Reduction
D. Dadush, C. Guzman, N. Olver. SODA 2018.
- Rescaling Algorithms for Linear
Conic Feasibility
D. Dadush, L. Végh, G. Zambelli. Accepted in Mathematics of Operations
Research, 2019. Preliminary version "Rescaled Coordinate
Descent Methods for Linear Programming" in IPCO 2016.
- Towards Strong Reverse Minkowski Type Inequalities for Lattices
D. Dadush, O. Regev. FOCS 2016.
- An Algorithm for the Komlós Conjecture Matching Banaszczyk's Bound
N. Bansal, D. Dadush, S. Garg. FOCS 2016.
- Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem
D. Dadush, S. Garg, S. Lovett, A. Nikolov. 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.
- Unconditional Differentially Private
Mechanisms for Linear Queries
A. Bhaskara, D. Dadush, R. Krishnaswamy, K. Talwar. STOC 2012.
- 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.
PhD Thesis: