Article

Free access

Recycling queries in PCPs and in linearity tests (extended abstract)

Author:

Luca TrevisanAuthors Info & Claims

STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computing

Pages 299 - 308

https://doi.org/10.1145/276698.276769

Published: 23 May 1998 Publication History

PDF eReader

References

[1]

S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. In Proc. of the 33rd IEEE FOCS, pages 14-23, 1992.]]

Digital Library

Google Scholar

[2]

S. Arora and S. Safra. Probabilistic checking of proofs; a new characterization of NP. In Proc. ofthe 33rdlEEE FOCS, pages 2-13, 1992.]]

Digital Library

Google Scholar

[3]

M. Bellare. Proof checking and approximation: Towards fight results. Sigact News, 27(1), 1996.]]

Google Scholar

[4]

M. Bellare, D. Coppersmith, J. H~stad, M. Kiwi, and M. Sudan. Linearity testing over characteristic two. IEEE Trans. on Information Theory, 42(6): 1781-1795, 1996.]]

Crossref

Google Scholar

[5]

M. Bellare, O. Goldreich, and M. Sudan. Free bits, PCP's and non-approximability- towards fight results (5th version). Technical Report TR95-24, Electronic Colloquium on Computational Complexity, 1997. Preliminary version in Proc. of FOCS'95.]]

Digital Library

Google Scholar

[6]

M Bellare, S. Goldwasser, C. Lund, and A. Russell. Efficient probabilistically checkable proofs and applications to approximation. In Proc. of the 25th ACM STOC, pages 294-304, 1993. See also the errata sheet in Proc of STOC'94.]]

Crossref

Google Scholar

[7]

M. Bellare and M. Sudan. improved nonapproximability results. In Proc. of the 26th ACM STOC, pages 184-193, 1994.]]

Digital Library

Google Scholar

[8]

M. Blum, M. Luby, and R. Rubinfeld. Selftesting/correcting with applications to numerical problems. in Proc. of the 22nd ACM STOC, pages 73-83, 1990.]]

Digital Library

Google Scholar

[9]

D. Coppersmith. Unpublished notes, 1990.]]

Google Scholar

[10]

N. Creignou. A dichotomy theorem for maximum generalized satisfiability problems. JC$S, 51(3):511-522, 1995.]]

Digital Library

Google Scholar

[11]

J. H'3stad. Testing of the long code and hardness for clique. In Proc. of the 28th ACM STOC, pages 11-19, 1996.]]

Digital Library

Google Scholar

[12]

J. H'lstad. Clique is hard to approximate within nl-`. Technical Report TR97-38, Electronic Colloquium on Computational Complexity, 1997. Preliminary version in Proc. of FOCS'96.]]

Digital Library

Google Scholar

[13]

J. H'lstad. Some optimal inapproximability resuks. In Proc. of the 29thACM STOC, pages 1-10, 1997.]]

Digital Library

Google Scholar

[14]

B. Karloff and U. Zwiek. A (7/8 - ~)-approximation algorithm for MAX 3SAT? In Proc. of the 38th IEEE FOCS, 1997.]]

Digital Library

Google Scholar

[15]

S. Khanna, R. Motwani, M. Sudan, and U. Vazirani. On syntactic versus computational views of approximability. In Proc. of the 35th IEEE FOC$, pages 819-830, 1994.]]

Digital Library

Google Scholar

[16]

S. Khanna, M. Sudan, and D.P. Williamson. A complete classification of the approximability of maximization problems derived from boolean constraint satisfaction. In Proc. of the 29th ACM STOC, pages 11-20, 1997.]]

Digital Library

Google Scholar

[17]

M. Kiwi. Probabilistically Checkable Proofs and the Testing of Hadamard-like Codes. PhD thesis, MIT, 1996.]]

Digital Library

Google Scholar

[18]

C. H. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes. JC$$, 43:425- 440, 1991. Preliminary version in Proc. of STOC'88.]]

Digital Library

Google Scholar

[19]

R. Raz. A parallel repetition theorem. In Proc. of the 27th ACM STOC, pages 447-456, 1995.]]

Digital Library

Google Scholar

[20]

M. Seres, L. Trevisan, and E Xhafa. The parallel approximability of non-boolean constraint satisfaction and restricted integer linear programming. In Proc. of the 15th STACS, 1998. To appear.]]

Google Scholar

[21]

M. Sudan and L. Trevisan. Unpublished Notes, February 1998.]]

Google Scholar

[22]

L. Trevisan. Positive linear programming, parallel approximation, and PCP's. In Proc. of the 4th ESA, pages 62-75. LNCS t 136, Springer-Vefiag, 1996.]]

Digital Library

Google Scholar

[23]

L. Trevisan. Approximating satisfiable satisfiability problems. In Proc. of the 5th ESA, pages 472-485. LNCS 1284, Spdnger-Vedag, 1997.]]

Digital Library

Google Scholar

[24]

L. Trevisan. Recycling queries in PCPs and in linearity tests. Technical Report TR98-07, Electronic Colloquium on Computational Complexity, January 1998.]]

Google Scholar

[25]

L. Trevisan, G.B. Sorkin, M. Sudan, and D.P. Williamson. Gadgets, approximation, and linear programming. In Proc. of the 37th iEEE FOC$, pages 617-626, 1996.]]

Digital Library

Google Scholar

[26]

U. Zwick. Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint. In Proc. of the 9th ACM-SIAM SODA, 1998.]]

Digital Library

Google Scholar

Cited By

View all

Chan S(2016)Approximation Resistance from Pairwise-Independent SubgroupsJournal of the ACM10.1145/287305463:3(1-32)Online publication date: 12-Aug-2016
https://dl.acm.org/doi/10.1145/2873054
Devadas SRubinfeld R(2016)A Self-Tester for Linear Functions over the Integers with an Elementary Proof of CorrectnessTheory of Computing Systems10.1007/s00224-015-9639-z59:1(99-111)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1007/s00224-015-9639-z
Chan SBoneh DRoughgarden TFeigenbaum J(2013)Approximation resistance from pairwise independent subgroupsProceedings of the forty-fifth annual ACM symposium on Theory of Computing10.1145/2488608.2488665(447-456)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1145/2488608.2488665
Show More Cited By

Index Terms

Recycling queries in PCPs and in linearity tests (extended abstract)
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
  2. Models of computation
    1. Probabilistic computation

Recommendations

A Modified CMOS Balanced Output Transconductor with Extended Linearity

A new CMOS balanced output transconductor is presented. The circuit is based on applying the dynamic biasing technique on the floating current source to extend its linearity range. The difference in the biasing currents is compensated to maintain the ...
Combinatorial PCPs with Efficient Verifiers

The PCP theorem asserts the existence of proofs that can be verified by a verifier that reads only a very small part of the proof. The theorem was originally proved by Arora and Safra (J. ACM 45(1)) and Arora et al. (J. ACM 45(3)) using sophisticated ...
Infeasibility of instance compression and succinct PCPs for NP
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computing

The OR-SAT problem asks, given Boolean formulae Φ₁,...,Φ_m each of size at most n, whether at least one of the Φ_i's is satisfiable. We show that there is no reduction from OR-SAT to any set A where the length of the output is bounded by a polynomial in n,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computing

May 1998

684 pages

ISBN:0897919629

DOI:10.1145/276698

Chairman:
Jeffrey Vitter

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 May 1998

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC98

Sponsor:

SIGACT

STOC98: The 30th Annual ACM Symposium on Theory of Computing

May 24 - 26, 1998

Texas, Dallas, USA

Acceptance Rates

STOC '98 Paper Acceptance Rate 75 of 169 submissions, 44%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
289
Total Downloads

Downloads (Last 12 months)42
Downloads (Last 6 weeks)9

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chan S(2016)Approximation Resistance from Pairwise-Independent SubgroupsJournal of the ACM10.1145/287305463:3(1-32)Online publication date: 12-Aug-2016
https://dl.acm.org/doi/10.1145/2873054
Devadas SRubinfeld R(2016)A Self-Tester for Linear Functions over the Integers with an Elementary Proof of CorrectnessTheory of Computing Systems10.1007/s00224-015-9639-z59:1(99-111)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1007/s00224-015-9639-z
Chan SBoneh DRoughgarden TFeigenbaum J(2013)Approximation resistance from pairwise independent subgroupsProceedings of the forty-fifth annual ACM symposium on Theory of Computing10.1145/2488608.2488665(447-456)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1145/2488608.2488665
Chen V(2010)Query-efficient dictatorship testing with perfect completenessProperty testing10.5555/1986603.1986626(276-279)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1986603.1986626
Chen V(2010)Query-efficient dictatorship testing with perfect completenessProperty testing10.5555/1980617.1980640(276-279)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1980617.1980640
Tamaki SYoshida Y(2010)A query efficient non-adaptive long code test with perfect completenessProceedings of the 13th international conference on Approximation, and 14 the International conference on Randomization, and combinatorial optimization: algorithms and techniques10.5555/1886521.1886578(738-751)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.5555/1886521.1886578
Chen V(2010)Query-Efficient Dictatorship Testing with Perfect CompletenessProperty Testing10.1007/978-3-642-16367-8_20(276-279)Online publication date: 2010
https://doi.org/10.1007/978-3-642-16367-8_20
Tamaki SYoshida Y(2010)A Query Efficient Non-adaptive Long Code Test with Perfect CompletenessApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques10.1007/978-3-642-15369-3_55(738-751)Online publication date: 2010
https://doi.org/10.1007/978-3-642-15369-3_55
Chen V(2009)A Hypergraph Dictatorship Test with Perfect CompletenessProceedings of the 12th International Workshop and 13th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques10.1007/978-3-642-03685-9_34(448-461)Online publication date: 21-Aug-2009
https://dl.acm.org/doi/10.1007/978-3-642-03685-9_34
Engebretsen LHolmerin J(2008)More efficient queries in PCPs for NP and improved approximation hardness of maximum CSPRandom Structures & Algorithms10.5555/1458645.145864733:4(497-514)Online publication date: 1-Dec-2008
https://dl.acm.org/doi/10.5555/1458645.1458647
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A Modified CMOS Balanced Output Transconductor with Extended Linearity

Combinatorial PCPs with Efficient Verifiers

Infeasibility of instance compression and succinct PCPs for NP