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).

Events:

I am jointly organizing a workshop on Discrepancy Theory and Integer Programming, June 11-15 at CWI. Space is very limited so register early!

Students and Interns:

Teaching:

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:

Research Grants:

Research Awards:

Research Publications:

Preprints:

  1. On Approximating the Covering Radius and Finding Dense Lattice Subspaces (slides)
    D. Dadush. Manuscript, 2017.
  2. AWGN-Goodness is Enough: Capacity-Achieving Lattice Codes based on Dithered Probabilistic Shaping
    A. Campello, D. Dadush. Manuscript, 2017.

Conference & Journal Publications:

  1. A Friendly Smoothed Analysis of the Simplex Method
    D. Dadush, S. Huiberts. To appear in STOC 2018.
  2. The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues
    N. Bansal, D. Dadush, S. Garg, S. Lovett. To appear in STOC 2018.
  3. Lattice based Locality Sensitive Hashing is Optimal (extended abstract)
    C. Chandrasekaran, D. Dadush, E. Grigorescu, V. Gandikota. ITCS 2018.
  4. Geometric Rescaling Algorithms for Submodular Function Minimization
    D. Dadush, L. Végh, G. Zambelli. SODA 2018.
  5. Fast, Deterministic and Sparse Dimensionality Reduction (extended abstract)
    D. Dadush, C. Guzman, N. Olver. SODA 2018.
  6. Rescaling Algorithms for Linear Programming - Part I: Conic feasibility
    D. Dadush, L. Végh, G. Zambelli. Preliminary version "Rescaled Coordinate Descent Methods for Linear Programming" in IPCO 2016.
  7. Towards Strong Reverse Minkowski Type Inequalities for Lattices
    D. Dadush, O. Regev. FOCS 2016.
  8. An Algorithm for the Komlós Conjecture Matching Banaszczyk's Bound
    N. Bansal, D. Dadush, S. Garg. FOCS 2016.
  9. Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem
    D. Dadush, S. Garg, S. Lovett, A. Nikolov. RANDOM 2016.
  10. On the Lattice Distortion Problem
    H. Bennett, D. Dadush, N. Stephens-Davidowitz. ESA 2016.
  11. Solving the Closest Vector Problem in 2^n Time: The Discrete Gaussian Strikes Again! (slides)
    D. Aggarwal, D. Dadush, N. Stephens-Davidowitz. FOCS 2015.
  12. 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.
  13. Faster Deterministic Volume Estimation in the Oracle Model via Thin Lattice Coverings (slides)
    D. Dadush. SOCG 2015.
  14. 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.
  15. Short Paths on the Voronoi Graph and the Closest Vector Problem with Preprocessing (slides)
    N. Bonifas, D. Dadush. SODA 2015.
  16. On the Closest Vector Problem with a Distance Guarantee
    D. Dadush, O. Regev, N. Stephens-Davidowitz. CCC 2014.
  17. 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.
  18. On the Lattice Smoothing Parameter Problem (slides)
    K.M. Chung, D. Dadush, F.H. Liu, C. Peikert. CCC 2013.
  19. 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.
  20. Algorithms for the Densest Sublattice Problem
    D. Dadush, D. Micciancio. SODA 2013
  21. 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.
  22. Unconditional Differentially Private Mechanisms for Linear Queries
    A. Bhaskara, D. Dadush, R. Krishnaswamy, K. Talwar. STOC 2012.
  23. A Randomized Sieving Algorithm for Approximate Integer Programming (slides)
    D. Dadush. Algorithmica, 70, 208-244, 2014.
    Preliminary version in LATIN 2012.
  24. Deterministic Construction of an Approximate M-Ellipsoid and its Applications to Derandomizing Lattice Algorithms
    D. Dadush, S. Vempala. SODA 2012.
  25. 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.
  26. 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.
  27. 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.
  28. Enumerative Lattice Algorithms in Any Norm via M-Ellipsoid Coverings (slides)
    D. Dadush, C. Peikert, S. Vempala. FOCS 2011.
  29. Thin Partitions: Isoperimetric Inequalities and a Sampling Algorithm for Star Shaped Bodies
    D. Dadush, C. Chandresekaran, S. Vempala. SODA 2010.

PhD Thesis: