Each query is a vertex v ∈ V. The answer is the triplet of bits I(v) = (T(v), S(v), P(v)) ∈ {0, 1}3.
Lemma 3.2
Randomized query complexity. For every constant
Proof
By Yao’s Minmax Theorem it is sufficient to introduce a distribution over paths such that every deterministic query algorithm requires Ω(2n) queries to determine the first bit of the end-of-line vertex with probability of at least 1 − δ. We choose a permutation π over [0, 1}n \ {0n} uniformly at random, and set π(0) ≜ 0n. π induces a line of length Θ(2n n) over G, starting at 02n+1, ending at (π(2n − 1), π(2n − 1),0), and where two consecutive vertices v = π(i) and w = π(i+1) are mapped to the following line of n + 1 edges:
Here (w[1,k], v[k+1,n]) denotes the vector with the first k coordinates as in w and the last n − k coordinates as in v.
The information of a single query of QUERY END-OF-THE-LINE (for the above class of lines) can be extracted from π(i − 1), π(i), and π(i + 1). Therefore QUERY END-OF-THE-LINE is at least as hard as the problem of finding the first bit of the last element in a random permutation, where each query returns the previous, the current, and the next vertices. Conditioning on the answers to k queries π(q1 − 1), π(q1), π(q1 + 1),…, π(qk − 1), π(qk), π(qk + 1), the last element of the permutation is still uniformly random across all vertices that are not π(q1),…, π(qk), π(q1 − 1),…, π(qk − 1), π(q1 + 1),…,π(qk + 1). This proves that the latter problem requires Ω(2n) queries.
3.5.2 Communicationally Hard, Discrete End-of-Any-Line Problem
In order to use a simulation theorem (Theorem 2.5) for randomized communication complexity, we define the following simulation variant of QUERY END-OF-THE-LINE:
Definition 3.2
SIMULATION END-OF-THE-LINE. We let N = 2n·2n·(n + 1)·3.
Input: For each v ∈{0, 1}n ×{0, 1}n × [n + 1], Alice receives three vectors
We define
We simulate the problem QUERY END-OF-THE-LINE; therefore we restrict attention to inputs such that (T, S, P) that are defined in (3.1) meet all the requirements of QUERY END-OF-THE-LINE.
Output: The first bit ([v*]1) of a non-trivial end or start of a line (v*, v*, 0) ≠ 02n+1.
Applying the randomized simulation theorem (Theorem 2.5) to the query complexity lower bound (Lemma 3.2) gives a lower bound on the randomized communication complexity of a discrete end-of-line problem SIMULATIONEND-OF-THE-LINE.
Corollary 3.4
3.5.3 Embedding a Line as a Local Lipschitz Function
We embed I as a Euclidean-norm hard continuous function à la Section 4.2. Below, we recall some of the properties of the construction that will be useful for our reduction.
It will be more convenient to think of G as a graph over {0, 1}2n+log(n+1).
Let m =Θ(2n+ log(n + 1)) = Θ(n) and let E: {0, 1}2n+log(n+1) → {0, 1}m denote the encoding function of a good binary error-correcting code. We embed the discrete graph G into the continuous cube [−1, 2]4m.
The vertex v is embedded to the point (E(v), E(v), 0m, 0m) ∈ [−1, 2]4m, which is called the embedded vertex.
For two vertices v, w ∈ V such that (v, w) is an edge in the graph G, we define five vertices:
Note that x1(v, w) is the embedded vertex v, x5(v, w) is the embedded vertex w.
The line that connects the points xi(v, w) and xi+1(v, w) is called a Brouwer line segment. The union of these four Brouwer line segments is called the embedded edge (v, w). It is not hard to check that non-consecutive Brouwer line segments are Ω(1)-far one from the other, and in particular it implies that non-consecutive embedded edges are sufficiently far one from the other.
The following proposition shows that the END-OF-THE-LINE problem can be reduced to the problem of finding an approximate fixed point of a continuous Lipschitz function, when the function is “local” in the following sense: every edge in G is embedded as a path in the continuous hypercube (as described above). For points close to the embedding of an edge, f depends only on the “local behavior” of the lines I at the endpoints of this edge; for all other points, f is independent of the lines I.
Proposition 3.1
Theorem 4.2 and Fact 4.2. There exist constants δ, h> 0 such that given a line I = (T, S, P) over G there exists a function f = f(I) = [−1, 2]4m → [−1, 2]4m with the following properties:
1. ||f(x) − x||2 >δ for every x that is not h-close to the embedded edge of the end of the line (i.e., the embedding
