# Uniform multicommodity flow in the hypercube with random edge capacities

arXiv: https://arxiv.org/abs/1406.4433 · HTML: https://mlsanity.com/paper/1406.4433/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jun 2014.

## Built on by (most cited first, 1 of 1)

- [Certifying almost all quantum states with few single-qubit measurements](https://mlsanity.com/paper/2404.07281/) (2024)

## Abstract (arXiv)

We give two results for multicommodity flows in the d-dimensional hypercube Qd with independent random edge capacities distributed like C where Pr[C>0]>1/2. Firstly, with high probability as d rightarrow ∞, the network can support simultaneous multicommodity flows of volume close to E[C] between all antipodal vertex pairs. Secondly, with high probability, the network can support simultaneous multicommodity flows of volume close to 21-d E[C] between all vertex pairs. Both results are best possible.