Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity.

Eli Ben-Sasson Yohay Kaplan Swastik Kopparty Or Meir Henning Stichtenoth

Published in: J. ACM (2016)

Keyphrases

query complexity
data complexity
membership queries
satisfiability problem
sat solvers
vc dimension
dnf formulas
concept class
database
learning algorithm
upper bound
expressive power
query evaluation
uniform distribution
pac learning
exact learning