Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
From MaRDI portal
Recommendations
- On O(Tlog T) reduction from RAM computations to satisfiability
- Fast and parallel decomposition of constraint satisfaction problems
- On the efficient approximability of constraint satisfaction problems
- Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems
- Sparsification of SAT and CSP Problems via Tractable Extensions
- Reoptimization of constraint satisfaction problems with approximation resistant predicates
- The approximability of constraint satisfaction problems
- New schemes for simplifying binary constraint satisfaction problems
- An efficient algorithm for a class of constraint satisfaction problems
Cites work
- A model of interactive teaching
- A theory of goal-oriented communication
- A theory of the learnable
- Algorithmic Learning Theory
- Derandomizing polynomial identity tests means proving circuit lower bounds
- scientific article; zbMATH DE number 3154781 (Why is no real title available?)
- scientific article; zbMATH DE number 67625 (Why is no real title available?)
- scientific article; zbMATH DE number 67631 (Why is no real title available?)
- scientific article; zbMATH DE number 1559537 (Why is no real title available?)
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Learning from different teachers
- Measuring teachability using variants of the teaching dimension
- Models of cooperative teaching and learning
- Occam's razor
- On specifying Boolean functions by labelled examples
- On the complexity of teaching
- On the limits of efficient teachability
- On the power of inductive inference from good examples
- Pseudorandom generators for space-bounded computation
- Recent Developments in Algorithmic Teaching
- Teachability in computational learning
- Teaching a smarter learner.
- Teaching Randomized Learners
Cited in
(23)- Local reduction
- Scalable zero knowledge via cycles of elliptic curves
- Spartan: efficient and general-purpose zkSNARKs without trusted setup
- \textsf{Halo Infinite}: proof-carrying data from additive polynomial commitments
- Succinct non-interactive arguments via linear interactive proofs
- Preprocessing succinct non-interactive arguments for rank-1 constraint satisfiability from holographic proofs
- Linear-size constant-query IOPs for delegating computation
- Quasi-linear size zero knowledge from linear-algebraic PCPs
- Local reductions
- Shorter arithmetization of nondeterministic computations
- Computational integrity with a public random string from quasi-linear PCPs
- SPARKs: Succinct Parallelizable Arguments of Knowledge
- PrORAM
- 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
- Fiat-Shamir security of FRI and related SNARKs
- Polynomial IOPs for memory consistency checks in zero-knowledge virtual machines
- Probabilistically checkable arguments for all NP
- Public-coin, complexity-preserving, succinct arguments of knowledge for NP from collision-resistance
- On soundness notions for interactive oracle proofs
- On O(Tlog T) reduction from RAM computations to satisfiability
This page was built for publication: Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986889)
