Solving Classes of Linear Programs with Strongly Polynomial Straight Line Complexity in Strongly Polynomial Time
1 version
DD
Daniel Dadush
cs.DSmath.OCcs.CCcs.DMmath.COmath.PRmath.FAcs.CGmath.MGBranch and bound
On Valency
published · living versionsPreprints & journals
55 papers in the corpus · 2009–2026Solving Classes of Linear Programs with Strongly Polynomial Straight Line Complexity in Strongly Polynomial Time
0 citations
A Simple Algorithm for Counting Solutions to Integer Programs
0 citations
Faster Directed Hopsets, Distance Preservers, and Deterministic Shortcut Sets
0 citations
Greedy Vector Balancing
0 citations
On finding exact solutions of linear programs in the oracle model
0 citations
Revisiting Diameter in Directed Graphs
0 citations
Dynamic Detours
0 citations
On Circuit Diameter and Straight Line Complexity
0 citations
Greedy Algorithms for Shortcut Sets and Hopsets
0 citations
Excluding a Line Minor via Design Matrices and Column Number Bounds for the Circuit Imbalance Measure
0 citations
From Incremental Transitive Cover to Strongly Polynomial Maximum Flow
0 citations
Lower bounds for cube-ideal set-systems
0 citations
A nearly optimal randomized algorithm for explorable heap selection.
1 citation
From approximate to exact integer programming.
1 citation
Strongly Polynomial Frame Scaling to High Precision
1 citation
Optimizing Low Dimensional Functions over the Integers
0 citations
From approximate to exact integer programming
2 citations
A nearly optimal randomized algorithm for explorable heap selection
5 citations
Interior point methods are not worse than Simplex
8 citations
Integrality Gaps for Random Integer Programs via Discrepancy
6 citations
Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes
1 citation
On Circuit Diameter Bounds via Circuit Imbalances
4 citations
A New Framework for Matrix Discrepancy: Partial Coloring Bounds via Mirror Descent
8 citations
Majorizing Measures for the Optimizer
1 citation
On the Integrality Gap of Binary Integer Programs with Gaussian Data
11 citations
A Simple Method for Convex Optimization in the Oracle Model
3 citations
Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers
18 citations
On the Complexity of Branching Proofs
18 citations
An Accelerated Newton-Dinkelbach Method and its Application to Two Variables Per Inequality Systems
3 citations
A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
16 citations
Lattice-based Locality Sensitive Hashing is Optimal
1 citation
A Friendly Smoothed Analysis of the Simplex Method
31 citations
The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues
39 citations
AWGN-Goodness is Enough: Capacity-Achieving Lattice Codes based on Dithered Probabilistic Shaping
11 citations
Geometric Rescaling Algorithms for Submodular Function Minimization
13 citations
Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem
12 citations
Rescaling Algorithms for Linear Conic Feasibility
16 citations
Towards Strong Reverse Minkowski-type Inequalities for Lattices
12 citations
On the Lattice Distortion Problem
1 citation
An Algorithm for Komlós Conjecture Matching Banaszczyk's bound
7 citations
Solving the Closest Vector Problem in Time--- The Discrete Gaussian Strikes Again!
72 citations
On the Lattice Smoothing Parameter Problem
27 citations
Solving the Shortest Vector Problem in Time via Discrete Gaussian Sampling
39 citations
On the Shadow Simplex Method for Curved Polyhedra
25 citations
Short Paths on the Voronoi Graph and the Closest Vector Problem with Preprocessing
2 citations
On the Closest Vector Problem with a Distance Guarantee
41 citations
A Deterministic Polynomial Space Construction for eps-nets under any Norm
2 citations
On the existence of 0/1 polytopes with high semidefinite extension complexity
34 citations
Lattice Sparsification and the Approximate Closest Vector Problem
10 citations
Near-Optimal Deterministic Algorithms for Volume Computation and Lattice Problems via M-Ellipsoids
22 citations
Profile built from the corpus for this byline.
Author records are still filling in while the Hub is in beta. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.