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. [ .pdf ] |
| [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]. |
This file has been generated by bibtex2html 1.81.