Yosi Ben-Asher, Ilan Newman

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

Dimitrios Koukopoulos, Marios Mavronicolas, Paul Spirakis

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

David GarcĂa Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briet

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

Oded Goldreich, Avi Wigderson

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