Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.
KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.
2005 (English)In: STACS 2005, PROCEEDINGS / [ed] Diekert, V; Durand, B, 2005, Vol. 3404, 194-205 p.Conference paper, Published paper (Refereed)
Abstract [en]

In the PCP model, a verifier is supposed to probabilistically decide if a given input belongs to some language by posing queries to a purported proof of this fact. The probability that the verifier accepts an input in the language given a correct proof is called the completeness C; the probability that the verifier rejects an input not in the language given any proof is called the soundness s. For a verifier posing q queries to the proof, the amortized query complexity is defined by q/log(2) (c/s) if the proof is coded in binary. It is a measure of the average "efficiency" of the queries in the following sense: An ideal query should preserve the completeness and halve the soundness. If this were the case for all queries, the amortized query complexity would be exactly one. Samorodnitsky and Trevisan [STOC 2000] gave a q-query PCP for NP with amortized query complexity 1 + 2/root q + epsilon for any constant epsilon > 0. In this paper, we examine to what extent their result can be sharpened. Using the layered label cover problem recently introduced by Dinur et al. [STOC 2003], we devise a new "outer verifier" that allows us to construct an "inner verifier" that uses the query bits more efficiently than earlier verifiers. This enables us to construct a PCP for NP that queries q positions in the proof and has amortized query complexity 1 + root 2/q + epsilon. As an immediate corollary, we also obtain an improved hardness of approximation result for the Maximum q-CSP problem. Since the improvement compared to previous work is moderate, we then examine if there is an underlying reason for this. Our construction in this paper follows a paradigm for query efficient PCPs for NP outlined by many previous researchers and it combines a state-of-the-art "outer verifier" with a natural candidate for a query efficient "inner verifier". We prove in the full version of this paper that all natural attempts to construct more query efficient versions of our verifier are doomed to fail. This implies that significantly new ideas regarding proof composition and A encoding of PCP proofs are required to construct PCPs for NP that are more query efficient than the one we propose in his paper.

Place, publisher, year, edition, pages
2005. Vol. 3404, 194-205 p.
Series
LECTURE NOTES IN COMPUTER SCIENCE, ISSN 0302-9743 ; 3404
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-42742ISI: 000229009500016Scopus ID: 2-s2.0-24144452190ISBN: 3-540-24998-2 (print)OAI: oai:DiVA.org:kth-42742DiVA: diva2:447958
Conference
22nd Annual Symposium on Theoretical Aspects of Computer Science Location: Stuttgart, GERMANY Date: FEB 24-26, 2005
Note
QC 20111013Available from: 2011-10-13 Created: 2011-10-12 Last updated: 2011-10-13Bibliographically approved

Open Access in DiVA

No full text

Scopus

Search in DiVA

By author/editor
Engebretsen, LarsHolmerin, Jonas
By organisation
Numerical Analysis and Computer Science, NADA
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 63 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf