Query-Efficient Dictatorship Testing with Perfect Completeness

1. Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. J. ACM 45(3), 501–555 (1998)

   Article  MathSciNet  MATH  Google Scholar 

2. Arora, S., Safra, S.: Probabilistic checking of proofs: a new characterization of NP. J. ACM 45(1), 70–122 (1998)

   Article  MathSciNet  MATH  Google Scholar 

3. Bellare, M., Goldreich, O., Sudan, M.: Free bits, PCPs, and nonapproximability–towards tight results. SIAM Journal on Computing 27(3), 804–915 (1998)

   Article  MathSciNet  MATH  Google Scholar 

4. Chen, V.: A hypergraph dictatorship test with perfect completeness. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX-RANDOM 2009. LNCS, vol. 5687, pp. 448–461. Springer, Heidelberg (2009)

   Chapter  Google Scholar 

5. Dinur, I., Mossel, E., Regev, O.: Conditional Hardness for Approximate Coloring. SIAM Journal on Computing 39(3), 843–873 (2009)

   Article  MathSciNet  MATH  Google Scholar 

6. Engebretsen, L., Holmerin, J.: More Efficient Queries in PCPs for NP and Improved Approximation Hardness of Maximum CSP. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol. 3404, pp. 194–205. Springer, Heidelberg (2005)

   Chapter  Google Scholar 

7. Gowers, W.T.: A new proof of Szemerédi’s theorem. Geom. Funct. Anal. 11(3), 465–588 (2001)

   Article  MathSciNet  MATH  Google Scholar 

8. Guruswami, V., Lewin, D., Sudan, M., Trevisan, L.: A tight characterization of NP with 3 query PCPs. In: FOCS, pp. 8–17 (1998)

   Google Scholar 

9. Håstad, J.: Some optimal inapproximability results. J. of ACM 48(4), 798–859 (2001)

   Article  MathSciNet  MATH  Google Scholar 

10. Håstad, J., Khot, S.: Query Efficient PCPs with Perfect Completeness. Theory of Computing 1(7), 119–148 (2005)

    Article  MathSciNet  MATH  Google Scholar 

11. Håstad, J., Wigderson, A.: Simple analysis of graph tests for linearity and PCP. Random Struct. Algorithms 22(2), 139–160 (2003)

    Article  MathSciNet  MATH  Google Scholar 

12. Khot, S.: On the power of unique 2-prover 1-round games. In: STOC, pp. 767–775 (2002)

    Google Scholar 

13. Khot, S., Kindler, G., Mossel, E., O’Donnell, R.: Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs? SIAM Journal on Computing 37(1), 319–357 (2007)

    Article  MathSciNet  MATH  Google Scholar 

14. Khot, S., Saket, R.: A 3-Query Non-Adaptive PCP with Perfect Completeness. In: CCC, pp. 159–169 (2006)

    Google Scholar 

15. O’Donnell, R., Wu, Y.: 3-bit dictator testing: 1 vs. 5/8. In: SODA, pp. 365–373 (2009)

    Google Scholar 

16. O’Donnell, R., Wu, Y.: Conditional Hardness for Satisfiable-3CSPs. In: STOC, pp. 493–502 (2009)

    Google Scholar 

17. Parnas, M., Ron, D., Samorodnitsky, A.: Testing Basic Boolean Formulae. SIAM Journal on Discrete Mathematics 16(1), 20–46 (2002)

    Article  MathSciNet  MATH  Google Scholar 

18. Raz, R.: A Parallel Repetition Theorem. SIAM Journal on Computing 27(3), 763–803 (1998)

    Article  MathSciNet  MATH  Google Scholar 

19. Samorodnitsky, A.: Low-degree tests at large distances. In: STOC, pp. 506–515 (2007)

    Google Scholar 

20. Samorodnitsky, A., Trevisan, L.: A PCP characterization of NP with optimal amortized query complexity. In: STOC, pp. 191–199 (2000)

    Google Scholar 

21. Samorodnitsky, A., Trevisan, L.: Gowers uniformity, influence of variables, and PCPs. SIAM Journal on Computing 39(1), 323–360 (2009)

    Article  MathSciNet  MATH  Google Scholar 

22. Sudan, M., Trevisan, L.: Probabilistically checkable proofs with low amortized query complexity. In: FOCS, pp. 18–27 (1998)

    Google Scholar 

23. Tamaki, S., Yoshida, Y.: A query efficient non-adaptive long code test with perfect completeness. ECCC, TR09-074 (2009)

    Google Scholar 

24. Tao, T.: Structure and randomness in combinatorics. In: FOCS, pp. 3–15 (2007)

    Google Scholar 

25. Trevisan, L.: Recycling queries in PCPs and in linearity tests (extended abstract). In: STOC, pp. 299–398 (1998)

    Google Scholar 

Download references