Daniel Dadush

Martin Milanic

Tami Tamir

ACM Trans. Algorithms, July, 2024

A Strongly Polynomial Algorithm for Linear Programs with At Most Two Nonzero Entries per Row or Column.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Strongly Polynomial Frame Scaling to High Precision.

[BibT_eX]

[DOI]

Akshay Ramachandran

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

Integrality Gaps for Random Integer Programs via Discrepancy.

[BibT_eX]

[DOI]

Sander Borst

Dan Mikulincer

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Optimizing Low Dimensional Functions over the Integers.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2023

From Approximate to Exact Integer Programming.

[BibT_eX]

[DOI]

Friedrich Eisenbrand

Thomas Rothvoss

Proceedings of the Integer Programming and Combinatorial Optimization, 2023

A Nearly Optimal Randomized Algorithm for Explorable Heap Selection.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2023

2022

A new framework for matrix discrepancy: partial coloring bounds via mirror descent.

[BibT_eX]

[DOI]

Haotian Jiang

Victor Reis

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

On finding exact solutions of linear programs in the oracle model.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

On Circuit Diameter Bounds via Circuit Imbalances.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2022

A Simple Method for Convex Optimization in the Oracle Model.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2022

Interior point methods are not worse than Simplex.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes.

[BibT_eX]

[DOI]

Proceedings of the 38th International Symposium on Computational Geometry, 2022

2021

On the Integrality Gap of Binary Integer Programs with Gaussian Data.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2021

Majorizing Measures for the Optimizer.

[BibT_eX]

[DOI]

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

An Accelerated Newton-Dinkelbach Method and Its Application to Two Variables per Inequality Systems.

[BibT_eX]

[DOI]

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

2020

Rescaling Algorithms for Linear Conic Feasibility.

[BibT_eX]

[DOI]

Math. Oper. Res., 2020

Simple Iterative Methods for Linear Optimization over Convex Sets.

[BibT_eX]

[DOI]

CoRR, 2020

A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers.

[BibT_eX]

[DOI]

Bento Natura

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

On the Complexity of Branching Proofs.

[BibT_eX]

[DOI]

Samarth Tiwari

Proceedings of the 35th Computational Complexity Conference, 2020

Smoothed Analysis of the Simplex Method.

[BibT_eX]

[DOI]

Sophie Huiberts

Proceedings of the Beyond the Worst-Case Analysis of Algorithms, 2020

2019

AWGN-Goodness Is Enough: Capacity-Achieving Lattice Codes Based on Dithered Probabilistic Shaping.

[BibT_eX]

[DOI]

Antonio Campello

Cong Ling

IEEE Trans. Inf. Theory, 2019

On approximating the covering radius and finding dense lattice subspaces.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

2018

A friendly smoothed analysis of the simplex method.

[BibT_eX]

[DOI]

Sophie Huiberts

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

The gram-schmidt walk: a cure for the Banaszczyk blues.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Geometric Rescaling Algorithms for Submodular Function Minimization.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Fast, Deterministic and Sparse Dimensionality Reduction.

[BibT_eX]

[DOI]

Karthekeyan Chandrasekaran

Cristóbal Guzmán

Neil Olver

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Lattice-based Locality Sensitive Hashing is Optimal.

[BibT_eX]

[DOI]

Venkata Gandikota

Elena Grigorescu

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Balancing Vectors in Any Norm.

[BibT_eX]

[DOI]

Nicole Tomczak-Jaegermann

Aleksandar Nikolov

Kunal Talwar

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

AWGN-Goodness is Enough: Capacity-Achieving Lattice Codes based on Dithered Probabilistic Shaping.

[BibT_eX]

[DOI]

Antonio Campello

CoRR, 2017

2016

Rescaling Algorithms for Linear Programming - Part I: Conic feasibility.

[BibT_eX]

[DOI]

CoRR, 2016

Rescaled Coordinate Descent Methods for Linear Programming.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2016

Towards Strong Reverse Minkowski-Type Inequalities for Lattices.

[BibT_eX]

[DOI]

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound.

[BibT_eX]

[DOI]

Nikhil Bansal

Shashwat Garg

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

On the Lattice Distortion Problem.

[BibT_eX]

[DOI]

Huck Bennett

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2016

2015

Solving the Shortest Vector Problem in 2<sup>n</sup> Time Using Discrete Gaussian Sampling: Extended Abstract.

[BibT_eX]

[DOI]

Divesh Aggarwal

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Short Paths on the Voronoi Graph and Closest Vector Problem with Preprocessing.

[BibT_eX]

[DOI]

Nicolas Bonifas

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Solving the Closest Vector Problem in 2^n Time - The Discrete Gaussian Strikes Again!

[BibT_eX]

[DOI]

Divesh Aggarwal

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

On the Shadow Simplex Method for Curved Polyhedra.

[BibT_eX]

[DOI]

Nicolai Hähnle

Proceedings of the 31st International Symposium on Computational Geometry, 2015

Faster Deterministic Volume Estimation in the Oracle Model via Thin Lattice Coverings.

[BibT_eX]

[DOI]

Proceedings of the 31st International Symposium on Computational Geometry, 2015

2014

Solving the Shortest Vector Problem in $2^n$ Time via Discrete Gaussian Sampling.

[BibT_eX]

[DOI]

Divesh Aggarwal

CoRR, 2014

A Randomized Sieving Algorithm for Approximate Integer Programming.

[BibT_eX]

[DOI]

Algorithmica, 2014

On the Closest Vector Problem with a Distance Guarantee.

[BibT_eX]

[DOI]

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013

Near-optimal deterministic algorithms for volume computation via M-ellipsoids.

[BibT_eX]

[DOI]

Proc. Natl. Acad. Sci. USA, 2013

A Deterministic Polynomial Space Construction for eps-nets under any Norm.

[BibT_eX]

[DOI]

CoRR, 2013

Algorithms for the Densest Sub-Lattice Problem.

[BibT_eX]

[DOI]

Daniele Micciancio

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Lattice Sparsification and the Approximate Closest Vector Problem.

[BibT_eX]

[DOI]

Gábor Kun

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

On the Existence of 0/1 Polytopes with High Semidefinite Extension Complexity.

[BibT_eX]

[DOI]

Jop Briët

Sebastian Pokutta

Proceedings of the Algorithms - ESA 2013, 2013

On the Lattice Smoothing Parameter Problem.

[BibT_eX]

[DOI]

Proceedings of the 28th Conference on Computational Complexity, 2013

2012

Integer programming, lattice algorithms, and deterministic volume estimation.

[BibT_eX]

[DOI]

PhD thesis, 2012

Deterministic 2^{O(n)} Algorithms for M-Ellipsoids, Lattice Problems and Volume Estimation

[BibT_eX]

[DOI]

CoRR, 2012

Unconditional differentially private mechanisms for linear queries.

[BibT_eX]

[DOI]

Aditya Bhaskara

Ravishankar Krishnaswamy

Kunal Talwar

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Deterministic construction of an approximate M-ellipsoid and its applications to derandomizing lattice algorithms.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

A O(1/ε 2) n -Time Sieving Algorithm for Approximate Integer Programming.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2012: Theoretical Informatics, 2012

2011

The split closure of a strictly convex body.

[BibT_eX]

[DOI]

Santanu S. Dey

Juan Pablo Vielma

Oper. Res. Lett., 2011

The Chvátal-Gomory Closure of a Strictly Convex Body.

[BibT_eX]

[DOI]

Santanu S. Dey

Juan Pablo Vielma

Math. Oper. Res., 2011

A O(1/eps^2)^n Time Sieving Algorithm for Approximate Integer Programming

[BibT_eX]

[DOI]

CoRR, 2011

Deterministic Construction of an Approximate M-Ellipsoid and its Application to Derandomizing Lattice Algorithms

[BibT_eX]

[DOI]

CoRR, 2011

On the Chvátal-Gomory Closure of a Compact Convex Set.

[BibT_eX]

[DOI]

Santanu S. Dey

Juan Pablo Vielma

Proceedings of the Integer Programming and Combinatoral Optimization, 2011

Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings.

[BibT_eX]

[DOI]

Chris Peikert

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

Enumerative Algorithms for the Shortest and Closest Lattice Vector Problems in Any Norm via M-Ellipsoid Coverings

[BibT_eX]

[DOI]

Chris Peikert

Karthekeyan Chandrasekaran

CoRR, 2010

Thin Partitions: Isoperimetric Inequalities and a Sampling Algorithm for Star Shaped Bodies.

[BibT_eX]

[DOI]

Karthekeyan Chandrasekaran

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

2009

Thin Partitions: Isoperimetric Inequalities and Sampling Algorithms for some Nonconvex Families

[BibT_eX]

[DOI]