Uploaded May 2026 | Updated September 2026, 2 weeks ago
R Ravi (Carnegie Mellon University)
https://simons.berkeley.edu/talks/r-ravi-carnegie-mellon-university-2026-05-28
The Role of TCS in Modern Machine Learning
In a digraph, a dicut is a cut where all the arcs cross in one direction. A dijoin is a subset of arcs that intersects each dicut. Woodall conjectured in 1976 that in every digraph, the minimum size of a dicut equals to the maximum number of disjoint dijoins. By building connections with nowhere-zero k-flows, we prove that every digraph with minimum dicut size $\tau$ contains $\lfloor \tau/k \rfloor$ disjoint dijoins if the underlying undirected graph admits a nowhere-zero k-flow.
Joint work with Gérard Cornuéjols (CMU) and Siyue Liu (CMU)
R Ravi (Carnegie Mellon University)
https://simons.berkeley.edu/talks/r-ravi-carnegie-mellon-university-2026-05-28
The Role of TCS in Modern Machine Learning
In a digraph, a dicut is a cut where all the arcs cross in one direction. A dijoin is a subset of arcs that intersects each dicut. Woodall conjectured in 1976 that in every digraph, the minimum size of a dicut equals to the maximum number of disjoint dijoins. By building connections with nowhere-zero k-flows, we prove that every digraph with minimum dicut size $\tau$ contains $\lfloor \tau/k \rfloor$ disjoint dijoins if the underlying undirected graph admits a nowhere-zero k-flow.
Joint work with Gérard Cornuéjols (CMU) and Siyue Liu (CMU)
