Skip to content
lectern.tv
Simons Institute: Theoretical Foundations of Modern Machine Learning →0/19
1

Talk by Pranjal Awasthi (Google) (SIMONS-TCS-ML)

38:15
2

Talk by Katrina Ligett (Hebrew University of Jerusalem) (SIMONS-TCS-ML)

36:41
3

Efficient Algorithms for Reliable Machine Learning (SIMONS-TCS-ML)

37:26
4

Computational Thinking on Learning Models (SIMONS-TCS-ML)

38:30
5

On the Komlós Conjecture (SIMONS-TCS-ML)

33:41
6

Multi-objective Learning: An Algorithmic Toolbox for Optimal Predictions Anytime Anywhere! (SIMONS-TCS-ML)

37:40
7

Approximately Packing Dijoins Via Nowhere-Zero Flows (SIMONS-TCS-ML)

33:46
8

Lightning Talks! (SIMONS-TCS-ML)

56:01
9

Venturing out into the world with AI (SIMONS-TCS-ML)

44:41
10

Unfamiliar Terrain (SIMONS-TCS-ML)

29:51
11

Astral Space: Convex Analysis at Infinity (SIMONS-TCS-ML)

44:01
12

AI and Safety (SIMONS-TCS-ML)

29:26
13

The Role of TCS in Understanding (AI) Consciousness (SIMONS-TCS-ML)

43:21
14

The Conscious Turing Machine (CTM), a formally defined Theoretical model of Consciousness (SIMONS-TCS-ML)

45:00
15

Theory of Modern AI: Learning Theoretic, Game Theoretic, and Algorithmic Perspectives (SIMONS-TCS-ML)

40:41
16

An Occam's Razor Principle for Transformers? (SIMONS-TCS-ML)

39:55
17

Red Points and Blue Points (SIMONS-TCS-ML)

38:15
18

Latent Variable models and Subset Smoothing (SIMONS-TCS-ML)

29:26
19

Enhanced and Efficient Reasoning in Large Language Models (SIMONS-TCS-ML)

36:16

Approximately Packing Dijoins Via Nowhere-Zero Flows (SIMONS-TCS-ML)

R RaviSimons Institute (UC Berkeley)

Professor

33:46·2026·research level

R Ravi explores Woodall's conjecture on dijoins, proving that digraphs with minimum dicut size $\tau$ contain $\lfloor \tau/k \rfloor$ disjoint dijoins if the underlying graph has a nowhere-zero k-flow.

Theory & AlgosGraph TheoryNetwork FlowsWoodall's ConjectureCombinatorial Optimization

R Ravi (Carnegie Mellon University)

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.

Previous · Lecture 6

Multi-objective Learning: An Algorithmic Toolbox for Optimal Predictions Anytime Anywhere! (SIMONS-TCS-ML)

Next · Lecture 8

Lightning Talks! (SIMONS-TCS-ML)

Comments

Add a comment...Sign in