Li–Li network coding conjecture

Imagine several people sending different messages through the same network. A router usually forwards pieces of each message. Network coding instead lets an intermediate node send a combination of pieces, which receivers may later disentangle. Can that mixing ever increase independent traffic when every link is two-way?[1] [2]

Different senders must deliver independent messages through shared two-way links. Can combining information at intermediate nodes ever achieve delivery rates beyond splitting each message among paths? Let $G$ be a finite connected undirected supply graph, with capacities $c(e)\geq0$ and independent sessions $(s_i,t_i)$. The zero-error coding and fractional-routing rate regions are $\mathcal C_{\rm NC}$ and $\mathcal C_{\rm MCF}$. A coding scheme uses source data and previously received symbols, with $f(u\to v)+f(v\to u)\leq c(\{u,v\})$. The conjecture requires $\mathcal C_{\rm NC}=\mathcal C_{\rm MCF}$ for every such graph, capacity assignment and session set.[1] [2]

Ordinary routing, including splitting a message across paths, has been proved to match coding when all senders and receivers together occupy at most five distinct places in the network. There may still be any number of intermediate routers and any arrangement of links. The open conjecture removes that endpoint restriction: does routing match mixing for every set of independent messages on shared two-way links? The theorem does not make a larger endpoint set a counterexample.[1] [2]

Routing is already a special case of coding, so the missing direction converts an arbitrary feasible coding rate into a multicommodity path flow. The dual formulation compares total coding cost with the sum of each session’s rate times its shortest-path distance. A recent session-interaction reformulation still requires proving independence of every irreducible core; naming that condition does not establish it.[1] [2]

Sorting data held outside a computer’s main memory costs transfers as well as comparisons. Some mathematical lower-bound arguments model data movements as independent messages in an undirected network. If mixing cannot save transmissions there, those arguments place limits on the transfers certain algorithms require. The consequence is conditional on both this conjecture and the specified computation model.[1] [2]

A routing limit expresses how much information can move along paths under shared capacities; a coding limit must allow intermediate computation on that information. The difference matters beyond router design. The cited Introduction reports conditional lower bounds for external-memory integer sorting and other computational models: suitable reductions treat data movements as network communication, so the absence of a coding advantage constrains the original computation. Within the network model, cut inequalities alone may miss routing constraints captured by metric duality. A weak cut bound is therefore not evidence that processing messages beats routing; a counterexample would need an achievable coding rate outside the full path-flow region.[1] [2]