Daniel Dadush

activity

20242026

collaborators

Showing 2025Show all

2 papers · 1 filter

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^{ω + o (1)}$ -time strongly polynomial time…

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} κ_{A})$ where $κ_{A}$ is the \emph{circuit imbalance measure} of $A$ . The circu…