Alex Samorodnitsky
- 1.S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. Journal of the A CM, 45(3):501-555, 1998. Preliminary version in Proc. of FOCS'92. Google Scholar
Digital Library
- 2.S. Arora and S. Safra. Probabilistic checking of proofs: A new characterization of NP. Journal of the A CM, 45(1):70-122, 1998. Preliminary version in Proc. of FOCS'92. Google ScholarDigital Library
- 3.S. Arora and M. Sudan. Improved low degree testing and its applications. In Proceedings of the 29th A CM Symposium on Theory of Computing, pages 485-495, 1997. Google ScholarDigital Library
- 4.M. Bellare. Proof checking and approximation: Towards tight results. Sigact News, 27(1), 1996.Google Scholar
- 5.M. Bellare, O. Goldreich, and M. Sudan. Free bits, PCP's and non-approximability- towards tight results. SIAM Journal on Computing, 27(3):804-915, 1998. Preliminary version in Proc. of FOCS'95. Google ScholarDigital Library
- 6.M. Bellare, S. Goldwasser, C. Lund, and A. Russell. Efficient probabilistically checkable proofs and applications to approximation. In Proceedings of the 25th A CM Symposium on Theory of Computing, pages 294-304, 1993. See also the errata sheet in Proc of STOC'9J. Google ScholarDigital Library
- 7.M. Bellare and M. Sudan. Improved nonapproximability results. In Proceedings of the 26th A CM Symposium on Theory of Computing, pages 184-193, 1994. Google ScholarDigital Library
- 8.M. Blum, M. Luby, and R. P~ubinfeld. Selftesting/correcting with applications to numerical problems. In Proceedings of the 22nd A CM Symposium on Theory of Computing, pages 73-83, 1990. Google ScholarDigital Library
- 9.N. Creignou. A dichotomy theorem for maximum generalized satisfiability problems, journal of Computer and System Sciences, 51(3):511-522, 1995. Google ScholarDigital Library
- 10.I. Dinur, E. Fischer, G. Kindler, R. Raz, and S. Safra. PCP characterizations of NP: Towards a polynomiallysmall error-probability. In Proceedings of the 31st A CM Symposium' on Theory of Computing, pages 29-40, 1999. Google ScholarDigital Library
- 11.U. Feige, S. Goldwasser, L. Lovfisz, S. Safra, and M. Szegedy. Approximating clique is almost NP- complete. In Proceedings of the 32nd IEEE Symposium on Foundations of Computer Science, pages 2-12, 1991. Google ScholarDigital Library
- 12.U. Feige and J. Kilian. Two prover protocols - low error at affordable rates. In Proceedings of the 26th A CM Symposium on Theory of Computing, pages 172-183, 1994. Google ScholarDigital Library
- 13.J. H~tad. Clique is hard to approximate within nl-c In Proceedings of the 37th IEEE Symposium on Foundations of Computer Science, pages 627-636, 1996. Google ScholarDigital Library
- 14.j. H~tad. Some optimal inapproximability results. In Proceedings of the 29th A CM Symposium on Theory of Computing, pages 1-10, 1997. Google ScholarDigital Library
- 15.S. Khanna, I{. Motwani, M. Sudan, and U. Vazirani. On syntactic versus computational views of approximability. SIAM Journal on Computing, 28(1):164-191, 1999. Preliminary version in Proc. of FOC3'94. Google ScholarDigital Library
- 16.S. Khanna, M. Sudan, and D. Williamson. A complete classification of the approximability of maximization problems derived from boolean constraint satisfaction.' In Proceedings of the 29th A CM Symposium on Theory of Computing, pages 11-20, 1997. Google ScholarDigital Library
- 17.R. Raz and S. Safra. A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In Proceedings of the 29th A CM Symposium on Theory of Computing, pages 475- 484, 1997. Google ScholarDigital Library
- 18.M. Serna, L. Trevisan, and F. Xhafa. The parallel approximability of non-boolean constraint satisfaction and restricted integer linear programming. In Proceedings of the 15th Symposium on Theoretical Aspects of Computer Science, pages 488-498. LNCS 1373, Springer-Verlag, 1998. Google ScholarDigital Library
- 19.M. Sudan and L. Trevisan. Probabilistically checkable proofs with low amortized query complexity. In Proceedings of the 39th IEEE Symposium on Foundations of Computer Science, 1998. Google ScholarDigital Library
- 20.L. Trevisan. Positive linear programming, parallel approximation, and PCP's. In Proceedings of the dth European Symposium on Algorithms, pages 62-75. LNCS 1136, Springer-Verlag, 1996. Google ScholarDigital Library
- 21.L. Trevisan. Approximating satisfiable satisfiability problems. In Proceedings of the 5th European Symposium on Algorithms, pages 472-485. LNCS 1284, Springer-Verlag, 1997. Google ScholarDigital Library
- 22.L. Trevisan. Recycling queries in PCPs and in linearity tests. In Proceedings of the 30th A CM Symposium on Theory of Computing, 1998. Google ScholarDigital Library
- 23.L. Trevisan, G. Sorkin, M. Sudan, and D. Williamson. Gadgets, approximation, and linear programming. In Proceedings of the 37th IEEE Symposium on Foundations of Computer Science, pages 617-626, 1996. Google ScholarDigital Library
- 24.U. Zwick. Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint. In Proceedings of the 9th A CM-$IAM Symposium on Discrete Algorithms, 1998. Google ScholarDigital Library
- 25.U. Zwick. Finding almost satisfying assignment. In Proceedings of the 30th A CM Symposium on Theory of Computing, 1998. Google ScholarDigital Library
Index Terms
- A PCP characterization of NP with optimal amortized query complexity
Recommendations
A Tight Characterization of NP with 3 Query PCPs
FOCS '98: Proceedings of the 39th Annual Symposium on Foundations of Computer ScienceIt is known that there exists a PCP characterization of NP where the verifier makes 3 queries and has a one-sided error that is bounded away from 1; and also that 2 queries do not suffice for such a characterization. Thus PCPs with 3 queries possess non-...
Two-query PCP with subconstant error
We show that the NP-Complete language 3Sat has a PCP verifier that makes two queries to a proof of almost-linear size and achieves subconstant probability of error ε=o(1). The verifier performs only projection tests, meaning that the answer to the first ...
Two Query PCP with Sub-Constant Error
FOCS '08: Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer ScienceWe show that the NP-Complete language 3Sat has a PCPverifier that makes two queries to a proof of almost-linear size and achieves sub-constant probability of error o(1). The verifier performs only projection tests, meaning that the answer to the first ...
Comments