##
Polynomially Low Error PCPs with polyloglogn Queries via Modular Composition

by Irit Dinur, Prahladh Harsha, and Guy Kindler

#### Oded's comments

Only when equipped with refined composition theorems one may dare revisit
recursive constructions such as DFKRS [DFK+11]. Indeed, having developed a
new refined composition, the authors undertake this task.
They obtain a PCP with $q = O((\log n)^\eps)/\eps$ queries,
soundness error $1/n$, and alphabet size $\exp(\log^{1-\eps} n)$.
This holds also for sub-constant $\eps>0$,
but note that the number of bits retrieved is $O(\eps^{-1} \log n)$.
(This fact can, of course, be hidden when one uses a constant $\eps>0$,
but appears when one wants to use a sub-constant $\eps$.)

As usual, this is for logarithmic randomness, perfect completeness,
and using a non-adaptive verifier.
The stated result is obtained by optimizing the query complexity:
Picking $\eps = \log\log\log n / \log\log n$, yields $q < 1/\eps^2$.

#### The original abstract

We show that every language in NP has a PCP verifier that tosses $O(\log
n)$ random coins, has perfect completeness, and a soundness error of at
most $1/poly(n)$, while making at most $O(poly\log\log n)$ queries into a
proof over an alphabet of size at most $n^{1/poly\log\log n}$. Previous
constructions that obtain $1/\poly(n)$ soundness error used either
$poly\log n $ queries or an exponential sized alphabet, i.e. of size
$2^{n^c}$ for some $c>0$. Our result is an exponential improvement in
both parameters simultaneously.

Our result can be phrased as a polynomial-gap hardness for approximate
CSPs with arity $poly\log\log n$ and alphabet size $n^{1/poly\log n}$. The
ultimate goal, in this direction, would be to prove polynomial hardness for
CSPs with constant arity and polynomial alphabet size (aka the sliding
scale conjecture for inverse polynomial soundness error).

Our construction is based on a modular generalization of previous PCP
constructions in this parameter regime, which involves a composition
theorem that uses an extra `consistency' query but maintains the
inverse polynomial relation between the soundness error and the alphabet
size.

Our main technical/conceptual contribution is a new notion of
soundness, which we refer to as distributional soundness, that replaces the
previous notion of *list decoding soundness*, and that allows us
to prove a modular composition theorem with tighter parameters. This new
notion of soundness allows us to invoke composition a super-constant number
of times without incurring a blow-up in the soundness error.

See ECCC TR15-085.

Back to
list of Oded's choices.