On proximity oblivious testing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On proximity oblivious testing

Full text

Pdf (637 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the 41st annual ACM symposium on Theory of computing table of contents

Bethesda, MD, USA

SESSION: Property testing table of contents

Pages 141-150

Year of Publication: 2009

ISBN:978-1-60558-506-2

Authors

Oded Goldreich	Weizmann Institute of Science, Rehovot, Israel
Dana Ron	Tel Aviv University, Tel Aviv, Israel

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 59, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1536414.1536436 What is a DOI?

ABSTRACT

We initiate a systematic study of a special type of property testers. These testers consist of repeating a basic test for a number of times that depends on the proximity parameter, whereas the basic test is oblivious of the proximity parameter. We refer to such basic tests by the term Proximity-Oblivious Testers. While proximity-oblivious testers were studied before - most notably in the algebraic setting - the current study seems to be the first one to focus on graph properties. We provide a mix of positive and negative results, and in particular characterizations of the graph properties that have constant-query proximity-oblivious testers in the two standard models (i.e., the adjacency matrix and the bounded-degree models). Furthermore, we show that constant-query proximity-oblivious testers do not exist for many easily testable properties, and that even when proximity-oblivious testers exist, repeating them does not necessarily yield the best standard testers for the corresponding property.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Noga Alon, Testing subgraphs in large graphs, Random Structures & Algorithms, v.21 n.3-4, p.359-370, October 2002 [doi>10.1002/rsa.10056]
	2	Noga Alon , Seannie Dar , Michal Parnas , Dana Ron, Testing of Clustering, SIAM Journal on Discrete Mathematics, v.16 n.3, p.393-417, 2003 [doi>10.1137/S0895480102410973]
	3	N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy. Efficient testing of large graphs. Combinatorica, 20:451--476, 2000.
	4	Noga Alon , Eldar Fischer , Ilan Newman , Asaf Shapira, A combinatorial characterization of the testable graph properties: it's all about regularity, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132555]
	5	Noga Alon , Michael Krivelevich, Testing k-colorability, SIAM Journal on Discrete Mathematics, v.15 n.2, p.211-227, 2002 [doi>10.1137/S0895480199358655]
	6	Noga Alon , Asaf Shapira, A Characterization of Easily Testable Induced Subgraphs, Combinatorics, Probability and Computing, v.15 n.6, p.791-805, November 2006 [doi>10.1017/S0963548306007759]
	7	M. Bellare, D. Coppersmith, J. Håstad, M. Kiwi, and M. Sudan. Linearity testing over characteristic two. IEEE Transactions on Information Theory, 42(6):1781--1795, 1996.
	8	Eli Ben-Sasson , Prahladh Harsha , Sofya Raskhodnikova, Some 3CNF Properties Are Hard to Test, SIAM Journal on Computing, v.35 n.1, p.1-21, 2005 [doi>10.1137/S0097539704445445]
	9	Itai Benjamini , Oded Schramm , Asaf Shapira, Every minor-closed property of sparse graphs is testable, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374433]
	10	Manuel Blum , Michael Luby , Ronitt Rubinfeld, Self-testing/correcting with applications to numerical problems, Journal of Computer and System Sciences, v.47 n.3, p.549-595, Dec. 1993 [doi>10.1016/0022-0000(93)90044-W]
	11	Irit Dinur, The PCP theorem by gap amplification, Journal of the ACM (JACM), v.54 n.3, p.12-es, June 2007 [doi>10.1145/1236457.1236459]
	12	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.
	13	Eldar Fischer , Guy Kindler , Dana Ron , Shmuel Safra , Alex Samorodnitsky, Testing juntas, Journal of Computer and System Sciences, v.68 n.4, p.753-787, June 2004 [doi>10.1016/j.jcss.2003.11.004]
	14	Eldar Fischer , Oded Lachish , Ilan Newman , Arie Matsliah , Orly Yahalom, On the Query Complexity of Testing Orientations for Being Eulerian, Proceedings of the 11th international workshop, APPROX 2008, and 12th international workshop, RANDOM 2008 on Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, August 25-27, 2008, Boston, MA, USA [doi>10.1007/978-3-540-85363-3_32]
	15	O. Goldreich, S. Goldwasser, E. Lehman, D. Ron, and A. Samordinsky. Testing monotonicity. Combinatorica, 20(3):301--337, 2000.
	16	Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998 [doi>10.1145/285055.285060]
	17	O. Goldreich and D. Ron. Property testing in bounded degree graphs. Algorithmica, pages 302--343, 2002.
	18	O. Goldreich and D. Ron. Algorithmic aspects of property testing in the dense graphs model. ECCC, TR08-039, 2008.
	19	O. Goldreich and D. Ron. On proximity oblivious testing. ECCC, TR08-041, 2008.
	20	Oded Goldreich , Madhu Sudan, Locally testable codes and PCPs of almost-linear length, Journal of the ACM (JACM), v.53 n.4, p.558-655, July 2006 [doi>10.1145/1162349.1162351]
	21	Oded Goldreich , Luca Trevisan, Three theorems regarding testing graph properties, Random Structures & Algorithms, v.23 n.1, p.23-57, August 2003 [doi>10.1002/rsa.10078]
	22	O. Goldreich and L. Trevisan. Errata to {18}. Available from www.wisdom.weizmann.ac.il/~oded/p_ttt.html, 2005.
	23	Tali Kaufman , Madhu Sudan, Algebraic property testing: the role of invariance, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374434]
	24	Michal Parnas , Dana Ron, Testing metric properties, Information and Computation, v.187 n.2, p.155-195, 15 December 2003 [doi>10.1016/S0890-5401(03)00160-3]
	25	Michal Parnas , Dana Ron , Alex Samorodnitsky, Testing Basic Boolean Formulae, SIAM Journal on Discrete Mathematics, v.16 n.1, p.20-46, 2003 [doi>10.1137/S0895480101407444]
	26	S. Raskhodnikova and A. Smith. A note on adaptivity in testing properties of bounded degree graphs. Technical Report TR06-089, Electronic Colloquium on Computational Complexity (ECCC), 2006. Available from www.eccc.uni-trier.de/eccc/.
	27	D. Ron. Property testing. In Handbook on Randomization, Volume II, pages 597--649, 2001. Editors: S. Rajasekaran, P. M. Pardalos, J. H. Reif and J. D. P. Rolim.
	28	Ronitt Rubinfeld , Madhu Sudan, Robust Characterizations of Polynomials withApplications to Program Testing, SIAM Journal on Computing, v.25 n.2, p.252-271, February 1996 [doi>10.1137/S0097539793255151]