Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Network Coding:
TR04-034 | 12th April 2004
April Rasala Lehman, Eric Lehman

Network Coding: Does the Model Need Tuning?

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 >>>

TR14-141 | 24th October 2014
Shachar Lovett

Linear codes cannot approximate the network capacity within any constant factor

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 >>>

TR16-130 | 11th August 2016
Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra

Tight Network Topology Dependent Bounds on Rounds of Communication

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 >>>

ISSN 1433-8092 | Imprint