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].