that v is never a solution to the new END-OF-A-LINE instance.
■
We will be interested in restricted (but equally hard) variants of MEMBERSHIP END-OF-A-LINE. For example, in Section 16.2 we define LOCAL END-OF-A-LINE where, among other restrictions, T, S, P are AC0 circuits. In particular, in Chapter 3, we will consider a variant where each vertex is a priori restricted to have at most two potential incoming/outgoing neighbors, and the functions S, P merely specify which neighbor is chosen. We then abuse notation and let S, P output just a single bit.
2.3 Exponential Time Hypotheses
Our quasi-polynomial hardness results are conditional on the following hypotheses. We begin with the “plain” ETH:
Hypothesis 2.1
Exponential time hypothesis (ETH) [Impagliazzo et al. 2001]. 3SAT takes time 2Ω (n).
Since a Nash equilibrium always exists, we are unlikely to have a reduction (even of subexponential size) from 3SAT to Nash equilibrium. Instead, we need to assume the following analogue of ETH for the total class PPAD:
Hypothesis 2.2
ETH for PPAD [Babichenko et al. 2016]. Solving END-OF-A-LINE requires time
In Section 13.3 we will prove a quasi-polynomial lower bound on the running time for counting the number of communities in a social network. This result is also conditional, but requires the following much weaker #ETH assumption:
Hypothesis 2.3
#ETH [Dell et al. 2014]. Given a 3SAT formula, counting the number of satisfying assignments takes time 2Ω(n).
2.4 PCP Theorems
2.4.1 2CSP and the PCP Theorem
In the 2CSP problem (Constraint Satisfaction Problem), we are given a graph G = (V, E) on | V | = n vertices, where each of the edges (u, v) ∈ E is associated with some constraint function ψu, v : Σ × Σ → {0, 1} that specifies a set of legal “colorings” of u and v, from some finite alphabet Σ (2 in the term “2CSP” stands for the “arity” of each constraint, which always involves two variables). Let us denote by ψ the entire 2CSP instance, and define by OPT(ψ) the optimum (maximum) fraction of satisfied constraints in the associated graph G, over all possible assignments (colorings) of V.
The starting point of some of our reductions is the following version of the Probabilistically Checkable Proof (PCP) theorem, which asserts that it is NP-hard to distinguish a 2CSP instance whose value is 1, and one whose value is 1 − η, where η is some small constant:
Theorem 2.1
PCP Theorem [Dinur 2007]. Given a 3SAT instance φ of size n, there is a polynomial time reduction that produces a 2CSP instance ψ, with size |ψ| = n · polylog n variables and constraints, and constant alphabet size such that
• (Completeness) If OPT(φ) = 1 then OPT(ψ) = 1.
• (Soundness) If OPT(φ) < 1 then OPT(ψ) < 1 − η, for some constant η = Ω(1).
• (Graph) The constraint graph is d-regular, for some constant d, and bipartite.
See, e.g., the full version of Braverman et al. [2017]or Aaronson et al. [2014] for derivations of this formulation of the PCP theorem.
Notice that since the size of the reduction is near linear, ETH implies that solving the above problem requires near exponential time.
Corollary 2.1
Let ψ be as in Theorem 2.1. Then assuming ETH, distinguishing between OPT(ψ) = 1 and OPT(ψ) < 1 − η requires time
Label Cover
Definition 2.7
LABEL COVER. LABEL COVER is a maximization problem, and a special case of 2CSP. The input is a bipartite graph G = (A, B, E), alphabets, ΣB, ΣB and a projection πe : ΣA → ΣB for every e ∈ E.
The output is a labeling φA : A → ΣA, φΒ : Β → ΣB. Given a labeling, we say that a constraint (or edge) (a, b) ∈ E is satisfied if π(a, b) (φA(a)) = φB(b). The value of a labeling is the fraction of e ∈ E that are satisfied by the labeling. The value of the instance is the maximum fraction of constraints satisfied by any assignment.
We often encounter an assignment that only labels a subset of A ⋃ Β but leaves the rest unlabeled. We refer to such assignment as a partial assignment to an instance; more specifically, for any V ⊆ A ⋃ Β, a V-partial assignment (or partial assignment on V) is a function ϕ : V → Σ. For notational convenience, we sometimes write ΣV to denote the set of all functions from V to Σ.
Theorem 2.2
Moshkovitz-Raz PCP [Moshkovitz and Raz 2010 (Theorem 11)]. For every n and every ϵ > 0 (in particular, ϵ may be a function of n), solving 3SAT on inputs of size n can be reduced to distinguishing between the case that a (dA, dB)-bi-regular instance of LABEL COVER, with parameters |A| + |B| = n1+o(1) · poly(1/∈), |ΣA| = 2poly(1/∈), and dA, dB, |ΣB| = poly(1/∈), is completely satisfiable, versus the case that it has value at most ϵ.
Counting the number of satisfying assignments is even harder. The following hardness is well-known, and we sketch its proof only for completeness:
Fact 2.1
There is a linear-time reduction from #3SAT to counting the number of satisfying assignments of a LABEL COVER instance.
Proof
Construct a vertex in A for each variable and a vertex in Β for each clause. Set ΣA ≜ {0, 1} and let ΣB ≜ {0, 1}3 \ (000) (i.e., ΣB is the set of satisfying assignments for a 3SAT clause, after applying negations). Now if variable x appears in clause C, add a constraint that the assignments to x and C are consistent (taking into account the sign of x in C). Notice that: (i) any assignment to A corresponds to a unique assignment to the
