Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
type: Item
instance of: scholarly article
title: Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
zbMATH Open document ID: 1361.68088
DOI: 10.1145/2422436.2422481
author: Eli Ben-Sasson
author: Alessandro Chiesa
author: Daniel Genkin
author: Eran Tromer
published in: Proceedings of the 4th conference on Innovations in Theoretical Computer Science
publication date: 2017-05-16T00:00:00Z
Mathematics Subject Classification ID: 68Q10
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 6718205
zbMATH Keywords: delegation of computation
zbMATH Keywords: probabilistically checkable proofs
zbMATH Keywords: random-access machines
zbMATH Keywords: succinct arguments
zbMATH Keywords: zero-knowledge proofs
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1145/2422436.2422481
OpenAlex ID: W1971029566
cites work: Learning from different teachers
cites work: On specifying Boolean functions by labelled examples
cites work: Measuring teachability using variants of the teaching dimension
cites work: Algorithmic Learning Theory
cites work: Teaching Randomized Learners
cites work: Recent Developments in Algorithmic Teaching
cites work: Occam's razor
cites work: Q4013552
cites work: On the power of inductive inference from good examples
cites work: Q3272460
cites work: On the complexity of teaching
cites work: Teaching a smarter learner.
cites work: A theory of goal-oriented communication
cites work: In search of an easy witness: Exponential time vs. probabilistic polynomial time.
cites work: Q4526985
cites work: Derandomizing polynomial identity tests means proving circuit lower bounds
cites work: Q4013545
cites work: A model of interactive teaching
cites work: Pseudorandom generators for space-bounded computation
cites work: On the limits of efficient teachability
cites work: Teachability in computational learning
cites work: A theory of the learnable
cites work: Q5396611
Wikidata QID: Q130970249
Recommended article: On O(Tlog T) reduction from RAM computations to satisfiability
Recommended article: Fast and parallel decomposition of constraint satisfaction problems
Recommended article: Q5421814
Recommended article: Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems
Recommended article: Sparsification of SAT and CSP Problems via Tractable Extensions
Recommended article: Reoptimization of constraint satisfaction problems with approximation resistant predicates
Recommended article: The approximability of constraint satisfaction problems
Recommended article: New schemes for simplifying binary constraint satisfaction problems
Recommended article: An efficient algorithm for a class of constraint satisfaction problems
description: scientific article