Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with probabilistically checkable proofs:
TR97-003 | 29th January 1997
Sanjeev Arora, Madhu Sudan

Improved low-degree testing and its applications

NP = PCP(log n, 1) and related results crucially depend upon
the close connection between the probability with which a
function passes a ``low degree test'' and the distance of
this function to the nearest degree d polynomial. In this
paper we study a test ... more >>>

TR99-043 | 5th November 1999
Venkatesan Guruswami

The Approximability of Set Splitting Problems and Satisfiability Problems with no Mixed Clauses

We prove hardness results for approximating set splitting problems and
also instances of satisfiability problems which have no ``mixed'' clauses,
i.e all clauses have either all their literals unnegated or all of them
negated. Recent results of Hastad imply tight hardness results for set
splitting when all sets ... more >>>

TR17-057 | 7th April 2017
Alessandro Chiesa, Michael Forbes, Nicholas Spooner

A Zero Knowledge Sumcheck and its Applications

Many seminal results in Interactive Proofs (IPs) use algebraic techniques based on low-degree polynomials, the study of which is pervasive in theoretical computer science. Unfortunately, known methods for endowing such proofs with zero knowledge guarantees do not retain this rich algebraic structure.

In this work, we develop algebraic techniques for ... more >>>

TR19-023 | 25th February 2019
Orr Paradise

Smooth and Strong PCPs

Revisions: 3

Probabilistically checkable proofs (PCPs) can be verified based only on a constant amount of random queries, such that any correct claim has a proof that is always accepted, and incorrect claims are rejected with high probability (regardless of the given alleged proof). We consider two possible features of PCPs:
- ... more >>>

ISSN 1433-8092 | Imprint