Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Orr Paradise:

TR20-075 | 6th May 2020
Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal

Rigid Matrices From Rectangular PCPs

Revisions: 2

We introduce a variant of PCPs, that we refer to as *rectangular* PCPs, wherein proofs are thought of as square matrices, and the random coins used by the verifier can be partitioned into two disjoint sets, one determining the *row* of each query and the other determining the *column*.

We ... more >>>

TR19-023 | 25th February 2019
Orr Paradise

Smooth and Strong PCPs

Revisions: 4

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