  We present a new distributed model of probabilistically checkable proofs
(PCP). A satisfying assignment $x \in \{0,1\}^n$ to a CNF formula $\varphi$ is
shared between two parties, where Alice knows $x_1, \dots, x_{n/2}$, Bob knows
$x_{n/2+1},\dots,x_n$, and both parties know $\varphi$. The goal is to have
Alice and Bob jointly write a PCP that $x$ satisfies $\varphi$, while
exchanging little or no information. Unfortunately, this model as-is does not
allow for nontrivial query complexity. Instead, we focus on a non-deterministic
variant, where the players are helped by Merlin, a third party who knows all of
$x$.
  Using our framework, we obtain, for the first time, PCP-like reductions from
the Strong Exponential Time Hypothesis (SETH) to approximation problems in P.
In particular, under SETH we show that there are no truly-subquadratic
approximation algorithms for Bichromatic Maximum Inner Product over
{0,1}-vectors, Bichromatic LCS Closest Pair over permutations, Approximate
Regular Expression Matching, and Diameter in Product Metric. All our
inapproximability factors are nearly-tight. In particular, for the first two
problems we obtain nearly-polynomial factors of $2^{(\log n)^{1-o(1)}}$; only
$(1+o(1))$-factor lower bounds (under SETH) were known before.

Computational Complexity