Math Conjectures

Li–Li Undirected Network Coding Conjecture

OPENMajorConjectureProposed 2004 · Standard version

Canonical statement

For every finite undirected capacitated network with any finite collection of unicast source--sink pairs, the maximum common rate achievable by arbitrary network coding equals the maximum common rate achievable by fractional multicommodity routing.
View source LaTeX
For every finite undirected capacitated network with any finite collection of unicast source--sink pairs, the maximum common rate achievable by arbitrary network coding equals the maximum common rate achievable by fractional multicommodity routing.
INFO-006:[LiLi2004NetworkCoding][BravermanEtAl2017LiLi]
Information theoryTheoretical computer scienceOperations research

Notes

For a single multicast source, network coding can outperform routing, and directed multiple-unicast networks also admit separations. Li and Li conjectured that undirected multiple-unicast networks are different: coding should offer no gain over fractional multicommodity flow [LiLi2004NetworkCoding]. The conjecture has become a central bridge between information and communication complexity [BravermanEtAl2017LiLi], with neither an equality proof nor a counterexample known.

References (2)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.