The Edge Removal Problem

on YouTube ↗30m

" summary

Asks whether removing a directed edge of capacity δ always reduces every achievable rate by at most δ and frames an edge removal conjecture that is open; proves the claim for multicast, co-located sources and linear codes, and gives the butterfly example where removing δ drops both rates by δ. Shows adversarial and memoryless-noise constructions where a vanishing-capacity (≈log n / n) edge causes a large rate collapse, links the conjecture equivalently to the zero versus epsilon reliability gap and to reductions between network and index coding.

AI-written summary · about

" chapters (11)

1. 0:00Intro
2. 1:18Noiseless networks: network coding
3. 1:51Simplifying assumptions
4. 5:37The edge removal problem
5. 8:39Price of "edge removal"
6. 12:37Edge removal in noisy networks
7. 17:05Reliability: Zero vs ε error
8. 20:54Edge removal - zero error !
9. 23:29Network communication challenging combines topology with information
10. 24:35Reduction in code design: a code for IC corresponds to a code for NC
11. 25:18Edge removal resolves the Q