Consider the following problem in 2-party communication complexity, where Alice sends a single message to Bob who must compute the output.

  • Alice gets as input a bit vector $X=(x_1,...,x_N)$, for some integer N.
  • Bob gets as input an index $i \in [N]$ and gets $x_1,\dots,x_{i-1},x_{i+1},\dots,x_N$.

Goal: Bob must output $x_i$ after receiving a single message from Alice.

When Bob only knows $x_1,\dots,x_{i-1}$, this problem is known as Agumented Indexing and has a lower bound of $\Omega(N)$ bits, even for randomized protocols with constant error. However, I could not find any results about the variant where Bob knows everything except $x_i$.


  1. Is there a randomized protocol that can do better than $O(n)$ bits?
  2. If the answer to 1 is yes, is the lower bound for deterministic protocols still $\Omega(n)$?

1 Answer 1


I can answer my own question: Alice just sends the parity of her input to Bob, and from this, Bob can compute the answer, so there is no nontrivial lower bound.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.