Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > COMPLEXITY GAPS:
Reports tagged with Complexity Gaps:
TR18-024 | 1st February 2018
Olaf Beyersdorff, Judith Clymo, Stefan Dantchev, Barnaby Martin

#### The Riis Complexity Gap for QBF Resolution

We give an analogue of the Riis Complexity Gap Theorem for Quanti fied Boolean Formulas (QBFs). Every fi rst-order sentence $\phi$ without finite models gives rise to a sequence of QBFs whose minimal refutations in tree-like Q-Resolution are either of polynomial size (if $\phi$ has no models) or at least ... more >>>

TR20-058 | 24th April 2020
Shafi Goldwasser, Guy Rothblum, Jonathan Shafer, Amir Yehudayoff

#### Interactive Proofs for Verifying Machine Learning

Revisions: 1

We consider the following question: using a source of labeled data and interaction with an untrusted prover, what is the complexity of verifying that a given hypothesis is "approximately correct"? We study interactive proof systems for PAC verification, where a verifier that interacts with a prover is required to accept ... more >>>

ISSN 1433-8092 | Imprint