Daniel Dadush

collaborators

3 papers

math.OC2026

On Circuit Diameter and Straight Line Complexity

Daniel Dadush, Stefan Kober, Zhuan Khye Koh

The circuit diameter of a polyhedron is the maximum length (number of steps) of a shortest circuit walk between any two vertices of the polyhedron. Introduced by Borgwardt, Finhold…

cs.DS2025

From Incremental Transitive Cover to Strongly Polynomial Maximum Flow

Daniel Dadush, James B. Orlin, Aaron Sidford +1

We provide faster strongly polynomial time algorithms solving maximum flow in structured $n$ -node $m$ -arc networks. Our results imply an $n^{I ¨ + o (1)}$ -time strongly polynomial tim…

cs.DM2025

Excluding a Line Minor via Design Matrices and Column Number Bounds for the Circuit Imbalance Measure

Daniel Dadush, Friedrich Eisenbrand, Rom Pinchasi +2

For a real matrix $A \in R^{d \times n}$ with non-collinear columns, we show that $n \leq O (d^{4} I^º_{A})$ where $I^º_{A}$ is the \emph{circuit imbalance measure} of $A$ . The cir…