Tolerant Versus Intolerant Testing for Boolean Properties

by Eldar Fischer and Lance Fortnow

Theory of Computing, Volume 2(9), pp. 173-183, 2006

Bibliography with links to cited articles

[1]   N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy: Efficient testing of large graphs. Combinatorica, 20:451–476, 2000. [Combinatorica:mwapje2fdyk7ma2e].

[2]   N. Alon, M. Krivelevich, I. Newman, and M. Szegedy: Regular languages are testable with a constant number of queries. SIAM Journal on Computing, 30:1842–1862, 2001. [SICOMP:10.1137/S0097539700366528].

[3]   T. Batu, R. Rubinfeld, and P. White: Fast approximation PCPs for multidimensional bin-packing problems. Information and Computation, 196:42–56, 2005. [IandC:10.1016/j.ic.2004.10.001].

[4]   M. Bellare, O. Goldreich, and M. Sudan: Free bits, PCPs, and nonapproximability – towards tight results. SIAM Journal on Computing, 27:804–915, 1998. [SICOMP:10.1137/S0097539700366528].

[5]   E. Ben-Sasson, O. Goldreich, P. Harsha, M. Sudan, and S. Vadhan: Robust PCPs of proximity, shorter PCPs and applications to coding. In Proc. 36th STOC, pp. 1–10. ACM Press, 2004. [STOC:1007352.1007361].

[6]   E. Ben-Sasson, P. Harsha, and S. Raskhodnikova: Some 3CNF properties are hard to test. SIAM Journal on Computing, 35:1–21, 2005. [SICOMP:10.1137/S0097539704445445].

[7]   M. Blum, M. Luby, and R. Rubinfeld: Self-testing/correcting with applications to numerical problems. Journal of Computer and System Sciences, 47:549–595, 1993. [JCSS:10.1016/0022-0000(93)90044-W].

[8]   H. Buhrman, L. Fortnow, I. Newman, and H. Rohrig: Quantum property testing. In Proc. 14th ACM-SIAM Symp. on Discrete Algorithms (SODA’03), pp. 480–488. SIAM, 2003. [SODA:644108.644188].

[9]   F. Ergun, S. Kannan, R. Kumar, R. Rubinfeld, and M. Viswanathan: Spot checkers. Journal of Computer and System Sciences, 60:717–751, 2000. [JCSS:10.1006/jcss.1999.1692].

[10]   F. Ergun, R. Kumar, and R. Rubinfeld: Fast approximate probabilistically checkable proofs. Information and Computation, 189:135–159, 2004. [IandC:10.1016/j.ic.2003.09.005].

[11]   E. Fischer: The art of uninformed decisions: A primer to property testing. Bulletin of the European Association for Theoretical Computer Science, 75:97–126, 2001.

[12]   E. Fischer and L. Fortnow: Tolerant versus intolerant testing for Boolean properties. In Proc. 20th IEEE Conf. on Computational Complexity, pp. 135–140. IEEE Computer Society Press, 2005. [CCC:10.1109/CCC.2005.30].

[13]   E. Fischer, G. Kindler, D. Ron, S. Safra, and A. Samorodnitsky: Testing juntas. Journal of Computer and System Sciences, 68:753–787, 2004. [JCSS:10.1016/j.jcss.2003.11.004].

[14]   E. Fischer and I. Newman: Testing versus estimation of graph properties. In Proc. 37th STOC, pp. 138–146. ACM Press, 2005. [STOC:1060590.1060612].

[15]   E. Fischer, I. Newman, and J. Sgall: Functions that have read-twice constant width branching programs are not necessarily testable. Random Structures and Algorithms, 24:175–193, 2004. [RSA:10.1002/rsa.10110].

[16]   O. Goldreich, S. Goldwasser, and D. Ron: Property testing and its connection to learning and approximation. Journal of the ACM, 45:653–750, 1998. [JACM:285055.285060].

[17]   O. Goldreich and L. Trevisan: Three theorems regarding testing graph properties. Random Structures and Algorithms, 23:23–57, 2003. [RSA:10.1002/rsa.10078].

[18]   J. Håstad: Some optimal inapproximability results. Journal of the ACM, 48:798–859, 2001. [JACM:502090.502098].

[19]   M. Parnas, D. Ron, and R. Rubinfeld: Tolerant property testing and distance approximation. In ECCC, number TR04-010. 2004. [ECCC:TR04-010].

[20]   M. Parnas, D. Ron, and A. Samorodnitsky: Testing basic Boolean formulae. SIAM Journal on Discrete Mathematics, 16:20–46, 2002. [SIDMA:10.1137/S0895480101407444].

[21]   D. Ron: Property testing. In S. Rajasekaran, P. M. Pardalos, J. H. Reif, and J. D. P. Rolim, editors, Handbook of Randomized Computing, volume II, pp. 597–649. Kluwer, 2001.

[22]   R. Rubinfeld and M. Sudan: Robust characterization of polynomials with applications to program testing. SIAM Journal on Computing, 25:252–271, 1996. [SICOMP:10.1137/S0097539793255151].