English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

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/\text{poly}(n)$, while making at most $O(\text{poly}\log\log n)$ queriesinto a proof over an alphabet of size at most $n^{1/\text{poly}\log\log n}$.Previous constructions that obtain $1/\text{poly}(n)$ soundness error usedeither $\text{poly}\log n $ queries or an exponential sized alphabet, i.e. ofsize $2^{n^c}$ for some $c>0$. Our result is an exponential improvement in bothparameters simultaneously.  Our result can be phrased as a polynomial-gap hardness for approximate CSPswith arity $\text{poly}\log\log n$ and alphabet size $n^{1/\text{poly}\log n}$.The ultimate goal, in this direction, would be to prove polynomial hardness forCSPs with constant arity and polynomial alphabet size (aka the sliding scaleconjecture for inverse polynomial soundness error).  Our construction is based on a modular generalization of previous PCPconstructions in this parameter regime, which involves a composition theoremthat uses an extra `consistency' query but maintains the inverse polynomialrelation between the soundness error and the alphabet size.  Our main technical/conceptual contribution is a new notion of soundness,which we refer to as {\em distributional soundness}, that replaces the previousnotion of "list decoding soundness", and that allows us to prove a modularcomposition theorem with tighter parameters. This new notion of soundnessallows us to invoke composition a super-constant number of times withoutincurring a blow-up in the soundness error.

Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition