When does augmented indexing become easy?

Question

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

Questions:

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)$?

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.