%% ToC#249, v002/a009.bib   Fischer - Fortnow

@article{aet,
author = "N. Alon and E. Fischer and M. Krivelevich and M. Szegedy",
title = "Efficient testing of large graphs",
journal = "Combinatorica",
volume = 20,
year = 2000,
pages = "451--476",
eprint="combinatorica:mwapje2fdyk7ma2e"}

@article{aer,
author = "N. Alon and M. Krivelevich and I. Newman and M. Szegedy",
title = "Regular languages are testable with a constant number of queries",
journal = "SIAM Journal on Computing",
volume = 30,
year = "2001",
pages = "1842--1862",
eprint="sicomp:10.1137/S0097539700366528"}

@article{brw,
author = "T. Batu and R. Rubinfeld and P. White",
title = "Fast approximation {PCP}s for multidimensional bin-packing problems",
journal = "Information and Computation",
volume = 196,
year = "2005",
pages = "42--56",
eprint="iandc:10.1016/j.ic.2004.10.001"}

@article{bgs,
author = "M. Bellare and O. Goldreich and M. Sudan",
title = "Free bits, {PCP}s, and nonapproximability -- towards tight results",
journal = "SIAM Journal on Computing",
volume = 27,
year = "1998",
pages = "804--915",
eprint="sicomp:10.1137/S0097539700366528"}

@incollection{bep,
author = "E. Ben-Sasson and O. Goldreich and P. Harsha and M. Sudan and S. Vadhan",
title = "Robust {PCP}s of Proximity, shorter {PCP}s and applications to coding",
booktitle = "Proc. $36^{th}$ STOC",
year = "2004",
pages = "1--10",
publisher = "{ACM Press}",
eprint="stoc:1007352.1007361"}

@article{bhr,
author = "E. Ben-Sasson and P. Harsha and S. Raskhodnikova",
title = "Some 3{CNF} properties are hard to test",
journal = "SIAM Journal on Computing",
volume = 35,
year = "2005",
pages = "1--21",
eprint="sicomp:10.1137/S0097539704445445"}

@article{blr,
author = "M. Blum and M. Luby and R. Rubinfeld",
title = "Self-testing/cor\-recting with applications to numerical problems",
journal = "Journal of Computer and System Sciences",
volume = 47,
year = "1993",
pages = "549--595",
eprint="jcss:10.1016/0022-0000(93)90044-W"}

@incollection{beq,
author = "H. Buhrman and L. Fortnow and I. Newman and H. Rohrig",
title = "Quantum property testing",
booktitle = "Proc. $14^{th}$ ACM-SIAM Symp. on Discrete Algorithms (SODA'03)",
year = "2003",
pages = "480--488",
publisher = "{SIAM}",
eprint="soda:644108.644188"}

@article{ees,
author = "F. Ergun and S. Kannan and R. Kumar and R. Rubinfeld and M. Viswanathan",
title = "Spot checkers",
journal = "Journal of Computer and System Sciences",
volume = 60,
year = "2000",
pages = "717--751",
eprint="jcss:10.1006/jcss.1999.1692"}

@article{ekr,
author = "F. Ergun and R. Kumar and R. Rubinfeld",
title = "Fast approximate probabilistically checkable proofs",
journal = "Information and Computation",
volume = 189,
year = "2004",
pages = "135--159",
eprint="iandc:10.1016/j.ic.2003.09.005"}

@article{fts,
author = "E. Fischer",
title = "The art of uninformed decisions: A primer to property testing",
journal = "Bulletin of the European Association for Theoretical Computer Science",
volume = 75,
year = "2001",
pages = "97--126"}

@article{fej,
author = "E. Fischer and G. Kindler and D. Ron and S. Safra and A. Samorodnitsky",
title = "Testing juntas",
journal = "Journal of Computer and System Sciences",
volume = 68,
year = "2004",
pages = "753--787",
eprint="jcss:10.1016/j.jcss.2003.11.004"}

@incollection{fne,
author = "E. Fischer and I. Newman",
title = "Testing versus estimation of graph properties",
booktitle = "Proc. $37^{th}$ STOC",
year = "2005",
pages = "138--146",
publisher = "{ACM Press}",
eprint="stoc:1060590.1060612"}

@article{fns,
author = "E. Fischer and I. Newman and J. Sgall",
title = "Functions that have read-twice constant width branching programs are not necessarily testable",
journal = "Random Structures and Algorithms",
volume = 24,
year = "2004",
pages = "175--193",
eprint="rsa:10.1002/rsa.10110"}

@article{ggr,
author = "O. Goldreich and S. Goldwasser and D. Ron",
title = "Property testing and its connection to learning and approximation",
journal = "Journal of the ACM",
volume = 45,
year = "1998",
pages = "653--750",
eprint="jacm:285055.285060"}

@article{gtt,
author = "O. Goldreich and L. Trevisan",
title = "Three theorems regarding testing graph properties",
journal = "Random Structures and Algorithms",
volume = 23,
year = "2003",
pages = "23--57",
eprint="rsa:10.1002/rsa.10078"}

@article{hoi,
author = "J. H{\aa}stad",
title = "Some optimal inapproximability results",
journal = "Journal of the ACM",
volume = 48,
year = "2001",
pages = "798--859",
eprint="jacm:502090.502098"}

@incollection{prr,
author = "M. Parnas and D. Ron and R. Rubinfeld",
title = "Tolerant property testing and distance approximation",
booktitle = "ECCC",
number = "TR04-010",
year = 2004,
organization = "{ECCC}",
eprint="eccc:TR04-010"}

@article{prs,
author = "M. Parnas and D. Ron and A. Samorodnitsky",
title = "Testing basic {Boolean} formulae",
journal = "SIAM Journal on Discrete Mathematics",
volume = 16,
year = "2002",
pages = "20--46",
eprint="sidma:10.1137/S0895480101407444
"}

@incollection{rtt,
author = "D. Ron",
title = "Property testing",
booktitle = "Handbook of Randomized Computing",
editor = "S. Rajasekaran and P. M. Pardalos and J. H. Reif and J. D. P. Rolim",
year = 2001,
volume = "II",
pages = "597--649",
publisher = "Kluwer",
pdf="http://www.eng.tau.ac.il/~danar/Public-pdf/tut.pdf"}

@article{rsc,
author = "R. Rubinfeld and M. Sudan",
title = "Robust characterization of polynomials with
applications to program testing",
journal = "SIAM Journal on Computing",
volume = 25,
year = "1996",
pages = "252--271",
eprint="sicomp:10.1137/S0097539793255151"}

@string{sict20 = "Proc. 20th IEEE Conf.
                on Computational Complexity"}

@incollection{conf,
author = "E. Fischer and L. Fortnow",
title = "Tolerant Versus Intolerant Testing for {Boolean} Properties",
booktitle = sict20,
pages = "135--140",
year = 2005,
publisher = "{IEEE Computer Society Press}",
eprint="ccc:10.1109/CCC.2005.30"}