Daniel Dadush
Office: Room M234
Phone: +31 20 592 4210
Email: dadush AT cwi DOT nl
I am the leader of the Networks &
Optimization group, and a full professor at Utrecht University in the department of Mathematics. 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.
Events:
N&O Optimization Seminar:
Please visit the seminar website
for information about the current schedule and past talks.
Dutch Seminar on Optimization:
I am a co-organizer for the (online) Dutch Seminar on Optimization. Please see the seminar website for more information. If you'd like to join the seminar mailing list, please email Cedric Koh (zhuan.koh@cwi.nl).
Students and Interns:
- Ph.D.:
- 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).
Here's my curriculum vitae (CV) (last updated September 2024).
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:
SODA 2024, FOCS 2022, SODA 2022, ESA 2020, IPCO 2020, MIP 2019, SODA 2019,
IPCO 2017, ESA 2014.
Research Publications:
Surveys and Book Chapters:
- Smoothed Analysis of the Simplex Method
with S. Huiberts. Invited chapter in Beyond Worst Case Analysis (editor
Tim Roughgarden), December 2020.
Conference & Journal Publications:
- 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.
- Strongly Polynomial Frame Scaling to High Precision
with A. Ramachandran. SODA 2024.
- From Approximate to Exact Integer Programming
with F. Eisenbrand, T. Rothvoss. IPCO 2023 (Best paper award).
- From Approximate to Exact Integer Programming
with F. Eisenbrand, T. Rothvoss. IPCO 2023 (Best paper award).
- A Nearly Optimal Randomized Algorithm for Explorable Heap Selection
with S. Borst, D. Dadush, D. Kashaev, S. Huiberts. IPCO 2023.
- Optimizing Low Dimensional Functions over the Integers
with A. Leonard, L. Rohwedder, J. Verschae. IPCO 2023.
- Integrality Gaps for Random Integer Programs
via Discrepancy with S. Borst, D. Mikulincer. SODA 2023.
- Interior Point Methods are not worse than Simplex with X. Allamigeon, G. Loho, B. Natura, L. Végh. FOCS 2022.
- A New Framework for Matrix Discrepancy: Partial Coloring
Bounds via Mirror Descent with H. Jiang, V. Reis. STOC 2022.
- On Circuit Diameter Bounds via Circuit Imbalances with Z.K. Koh, B.
Natura, L. Végh. IPCO 2022.
- 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.
- Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes
with G. Bonnet, U. Grupel, S. Huiberts, G. Livshyts. SOCG 2022.
- On Finding Exact Solutions of Linear Programs in the Oracle Model
with L. Végh, G. Zambelli. SODA 2022.
- 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.
- 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.
- Majorizing Measures for the Optimizers
with S. Borst, N. Olver, M. Sinha. ITCS 2021.
- Revisiting Tardos' Framework for Linear Programming: Faster Exact Solutions
using Approximate Solvers
B. Natura, L. Végh. FOCS 2020.
- On the Complexity of Branching Proofs
with S. Tiwari. CCC 2020 (Best paper award).
- 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.
- On Approximating the Covering Radius and
Finding Dense Lattice Subspaces (slides) STOC 2019.
- AWGN-Goodness is Enough: Capacity-Achieving Lattice Codes based on Dithered Probabilistic Shaping
with A. Campello, C. Long. IEEE Transactions on
Information Theory, 2019.
- Balancing Vectors in Any Norm
with S. Nikolov, K. Talwar, N. Tomczak-Jaegermann. FOCS 2018.
- A Friendly Smoothed Analysis of the
Simplex Method
with S. Huiberts. SIAM Journal on Computing, 2020.
Special edition for STOC 2018.
- 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.
- Lattice based Locality Sensitive Hashing
is Optimal (extended abstract)
with C. Chandrasekaran, E. Grigorescu, V. Gandikota. ITCS 2018.
- Geometric Rescaling Algorithms
for Submodular Function Minimization
with L. Végh, G. Zambelli. Mathematics of Operations
Research, 2021.
Preliminary version in SODA 2018.
- Fast, Deterministic and Sparse
Dimensionality Reduction
with C. Guzman, N. Olver. SODA 2018.
- Rescaling Algorithms for Linear
Conic Feasibility
with L. Végh, G. Zambelli. Mathematics of Operations Research, 2020.
- Towards Strong Reverse Minkowski Type Inequalities for Lattices
with O. Regev. FOCS 2016.
- 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.
- 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.
- On the Lattice Distortion Problem
with H. Bennett, N. Stephens-Davidowitz. ESA 2016.
- Rescaled Coordinate Descent Methods for Linear Programming
with L. Végh, G. Zambelli. IPCO 2016.
- Solving the Closest Vector Problem
in 2^n Time: The Discrete Gaussian Strikes Again! (slides)
with D. Aggarwal, N. Stephens-Davidowitz. FOCS 2015.
- Solving the Shortest Vector Problem
in 2^n Time via Discrete Gaussian Sampling (slides)
with D. Aggarwal, O.
Regev, N. Stephens-Davidowitz. STOC 2015.
- Faster Deterministic Volume Estimation in
the Oracle Model via Thin Lattice Coverings (slides)
SOCG 2015.
- On the Shadow Simplex Method for Curved
Polyhedra (slides)
with N. Hähnle. Discrete & Computational Geometry, 2016.
Preliminary version in SOCG 2015.
- Short Paths on the Voronoi Graph and the Closest
Vector Problem with Preprocessing (slides)
with N. Bonifas. SODA 2015.
- On the Closest Vector Problem with
a Distance Guarantee
with O. Regev, N. Stephens-Davidowitz. CCC 2014.
- 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.
- On the Lattice Smoothing Parameter
Problem (slides)
with K.M. Chung, F.H. Liu, C. Peikert. CCC 2013.
- Lattice Sparsification and the
Approximate Closest Vector Problem (slides)
with G. Kun. Theory of Computing, 2016.
Preliminary version in SODA 2013.
- Algorithms for the Densest Sublattice
Problem
with D. Micciancio. SODA 2013.
- Near-Optimal Deterministic Algorithms
for Volume Computation via M-Ellipsoids (slides)
with S. Vempala.
Proceedings of the National Academy of Sciences, 2013.
- Unconditional Differentially Private
Mechanisms for Linear Queries
with A. Bhaskara, R. Krishnaswamy, K. Talwar. STOC 2012.
- A Randomized Sieving Algorithm for Approximate Integer Programming
(slides)
Algorithmica, 2014.
Preliminary version in LATIN 2012.
- Deterministic Construction of an Approximate M-Ellipsoid and its
Applications to Derandomizing Lattice Algorithms
with S. Vempala. SODA 2012.
- 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.
- The Split Closure of a Strictly Convex Body
with S.S. Dey, J.P. Vielma. Operations Research Letters, 2011.
- 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.
- Enumerative Lattice Algorithms in Any
Norm via M-Ellipsoid Coverings (slides)
with C. Peikert, S. Vempala. FOCS 2011.
- Thin Partitions: Isoperimetric Inequalities and a Sampling Algorithm for Star Shaped Bodies
with C. Chandresekaran, S. Vempala. SODA 2010.
PhD Thesis: