Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with routing:
TR96-053 | 6th August 1996
Yosi Ben-Asher, Ilan Newman

Geometric Approach for Optimal Routing on Mesh with Buses

Revisions: 1

The architecture of 'mesh of buses' is an important model in parallel computing. Its main advantage is that the additional broadcast capability can be used to overcome the main disadvantage of the mesh, namely its relatively large diameter. We show that the addition of buses indeed accelerates routing times. Furthermore, ... more >>>

TR03-016 | 15th January 2003
Dimitrios Koukopoulos, Marios Mavronicolas, Paul Spirakis

FIFO is Unstable at Arbitrarily Low Rates

Revisions: 1

In this work, we study the stability of the {\sf FIFO} ({\sf
First-In-First-Out}) protocol in the context of Adversarial
Queueing Theory. As an important intermediate step, we consider
{\em dynamic capacities}, where each network link capacity may
arbitrarily take on values in the two-valued set of integers
$\{1,C\}$ for $C>1$ ... more >>>

TR10-048 | 24th March 2010
David GarcĂ­a Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briet

Monotonicity Testing and Shortest-Path Routing on the Cube

We study the problem of monotonicity testing over the hypercube. As
previously observed in several works, a positive answer to a natural question about routing
properties of the hypercube network would imply the existence of efficient
monotonicity testers. In particular, if any $\ell$ disjoint source-sink pairs
on the directed hypercube ... more >>>

TR20-192 | 27th December 2020
Oded Goldreich, Avi Wigderson

Constructing Large Families of Pairwise Far Permutations: Good Permutation Codes Based on the Shuffle-Exchange Network

We consider the problem of efficiently constructing an as large as possible family of permutations such that each pair of permutations are far part (i.e., disagree on a constant fraction of their inputs).
Specifically, for every $n\in\N$, we present a collection of $N=N(n)=(n!)^{\Omega(1)}$ pairwise far apart permutations $\{\pi_i:[n]\to[n]\}_{i\in[N]}$ and ... more >>>

ISSN 1433-8092 | Imprint