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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We present an efficient proof system for Multipoint Arithmetic CircuitEvaluation: for every arithmetic circuit $C(x_1,\ldots,x_n)$ of size $s$ anddegree $d$ over a field ${\mathbb F}$, and any inputs $a_1,\ldots,a_K \in{\mathbb F}^n$,  $\bullet$ the Prover sends the Verifier the values $C(a_1), \ldots, C(a_K)\in {\mathbb F}$ and a proof of $\tilde{O}(K \cdot d)$ length, and  $\bullet$ the Verifier tosses $\textrm{poly}(\log(dK|{\mathbbF}|/\varepsilon))$ coins and can check the proof in about $\tilde{O}(K \cdot(n+ d) + s)$ time, with probability of error less than $\varepsilon$.  For small degree $d$, this "Merlin-Arthur" proof system (a.k.a. MA-proofsystem) runs in nearly-linear time, and has many applications. For example, weobtain MA-proof systems that run in $c^{n}$ time (for various $c < 2$) for thePermanent, $\#$Circuit-SAT for all sublinear-depth circuits, countingHamiltonian cycles, and infeasibility of $0$-$1$ linear programs. In general,the value of any polynomial in Valiant's class ${\sf VP}$ can be certifiedfaster than "exhaustive summation" over all possible assignments. These resultsstrongly refute a Merlin-Arthur Strong ETH and Arthur-Merlin Strong ETH posedby Russell Impagliazzo and others.  We also give a three-round (AMA) proof system for quantified Boolean formulasrunning in $2^{2n/3+o(n)}$ time, nearly-linear time MA-proof systems forcounting orthogonal vectors in a collection and finding Closest Pairs in theHamming metric, and a MA-proof system running in $n^{k/2+O(1)}$-time forcounting $k$-cliques in graphs.  We point to some potential future directions for refuting theNondeterministic Strong ETH.

Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation