Carsten Damm, Stasys Jukna, Jiri Sgall

We introduce the model of conservative one-way multiparty complexity

and prove lower and upper bounds on the complexity of pointer jumping.

The pointer jumping function takes as its input a directed layered

graph with a starting node and layers of nodes, and a single edge ...
more >>>

Noam Nisan, Ziv Bar-Yossef

We consider the well known problem of determining the k'th

vertex reached by chasing pointers in a directed graph of

out-degree 1. The famous "pointer doubling" technique

provides an O(log k) parallel time algorithm on a

Concurrent-Read Exclusive-Write (CREW) PRAM. We prove that ...
more >>>

Amit Chakrabarti

We consider the $k$-layer pointer jumping problem in the one-way

multi-party number-on-the-forehead communication model. In this problem,

the input is a layered directed graph with each vertex having outdegree

$1$, shared amongst $k$ players: Player~$i$ knows all layers {\em

except} the $i$th. The players must communicate, in the order

$1,2,\ldots,k$, ...
more >>>

Emanuele Viola, Avi Wigderson

In this paper we study the one-way multi-party communication model,

in which every party speaks exactly once in its turn. For every

fixed $k$, we prove a tight lower bound of

$\Omega{n^{1/(k-1)}}$ on the probabilistic communication

complexity of pointer jumping in a $k$-layered tree, where the

pointers of the $i$-th ...
more >>>

Amit Chakrabarti, Tony Wirth

Set cover, over a universe of size $n$, may be modelled as a

data-streaming problem, where the $m$ sets that comprise the instance

are to be read one by one. A semi-streaming algorithm is allowed only

$O(n \text{ poly}\{\log n, \log m\})$ space to process this ...
more >>>

Henry Corrigan-Gibbs, Dmitry Kogan

We study preprocessing algorithms for the function-inversion problem. In this problem, an algorithm gets oracle access to a function $f\colon[N] \to [N]$ and takes as input $S$ bits of auxiliary information about $f$, along with a point $y \in [N]$. After running for time $T$, the algorithm must output an ... more >>>