Daniel Dadush

Office: Room M234
Phone: +31 20 592 4210
Email: dadush AT cwi DOT nl

Events:

• I co-organized the Dutch Day on Optimization on Thursday October 13th, 2022 at CWI. Please visit the event website for more information.
• I co-organized a reading group on Learning Augmented Algorithms (Spring 2022). Please visit the reading group website for more information.
• I co-organized a Hausdorff Research Institute for Mathematics (HIM) Trimester on "Discrete Optimization" in Bonn during the Fall of 2021.
• I co-organized the workshop Lattices: Geometry, Algorithms and Hardness at the Simons Institute, Feb 18-21, 2020.
• I was on the committee of the Mixed Integer Programming (MIP 2019) workshop at MIT, July 11-15, 2019.
• I organized a workshop on Discrepancy Theory and Integer Programming, June 11-15 at CWI. Slides for the talks are available on the website.

N&O Optimization Seminar:

Dutch Seminar on Optimization:

Students and Interns:

• Ph.D.:
  • Samarth Tiwari.
  • Sander Borst. Graduated August 2024. (Postdoc, Max Plank Institute, Saarbrucken)
  • Sophie Huiberts. Graduated May 2022. (CNRS Researcher @ LIMOS, Clermont Auvergne University).
  • Huck Bennett (joint with Chee Yap). Graduated August 2017. (Assistant Professor, Oregon State University).
• M.Sc.:
  • Sophie Huiberts. Graduated December 2017.
• Interns:
  • Huck Bennett . Fall 2016. (Assistant Professor, University of Boulder)
  • Venkata Gandikota . Fall 2016. (Assistant Professor, University of Syracuse)

Teaching:

• Fall 2024: Continuous Optimization. Mastermath website.
• Fall 2022: Continuous Optimization. Mastermath website.
• 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 Manthey.
• Spring 2013: Lattices, Convexity and Algorithms. Co-Instructor: Oded Regev. New York University (graduate: CSCI-GA 3033-013).

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:

• ERC Starting Grant: Towards a Quantitative Theory of Integer Programming, 2019-2024. project website.
• NWO Veni Grant: New Frontiers in Lattice Algorithms and Design, 2015 - 2018.

Research Awards:

• Netherlands Society for Statistics and Operations Research Van Dantzig Prize, 2020.
• 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.

Program Committees:

Research Publications:

Surveys and Book Chapters:

1. Smoothed Analysis of the Simplex Method
   with S. Huiberts. Invited chapter in Beyond Worst Case Analysis (editor Tim Roughgarden), December 2020.

Conference & Journal Publications:

1. A Strongly Polynomial Algorithm for Linear Programs with at most Two Non-zero Entries per Row or Column.
   with Z.K. Koh, B. Natura, N. Olver, L. Végh. STOC 2024.
2. Strongly Polynomial Frame Scaling to High Precision
   with A. Ramachandran. SODA 2024.
3. From Approximate to Exact Integer Programming
   with F. Eisenbrand, T. Rothvoss. IPCO 2023 (Best paper award).
4. A Nearly Optimal Randomized Algorithm for Explorable Heap Selection
   with S. Borst, D. Dadush, D. Kashaev, S. Huiberts. IPCO 2023.
5. Optimizing Low Dimensional Functions over the Integers
   with A. Leonard, L. Rohwedder, J. Verschae. IPCO 2023.
6. Integrality Gaps for Random Integer Programs via Discrepancy
   with S. Borst, D. Mikulincer. SODA 2023.
7. Interior Point Methods are not worse than Simplex
   with X. Allamigeon, G. Loho, B. Natura, L. Végh. FOCS 2022.
8. A New Framework for Matrix Discrepancy: Partial Coloring Bounds via Mirror Descent
   with H. Jiang, V. Reis. STOC 2022.
9. On Circuit Diameter Bounds via Circuit Imbalances
   with Z.K. Koh, B. Natura, L. Végh. IPCO 2022.
10. A Simple Method for Convex Optimization in the Oracle Model
    with C. Hojny, S. Huiberts, S. Weltge. Mathematical Programming, 2023.
    Preliminary version in IPCO 2022.
11. Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes
    with G. Bonnet, U. Grupel, S. Huiberts, G. Livshyts. SOCG 2022.
12. On Finding Exact Solutions of Linear Programs in the Oracle Model
    with L. Végh, G. Zambelli. SODA 2022.
13. An Accelerated Newton-Dinkelbach Method and its Application to Two Variables Per Inequality Systems
    with Z.K. Koh, B. Natura, L. Végh. Mathematics of Operations Research, 2022.
    Preliminary version in ESA 2021.
14. On the Integrality Gap of Binary Integer Programs with Gaussian Data
    with S. Borst, S. Huiberts, S. Tiwari. Mathematical Programming, 2023.
    Preliminary version in IPCO 2021.
15. Majorizing Measures for the Optimizers
    with S. Borst, N. Olver, M. Sinha. ITCS 2021.
16. Revisiting Tardos' Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers
    B. Natura, L. Végh. FOCS 2020.
17. On the Complexity of Branching Proofs
    with S. Tiwari. CCC 2020 (Best paper award).
18. A Scaling-Invariant Algorithm for Linear Programming whose Running Time Depends only on the Constraint Matrix
    with S. Huiberts, B. Natura, L. Végh. Mathematical Programming, 2023.
    Preliminary version in STOC 2020.
19. On Approximating the Covering Radius and Finding Dense Lattice Subspaces (slides)
    STOC 2019.
20. AWGN-Goodness is Enough: Capacity-Achieving Lattice Codes based on Dithered Probabilistic Shaping
    with A. Campello, C. Long. IEEE Transactions on Information Theory, 2019.
21. Balancing Vectors in Any Norm
    with S. Nikolov, K. Talwar, N. Tomczak-Jaegermann. FOCS 2018.
22. A Friendly Smoothed Analysis of the Simplex Method
    with S. Huiberts. SIAM Journal on Computing, 2020.
    Special edition for STOC 2018.
23. The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues
    with N. Bansal, S. Garg, S. Lovett. Theory of Computing, 2019.
    Preliminary version in STOC 2018.
24. Lattice based Locality Sensitive Hashing is Optimal (extended abstract)
    with C. Chandrasekaran, E. Grigorescu, V. Gandikota. ITCS 2018.
25. Geometric Rescaling Algorithms for Submodular Function Minimization
    with L. Végh, G. Zambelli. Mathematics of Operations Research, 2021.
    Preliminary version in SODA 2018.
26. Fast, Deterministic and Sparse Dimensionality Reduction
    with C. Guzman, N. Olver. SODA 2018.
27. Rescaling Algorithms for Linear Conic Feasibility
    with L. Végh, G. Zambelli. Mathematics of Operations Research, 2020.
28. Towards Strong Reverse Minkowski Type Inequalities for Lattices
    with O. Regev. FOCS 2016.
29. An Algorithm for the Komlós Conjecture Matching Banaszczyk's Bound
    with N. Bansal, S. Garg. SIAM Journal of Computing, 2019.
    Special edition for FOCS 2016.
30. Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem
    with S. Garg, S. Lovett, A. Nikolov. Theory of Computing, 2019.
    Special edition for APPROX-RANDOM 2016.
31. On the Lattice Distortion Problem
    with H. Bennett, N. Stephens-Davidowitz. ESA 2016.
32. Rescaled Coordinate Descent Methods for Linear Programming
    with L. Végh, G. Zambelli. IPCO 2016.
33. Solving the Closest Vector Problem in 2^n Time: The Discrete Gaussian Strikes Again! (slides)
    with D. Aggarwal, N. Stephens-Davidowitz. FOCS 2015.
34. Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian Sampling (slides)
    with D. Aggarwal, O. Regev, N. Stephens-Davidowitz. STOC 2015.
35. Faster Deterministic Volume Estimation in the Oracle Model via Thin Lattice Coverings (slides)
    SOCG 2015.
36. On the Shadow Simplex Method for Curved Polyhedra (slides)
    with N. Hähnle. Discrete & Computational Geometry, 2016.
    Preliminary version in SOCG 2015.
37. Short Paths on the Voronoi Graph and the Closest Vector Problem with Preprocessing (slides)
    with N. Bonifas. SODA 2015.
38. On the Closest Vector Problem with a Distance Guarantee
    with O. Regev, N. Stephens-Davidowitz. CCC 2014.
39. On the existence of 0/1 polytopes with High Semidefinite Extension Complexity (slides)
    with J. Briet, S. Pokutta. Mathematical Programming, 2015.
    Preliminary version in ESA 2013.
40. On the Lattice Smoothing Parameter Problem (slides)
    with K.M. Chung, F.H. Liu, C. Peikert. CCC 2013.
41. Lattice Sparsification and the Approximate Closest Vector Problem (slides)
    with G. Kun. Theory of Computing, 2016.
    Preliminary version in SODA 2013.
42. Algorithms for the Densest Sublattice Problem
    with D. Micciancio. SODA 2013.
43. Near-Optimal Deterministic Algorithms for Volume Computation via M-Ellipsoids (slides)
    with S. Vempala. Proceedings of the National Academy of Sciences, 2013.
44. Unconditional Differentially Private Mechanisms for Linear Queries
    with A. Bhaskara, R. Krishnaswamy, K. Talwar. STOC 2012.
45. A Randomized Sieving Algorithm for Approximate Integer Programming (slides)
    Algorithmica, 2014.
    Preliminary version in LATIN 2012.
46. Deterministic Construction of an Approximate M-Ellipsoid and its Applications to Derandomizing Lattice Algorithms
    with S. Vempala. SODA 2012.
47. On the Chvátal-Gomory Closure of a Compact Convex Set (slides)
    with S.S. Dey, J.P. Vielma. Mathematical Programming, 2014.
    Preliminary version in IPCO 2011.
    Optimization Society Student Paper Prize, 2011.
48. The Split Closure of a Strictly Convex Body
    with S.S. Dey, J.P. Vielma. Operations Research Letters, 2011.
49. The Chvátal-Gomory Closure of a Strictly Convex Body
    with S.S. Dey, J.P. Vielma. Mathematics of Operations Research, 2011.
    INFORMS JFIG Paper Competition Finalist.
50. Enumerative Lattice Algorithms in Any Norm via M-Ellipsoid Coverings (slides)
    with C. Peikert, S. Vempala. FOCS 2011.
51. Thin Partitions: Isoperimetric Inequalities and a Sampling Algorithm for Star Shaped Bodies
    with C. Chandresekaran, S. Vempala. SODA 2010.

PhD Thesis:

• Integer Programming, Lattice Algorithms, and Deterministic Volume Estimation