Fast reductions from RAMs to delegatable succinct constraint satisfaction problems

DOI10.1145/2422436.2422481zbMath1361.68088OpenAlexW1971029566MaRDI QIDQ2986889

Eran Tromer, Eli Ben-Sasson, Daniel Genkin, Alessandro Chiesa

Publication date: 16 May 2017

Published in: Proceedings of the 4th conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2422436.2422481

zbMATH Keywords

zero-knowledge proofsprobabilistically checkable proofsdelegation of computationsuccinct argumentsrandom-access machines

Mathematics Subject Classification ID

Related Items (16)

\textsf{Halo Infinite}: proof-carrying data from additive polynomial commitments ⋮ Local Reductions ⋮ Succinct non-interactive arguments via linear interactive proofs ⋮ Local reduction ⋮ Preprocessing succinct non-interactive arguments for rank-1 constraint satisfiability from holographic proofs ⋮ Linear-size constant-query IOPs for delegating computation ⋮ PrORAM ⋮ Scalable zero knowledge via cycles of elliptic curves ⋮ Succinct arguments for RAM programs via projection codes ⋮ Brakedown: linear-time and field-agnostic SNARKs for R1CS ⋮ Proofs for inner pairing products and applications ⋮ On black-box constructions of time and space efficient sublinear arguments from symmetric-key primitives ⋮ Shorter arithmetization of nondeterministic computations ⋮ Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs ⋮ Spartan: efficient and general-purpose zkSNARKs without trusted setup ⋮ Computational Integrity with a Public Random String from Quasi-Linear PCPs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Teachability in computational learning
• Measuring teachability using variants of the teaching dimension
• Teaching a smarter learner.
• Occam's razor
• Pseudorandom generators for space-bounded computation
• On the power of inductive inference from good examples
• A model of interactive teaching
• Learning from different teachers
• On the limits of efficient teachability
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• On the complexity of teaching
• On specifying Boolean functions by labelled examples
• Recent Developments in Algorithmic Teaching
• A theory of the learnable
• Teaching Randomized Learners
• Algorithmic Learning Theory
• A theory of goal-oriented communication
• Derandomizing polynomial identity tests means proving circuit lower bounds

This page was built for publication: Fast reductions from RAMs to delegatable succinct constraint satisfaction problems