April Rasala Lehman, Eric Lehman

We consider the general network information flow problem, which was

introduced by Ahlswede et. al. We show a periodicity effect: for

every integer m greater than 1, there exists an instance of the

network information flow problem that admits a solution if and only if

the alphabet size is a ...
more >>>

Shachar Lovett

Network coding studies the capacity of networks to carry information, when internal nodes are allowed to actively encode information. It is known that for multi-cast networks, the network coding capacity can be achieved by linear codes. It is also known not to be true for general networks. The best separation ... more >>>

Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra

We prove tight network topology dependent bounds on the round complexity of computing well studied $k$-party functions such as set disjointness and element distinctness. Unlike the usual case in the CONGEST model in distributed computing, we fix the function and then vary the underlying network topology. This complements the recent ... more >>>