Hardness of Approximation Between P and NP. Aviad Rubinstein

Чтение книги онлайн.

Читать онлайн книгу Hardness of Approximation Between P and NP - Aviad Rubinstein страница 20

Автор:
Жанр:
Серия:
Издательство:
Hardness of Approximation Between P and NP - Aviad Rubinstein ACM Books

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

Each query is a vertex vV. The answer is the triplet of bits I(v) = (T(v), S(v), P(v)) ∈ {0, 1}3.

      Randomized query complexity. For every constant image,image(QUERYEND-OF-THE-LINE) = Ω(2n).

       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:

image

      Here (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

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