Daniel Dadush | DeepAI

DeepAI AI Chat

Featured Co-authors

Haotian Jiang
27 publications
Lars Rohwedder
23 publications
Elena Grigorescu
19 publications
Karthekeyan Chandrasekaran
16 publications
Stefan Weltge
15 publications
Makrand Sinha
14 publications
László A. Végh
14 publications
Thomas Rothvoss
14 publications
Victor Reis
11 publications
Neil Olver
11 publications
Friedrich Eisenbrand
10 publications

∙ 03/04/2023

Optimizing Low Dimensional Functions over the Integers

We consider box-constrained integer programs with objective g(Wx) + c^T ...

0 Daniel Dadush, et al. ∙

∙ 11/07/2022

From approximate to exact integer programming

Approximate integer programming is the following: For a convex body K ⊆ℝ...

0 Daniel Dadush, et al. ∙

∙ 10/12/2022

A nearly optimal randomized algorithm for explorable heap selection

Explorable heap selection is the problem of selecting the nth smallest v...

0 Sander Borst, et al. ∙

∙ 06/17/2022

Interior point methods are not worse than Simplex

Whereas interior point methods provide polynomial-time linear programmin...

0 Xavier Allamigeon, et al. ∙

∙ 12/24/2021

Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes

The combinatorial diameter diam(P) of a polytope P is the maximum shorte...

0 Gilles Bonnet, et al. ∙

∙ 11/15/2021

On Circuit Diameter Bounds via Circuit Imbalances

We study the circuit diameter of polyhedra, introduced by Borgwardt, Fin...

0 Daniel Dadush, et al. ∙

∙ 11/04/2021

A New Framework for Matrix Discrepancy: Partial Coloring Bounds via Mirror Descent

Motivated by the Matrix Spencer conjecture, we study the problem of find...

0 Daniel Dadush, et al. ∙

∙ 12/24/2020

Majorizing Measures for the Optimizer

The theory of majorizing measures, extensively developed by Fernique, Ta...

0 Sander Borst, et al. ∙

∙ 12/15/2020

On the Integrality Gap of Binary Integer Programs with Gaussian Data

For a binary integer program (IP) max c^𝖳 x, Ax ≤ b, x ∈{0,1}^n, where A...

0 Sander Borst, et al. ∙

∙ 11/17/2020

Simple Iterative Methods for Linear Optimization over Convex Sets

We give simple iterative methods for computing approximately optimal pri...

0 Daniel Dadush, et al. ∙

∙ 09/10/2020

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

In breakthrough work, Tardos (Oper. Res. '86) gave a proximity based fra...

0 Daniel Dadush, et al. ∙

∙ 06/07/2020

On the Complexity of Branching Proofs

We consider the task of proving integer infeasibility of a bounded conve...

0 Daniel Dadush, et al. ∙

∙ 12/12/2019

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

Following the breakthrough work of Tardos in the bit-complexity model, V...

0 Daniel Dadush, et al. ∙

∙ 12/22/2017

Lattice-based Locality Sensitive Hashing is Optimal

Locality sensitive hashing (LSH) was introduced by Indyk and Motwani (ST...

0 Karthekeyan Chandrasekaran, et al. ∙

∙ 11/15/2017

A Friendly Smoothed Analysis of the Simplex Method

Explaining the excellent practical performance of the simplex method for...

0 Daniel Dadush, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world