research
∙
03/04/2023
Optimizing Low Dimensional Functions over the Integers
We consider box-constrained integer programs with objective g(Wx) + c^T ...
share
research
∙
11/07/2022
From approximate to exact integer programming
Approximate integer programming is the following: For a convex body K ⊆ℝ...
research
∙
10/12/2022
A nearly optimal randomized algorithm for explorable heap selection
Explorable heap selection is the problem of selecting the nth smallest v...
research
∙
06/17/2022
Interior point methods are not worse than Simplex
Whereas interior point methods provide polynomial-time linear programmin...
research
∙
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...
research
∙
11/15/2021
On Circuit Diameter Bounds via Circuit Imbalances
We study the circuit diameter of polyhedra, introduced by Borgwardt, Fin...
research
∙
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...
research
∙
12/24/2020
Majorizing Measures for the Optimizer
The theory of majorizing measures, extensively developed by Fernique, Ta...
research
∙
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...
research
∙
11/17/2020
Simple Iterative Methods for Linear Optimization over Convex Sets
We give simple iterative methods for computing approximately optimal pri...
research
∙
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...
research
∙
06/07/2020
On the Complexity of Branching Proofs
We consider the task of proving integer infeasibility of a bounded conve...
research
∙
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...
research
∙
12/22/2017
Lattice-based Locality Sensitive Hashing is Optimal
Locality sensitive hashing (LSH) was introduced by Indyk and Motwani (ST...
research
∙
11/15/2017
