Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #4 to TR19-023 | 28th January 2021 16:57

Smooth and Strong PCPs

RSS-Feed




Revision #4
Authors: Orr Paradise
Accepted on: 28th January 2021 16:57
Downloads: 567
Keywords: 


Abstract:

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:
- A PCP is *strong* if it rejects an alleged proof of a correct claim with probability proportional to its distance from some correct proof of that claim.
- A PCP is *smooth* if each location in a proof is queried with equal probability.

We prove that all sets in $\mathcal{NP}$ have a smooth and strong PCP of polynomial length that can be verified based on a constant number of queries. We do so by following the proof of the PCP theorem of Arora, Lund, Motwani, Sudan and Szegedy (JACM, 1998), providing a stronger analysis of the Hadamard and Reed--Muller based PCPs and a refined PCP composition theorem. In fact, we show that any set in $\mathcal{NP}$ has a smooth strong *canonical* PCP of Proximity (PCPP), meaning that there is an efficiently computable bijection of $\mathcal{NP}$ witnesses to correct proofs.

This improves on the recent result of Dinur, Gur and Goldreich (ITCS, 2019) that constructs strong canonical PCPPs that are inherently non-smooth. Our result implies the hardness of approximating the satisfiability of "stable" 3CNF formulae with bounded variable occurrence, proving a hypothesis used in the work of Friggstad, Khodamoradi and Salavatipour (SODA, 2019). Here *stability* means that the number of clauses violated by an assignment is proportional to its distance from a satisfying assignment (in the relative Hamming metric).



Changes to previous version:

In order of appearance:
- Changed "canonicality" to "canonicity".
- Section 1.0: Added another motivation for the study of smooth and strong PCPs in tandem.
- Added Remark 1.4 that replaces Appendix B.
- Added Remark 1.11 on previous appearances of the terms "Strong" and "Strong Canonical".
- Updated and expanded Section 1.3 (Related Work).
- Added Section 1.4.1 (Main Challenges) and updated the proof outline accordingly.
- Added Section 1.5 (Future Directions).
- Section 4: simplified the Hadamard PCPP construction to single-piece (instead of multi-piece)


Revision #3 to TR19-023 | 15th November 2019 23:44

Smooth and Strong PCPs





Revision #3
Authors: Orr Paradise
Accepted on: 15th November 2019 23:44
Downloads: 572
Keywords: 


Abstract:

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:
- A PCP is *strong* if it rejects an alleged proof of a correct claim with probability proportional to its distance from some correct proof of that claim.
- A PCP is *smooth* if each location in a proof is queried with equal probability.

We prove that all sets in $\mathcal{NP}$ have a smooth and strong PCP of polynomial length that can be verified based on a constant number of queries. We do so by following the proof of the PCP theorem of Arora, Lund, Motwani, Sudan and Szegedy (JACM, 1998), providing a stronger analysis of the Hadamard and Reed--Muller based PCPs and a refined PCP composition theorem. In fact, we show that any set in $\mathcal{NP}$ has a smooth strong *canonical* PCP of Proximity (PCPP), meaning that there is an efficiently computable bijection of $\mathcal{NP}$ witnesses to correct proofs.

This improves on the recent result of Dinur, Gur and Goldreich (ITCS, 2019) that constructs strong canonical PCPPs that are inherently non-smooth. Our result implies the hardness of approximating the satisfiability of "stable" 3CNF formulae with bounded variable occurrence, proving a hypothesis used in the work of Friggstad, Khodamoradi and Salavatipour (SODA, 2019). Here *stability* means that the number of clauses violated by an assignment is proportional to its distance from a satisfying assignment (in the relative Hamming metric).



Changes to previous version:

Re-added and updated author details.


Revision #2 to TR19-023 | 15th November 2019 23:39

Smooth and Strong PCPs





Revision #2
Authors: Orr Paradise
Accepted on: 15th November 2019 23:39
Downloads: 432
Keywords: 


Abstract:

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:
- A PCP is *strong* if it rejects an alleged proof of a correct claim with probability proportional to its distance from some correct proof of that claim.
- A PCP is *smooth* if each location in a proof is queried with equal probability.

We prove that all sets in NP have PCPs that are both smooth and strong, are of polynomial length, and can be verified based on a constant number of queries. This is achieved by following the proof of the PCP theorem of Arora, Lund, Motwani, Sudan and Szegedy (JACM, 1998), providing a stronger analysis of the Hadamard and Reed--Muller based PCPs and a refined PCP composition theorem. In fact, we show that any set in NP has a smooth strong *canonical* PCP of Proximity (PCPP), meaning that there is an efficiently computable bijection of NP witnesses to correct proofs. This improves on the recent construction of Dinur, Gur and Goldreich (ITCS, 2019) of PCPPs that are strong canonical but inherently non-smooth.

Our result implies the hardness of approximating the satisfiability of "stable" 3CNF formulae with bounded variable occurrence, where stable means that the number of clauses violated by an assignment is proportional to its distance from a satisfying assignment (in the relative Hamming metric). This proves a hypothesis used in the work of Friggstad, Khodamoradi and Salavatipour (SODA, 2019), suggesting a connection between the hardness of these instances and other stable optimization problems.



Changes to previous version:

- Fixed an issue with the smoothness of the construction of Section 5.3.
- Updated related work (Section 1.3.2).
- Other minor / typo fixes.


Revision #1 to TR19-023 | 1st September 2019 02:21

Smooth and Strong PCPs





Revision #1
Authors: Orr Paradise
Accepted on: 1st September 2019 02:21
Downloads: 535
Keywords: 


Abstract:

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:
* A PCP is *strong* if it rejects an alleged proof of a correct claim with probability proportional to its distance from some correct proof of that claim.
* A PCP is *smooth* if each location in a proof is queried with equal probability.

We prove that all sets in NP have PCPs that are both smooth and strong, are of polynomial length, and can be verified based on a constant number of queries. This is achieved by following the proof of the PCP theorem of Arora, Lund, Motwani, Sudan and Szegedy (JACM, 1998), providing a stronger analysis of the Hadamard and Reed--Muller based PCPs and a refined PCP composition theorem. In fact, we show that any set in NP has a smooth strong *canonical* PCP of Proximity (PCPP), meaning that there is an efficiently computable bijection of NP witnesses to correct proofs. This improves on the recent result of Dinur, Gur and Goldreich (ITCS, 2019) that constructs strong canonical PCPPs that are inherently non-smooth.

Our result implies the hardness of approximating the satisfiability of “stable” 3CNF formulae with bounded variable occurrence, where stable means that the number of clauses violated by an assignment is proportional to its distance from a satisfying assignment (in the relative Hamming metric). This proves a hypothesis used in the work of Friggstad, Khodamoradi and Salavatipour (SODA, 2019), suggesting a connection between the hardness of these instances and other stable optimization problems.



Changes to previous version:

Expanded the introduction (Section 1), most notably added a Related Work section (1.3), and a paragraph on the "distance oracle" to 1.2.2.

Fixed minor typos in the body of the work.

Updated acknowledgements.


Paper:

TR19-023 | 25th February 2019 19:48

Smooth and Strong PCPs





TR19-023
Authors: Orr Paradise
Publication: 26th February 2019 00:38
Downloads: 1209
Keywords: 


Abstract:

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:
- A PCP is *strong* if it rejects an alleged proof of a correct claim with probability proportional to its distance from some correct proof of that claim.
- A PCP is *smooth* if each location in a proof is queried with equal probability.

We prove that all sets in $\mathcal{NP}$ have a smooth and strong PCP of polynomial length that can be verified based on a constant number of queries. We do so by following the proof of the PCP theorem of Arora, Lund, Motwani, Sudan and Szegedy (JACM, 1998), providing a stronger analysis of the Hadamard and Reed--Muller based PCPs and a refined PCP composition theorem. In fact, we show that any set in $\mathcal{NP}$ has a smooth strong *canonical* PCP of Proximity (PCPP), meaning that there is an efficiently computable bijection of $\mathcal{NP}$ witnesses to correct proofs.

This improves on the recent result of Dinur, Gur and Goldreich (ITCS, 2019) that constructs strong canonical PCPPs that are inherently non-smooth. Our result implies the hardness of approximating the satisfiability of "stable" 3CNF formulae with bounded variable occurrence, proving a hypothesis used in the work of Friggstad, Khodamoradi and Salavatipour (SODA, 2019). Here *stability* means that the number of clauses violated by an assignment is proportional to its distance from a satisfying assignment (in the relative Hamming metric).



ISSN 1433-8092 | Imprint