Linear-time arguments with sublinear verification from tensor codes
Minimizing the computational cost of the prover is a central goal in the area of succinct
arguments. In particular, it remains a challenging open problem to construct a succinct …
arguments. In particular, it remains a challenging open problem to construct a succinct …
DEEP-FRI: sampling outside the box improves soundness
E Ben-Sasson, L Goldberg, S Kopparty… - arXiv preprint arXiv …, 2019 - arxiv.org
Motivated by the quest for scalable and succinct zero knowledge arguments, we revisit worst-
case-to-average-case reductions for linear spaces, raised by [Rothblum, Vadhan …
case-to-average-case reductions for linear spaces, raised by [Rothblum, Vadhan …
IOPs with inverse polynomial soundness error
We show that every language in NP has an Interactive Oracle Proof (IOP) with inverse
polynomial soundness error and small query complexity. This achieves parameters that …
polynomial soundness error and small query complexity. This achieves parameters that …
[图书][B] Property Testing: Problems and Techniques
A Bhattacharyya, Y Yoshida - 2022 - books.google.com
This book introduces important results and techniques in property testing, where the goal is
to design algorithms that decide whether their input satisfies a predetermined property in …
to design algorithms that decide whether their input satisfies a predetermined property in …
Interactive oracle proofs with constant rate and query complexity
E Ben-Sasson, A Chiesa, A Gabizon… - Cryptology ePrint …, 2016 - eprint.iacr.org
We study* interactive oracle proofs*(IOPs)[BCS16, RRR16], which combine aspects of
probabilistically checkable proofs (PCPs) and interactive proofs (IPs). We present IOP …
probabilistically checkable proofs (PCPs) and interactive proofs (IPs). We present IOP …
Worst-case to average case reductions for the distance to a code
E Ben-Sasson, S Kopparty, S Saraf - … Conference (CCC 2018), 2018 - drops.dagstuhl.de
Algebraic proof systems reduce computational problems to problems about estimating the
distance of a sequence of functions vec {u}=(u_1,..., u_k), given as oracles, from a linear …
distance of a sequence of functions vec {u}=(u_1,..., u_k), given as oracles, from a linear …
Quantum soundness of the classical low individual degree test
Z Ji, A Natarajan, T Vidick, J Wright, H Yuen - arXiv preprint arXiv …, 2020 - arxiv.org
Low degree tests play an important role in classical complexity theory, serving as basic
ingredients in foundational results such as $\mathsf {MIP}=\mathsf {NEXP} $[BFL91] and the …
ingredients in foundational results such as $\mathsf {MIP}=\mathsf {NEXP} $[BFL91] and the …
High-dimensional expansion of product codes is stronger than robust and agreement testability
G Kalachev - arXiv preprint arXiv:2308.02889, 2023 - arxiv.org
We study the coboundary expansion property of product codes called product expansion,
which played a key role in all recent constructions of good qLDPC codes. It was shown …
which played a key role in all recent constructions of good qLDPC codes. It was shown …
Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes
We consider the proximity testing problem for error-correcting codes which consist in
evaluations of multivariate polynomials either of bounded individual degree or bounded total …
evaluations of multivariate polynomials either of bounded individual degree or bounded total …
On axis-parallel tests for tensor product codes
Many low-degree tests examine the input function via its restrictions to random hyperplanes
of a certain dimension. Examples include the line-vs-line (Arora, Sudan 2003), plane-vs …
of a certain dimension. Examples include the line-vs-line (Arora, Sudan 2003), plane-vs …