Probabilistically checkable proofs by Sudan, Madhu

“…In this article we explain this notion, constructions of such probabilistically checkable proofs, and why this is important to all of combinatorial optimization.…”
Get full text

Implementing Probabilistically Checkable Proofs of Proximity by Bhattacharyya, Arnab

“…Abstract: In this paper, we describe a proof-of-concept implementation of the probabilistically checkable proof of proximity (PCPP) system described by Ben-Sasson and Sudan in \\cite{bs05}. …”
Get full text

Digital signatures from probabilistically checkable proofs by Sidney, Raymond M. (Raymond Mark)

Get full text

Probabilistically checkable proofs and the testing of Hadamard-like codes by Kiwi, Marcos

Get full text

Incrementally verifiable computation or knowledge implies time/space efficiency by Valiant, Paul (Paul Andrew)

Get full text

Imperfect gaps in Gap-ETH and PCPs by Vyas, Nikhil(Electrical engineer and computer scientist)Massachusetts Institute of Technology.

Get full text

Product-State Approximations to Quantum States by Brandão, Fernando G. S. L., Harrow, Aram W

“…Our approximations allow an extensive error in energy, which is the scale considered by the quantum PCP (probabilistically checkable proof) and NLTS (no low-energy trivial-state) conjectures. …”
Get full text
Get full text

Quantum Locally Testable Codes by Aharonov, Dorit, Eldar, Lior

“…Excellent LTCs exist in the classical world, and they are tightly related to the celebrated PCP (probabilistically checkable proof) theorem. In quantum complexity, quantum error correcting codes provide central examples in the study of the illusive behavior of multiparticle entanglement, and they have played a crucial role in many computational complexity results. …”
Get full text
Get full text

Robust PCPs of proximity and shorter PCPs by Harsha, Prahladh, 1976-

Get full text

PCPs for Arthur-Merlin games and communication protocols by Drucker, Andrew Donald

Get full text

Toward improved non-interactive proof systems by Kwon, Sophia Seoyoung

“…The study of non-interactive proof systems, such as Merlin-Arthur proof systems and probabilistically checkable proofs, can yield insights into problems for which we do not yet have efficient algorithms. …”
Get full text

Query-efficient checking of proofs and improved PCP characterizations of NP by Guruswami, Venkatesan, 1976-

Get full text

Small PCPs with low query complexity by Harsha, Prahladh, 1976-

Get full text

Distributed PCP Theorems for Hardness of Approximation in P by Abboud, Amir, Rubinstein, Aviad, Williams, Ryan

“…We present a new distributed} model of probabilistically checkable proofs (PCP). A satisfying assignment x ∈{0,1}^n to a CNF formula φ is shared between two parties, where Alice knows x-1, \dots, x-{n/2, Bob knows x-{n/2+1},\dots,x-n, and both parties know φ. …”
Get full text

New error correcting codes from lifting by Guo, Alan Xinyu

Get full text

Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity by Williams, Richard Ryan, Chen, Lijie

“…We apply Probabilistic Checkable Proofs of Proximity in a new way to show it would suffice to have a non-trivial CAPP algorithm for either 2 ◦ C, AND2 ◦ C or OR2 ◦ C. …”
Get full text

Locally Decodable Codes and Private Information Retrieval Schemes by Yekhanin, Sergey

Get full text