Hardness of Approximation Between P and NP. Aviad Rubinstein

Читать онлайн книгу.

Hardness of Approximation Between P and NP - Aviad Rubinstein


Скачать книгу
(w[1,k], v[k+1,n]) denotes the vector with the first k coordinates as in w and the last nk 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 imageimage, and Bob receives three indices image.

      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.

      image(SIMULATIONEND-OF-THE-LINE) = Ω(2n).

       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, wV such that (v, w) is an edge in the graph G, we define five vertices:

image

      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.

      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 of the edge (P(v*), v*).

      2. f is 0(1)-Lipschitz in ||·||2 norm.

      3. f is local in the sense that it can be defined as an interpolation between a few (in fact, 64) functions, image, that do not depend on the lines I and such that:

      (a) If the first m-tuple of coordinates of x is 6h-close to the encoded vertex E(v), but the second m-tuple of coordinates of x is 6h-far from any encoded vertex E(w), then image for every I2 ∈ {0, 1}3.

      (b) If the second m-tuple of coordinates of x is 6h-close to the encoded vertex E(w), but the first m-tuple of coordinates of x is 6h-far from any encoded vertex E(v), then image for every I1 ∈ {0, 1}3.

      (c) If the first m-tuple of coordinates of x is 6h-close to the encoded vertex E(v), and the second m-tuple of coordinates of x is 6h-close to the encoded vertex E(w), then f(I(v),I(w)(x) = f(x).

      (d) If none of the above conditions are satisfied, then image for every I1, I2 ∈ {0, 1}3.

       3.5.4 Two-Player Game

       Theorem 3.3

      Theorem 3.1, restated.


Скачать книгу