Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with pointer jumping:
TR95-044 | 18th September 1995
Carsten Damm, Stasys Jukna, Jiri Sgall

Some Bounds on Multiparty Communication Complexity of Pointer Jumping

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

TR97-008 | 16th March 1997
Noam Nisan, Ziv Bar-Yossef

Pointer Jumping Requires Concurrent Read

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

TR07-014 | 23rd January 2007
Amit Chakrabarti

Lower Bounds for Multi-Player Pointer Jumping

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

TR07-079 | 11th August 2007
Emanuele Viola, Avi Wigderson

One-way multi-party communication lower bound for pointer jumping with applications

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

TR15-113 | 9th July 2015
Amit Chakrabarti, Tony Wirth

Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover

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

TR18-182 | 31st October 2018
Henry Corrigan-Gibbs, Dmitry Kogan

The Function-Inversion Problem: Barriers and Opportunities

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

ISSN 1433-8092 | Imprint