We study the one-way number-on-the-forhead (NOF) communication complexity of the k-layer pointer jumping problem. Strong lower bounds for this problem would have important implications in circuit complexity. All of our results apply to myopic protocols (where players see only one layer ahead, but can still see arbitrarily far behind them.) ... more >>>

The Gap-Hamming-Distance problem arose in the context of proving space lower bounds for a number of key problems in the data stream model. In this problem, Alice and Bob have to decide whether the Hamming distance between their $n$-bit input strings is large (i.e., at least $n/2 + \sqrt n$) ... more >>>