Towards an optimal query efficient PCP? (English) Zbl 1361.68099
Proceedings of the 4th conference on innovations in theoretical computer science, ITCS’13, Berkeley, CA, USA, January 9–12, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-1859-4). 173-186 (2013).
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 05C65 | Hypergraphs |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn, and D. Ron. Testing Reed-Muller codes. IEEE Transactions on Information Theory, 51(11):4032-4039, 2005. 10.1109/TIT.2005.856958 · Zbl 1247.94057 |
| [2] | N. Alon and J. Spencer. The Probabilistic Method. Wiley, 2008. · Zbl 1148.05001 |
| [3] | S. Arora, C. Lund, R. Motawani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501-555, 1998. 10.1145/278298.278306 · Zbl 1065.68570 |
| [4] | S. Arora and S. Safra. Probabilistic checking of proofs : A new characterization of \(\mboxNP \). Journal of the ACM, 45(1):70-122, 1998. 10.1145/273865.273901 · Zbl 0903.68076 |
| [5] | M. Blum, M. Luby, and R. Rubinfeld. Self-testing/correcting with applications to numerical problems. J. Comput. Syst. Sci., 47(3):549-595, 1993. 10.1016/0022-0000(93)90044-W · Zbl 0795.68131 |
| [6] | S. O. Chan. Personal Communication, 2012. |
| [7] | M. Charikar, K. Makarychev, and Y. Makarychev. Near-optimal algorithms for unique games. In Proc. ACM Symposium on the Theory of Computing, pages 205-214, 2006. 10.1145/1132516.1132547 · Zbl 1301.68267 |
| [8] | L. Engebretsen and J. Holmerin. More efficient queries in pcps for np and improved approximation hardness of maximum csp. Random Struct. Algorithms, 33(4):497-514, 2008. 10.1002/rsa.v33:4 · Zbl 1159.68033 |
| [9] | U. Feige, S. Goldwasser, L. Lovász, S. Safra, and M. Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the ACM, 43(2):268-292, 1996. 10.1145/226643.226652 · Zbl 0882.68129 |
| [10] | J. Hastad. Clique is hard to approximate within n1-ε. Acta Mathematica, 182:105-142, 1999. · Zbl 0989.68060 |
| [11] | J. Hastad. Some optimal inapproximability results. Journal of ACM, 48:798-859, 2001. 10.1145/502090.502098 · Zbl 1127.68405 |
| [12] | J. Hastad and A. Wigderson. Simple analysis of graph tests for linearity andmboxPCP. In Proc. 16th IEEE Conference on Computational Complexity, 2001. |
| [13] | T. Holenstein. Parallel repetition: simplifications and the no-signaling case. In Proc. ACM Symposium on the Theory of Computing, pages 411-419, 2007. 10.1145/1250790.1250852 · Zbl 1211.68211 |
| [14] | S. Khot. On the power of unique 2-prover 1-round games. In Proc. 34th ACM Symposium on Theory of Computing, 2002. 10.1145/509907.510017 · Zbl 1192.68367 |
| [15] | S. Khot, G. Kindler, E. Mossel, and R. O’Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput., 37(1):319-357, 2007. 10.1137/S0097539705447372 · Zbl 1135.68019 |
| [16] | S. Khot and M. Safra. A two prover one round game with strong soundness. In Proceedings of the 52nd IEEE Symposium on Foundations of Computer Science, pages 648-657, 2011. 10.1109/FOCS.2011.62 · Zbl 1292.68075 |
| [17] | E. Mossel, R. O’Donnell, and K. Oleszkiewicz. Noise stability of functions with low influences: invariance and optimality. In Proc. 46th IEEE Symposium on Foundations of Computer Science, pages 21-30, 2005. 10.1109/SFCS.2005.53 |
| [18] | A. Rao. Parallel repetition in projection games and a concentration bound. In Proc. ACM Symposium on the Theory of Computing, pages 1-10, 2008. 10.1145/1374376.1374378 |
| [19] | R. Raz. A parallel repetition theorem. SIAM J. of Computing, 27(3):763-803, 1998. 10.1137/S0097539795280895 · Zbl 0911.68082 |
| [20] | A. Samorodnitsky. Low-degree tests at large distances. In Proceedings of the 39th ACM Symposium on Theory of Computing, pages 506-515, 2007. 10.1145/1250790.1250864 · Zbl 1232.68175 |
| [21] | A. Samorodnitsky and L. Trevisan. AmboxPCP characterization ofmboxNP with optimal amortized query complexity. In Proc. 32nd ACM Symposium on Theory of Computing, pages 191-199, 2000. 10.1145/335305.335329 · Zbl 1296.68060 |
| [22] | A. Samorodnitsky and L. Trevisan. Gowers uniformity, influence of variables, and PCPs. In Proc. 38th ACM Symposium on Theory of Computing, 2006. 10.1145/1132516.1132519 · Zbl 1301.68137 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
