2 papers
cs.CC2016
Tight Network Topology Dependent Bounds on Rounds of Communication
Arkadev Chattopadhyay, Michael Langberg, Shi Li +1
We prove tight network topology dependent bounds on the round complexity of computing well studied -party functions such as set disjointness and element distinctness. Unlike the…
cs.DS2010
Vertex Sparsifiers and Abstract Rounding Algorithms
Moses Charikar, Tom Leighton, Shi Li +1
The notion of vertex sparsification is introduced in \cite{M}, where it was shown that for any graph and a subset of terminals , there is a polynomial…