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

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

Published in: FOCS (2013)

Keyphrases

query complexity
data complexity
membership queries
sat solvers
expressive power
concept class
exact learning
learning algorithm
database systems
special case
positive and negative
conjunctive queries
resource consumption
boolean formula
dnf formulas