Property testing in bounded degree graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Property testing in bounded degree graphs

Full text

Pdf (1.61 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-ninth annual ACM symposium on Theory of computing table of contents

El Paso, Texas, United States

Pages: 406 - 415

Year of Publication: 1997

ISBN:0-89791-888-6

Authors

Oded Goldreich	Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel
Dana Ron	Labaratory for Computer Science, MIT, 545 Technology Sq. Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 49, Citation Count: 27

Additional Information:

references cited by 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/258533.258627 What is a DOI?

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	S. Arora, C. Lurid, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and intractability of approximation problems. In 33rd FOGS, pages 14-23, 1992.
	2	S. Arora and S. Safra. Probabilistic checkable proofs: A new characterization of NP. In 33rd FOGS, pages 1-13, 1992.
	3	László Babai , Lance Fortnow , Leonid A. Levin , Mario Szegedy, Checking computations in polylogarithmic time, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.21-32, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103428]
	4	L. Babai, L. Fortnow, and C. Lund. Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity, 1(1):3-40, 1991.
	5	M. Bellare , O. Goldreich , M. Sudan, Free bits, PCPs and non-approximability-towards tight results, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.422, October 23-25, 1995
	6	A. A. Benczur, A representation of cuts within 6/5 times the edge connectivity with applications, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.92, October 23-25, 1995
	7	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]
	8	E. A. Dinic, A. V. Karazanov, and M. V. Lomonosov. On the structure of the system of minimum edge cuts in a graph. Studies in Discrete Optimizalions, pages 290-306, 1976. In Russian.
	9	Y. Dinitz and J. Westbrook. Maintaining the classes of 4- edge-connectivity in a graph on-line. Technical Report ~871, Technion, Department of Computer Science, 1995.
	10	Shimon Even, Graph Algorithms, W. H. Freeman & Co., New York, NY, 1979
	11	U. Feige , S. Goldwasser , L. Lovász , S. Safra , M. Szegedy, Approximating clique is almost NP-complete (preliminary version), Proceedings of the 32nd annual symposium on Foundations of computer science, p.2-12, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185341]
	12	Harold N. Gabow, Applications of a poset representation to edge connectivity and graph rigidity, Proceedings of the 32nd annual symposium on Foundations of computer science, p.812-821, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185453]
	13	Peter Gemmell , Richard Lipton , Ronitt Rubinfeld , Madhu Sudan , Avi Wigderson, Self-testing/correcting for polynomials and for approximate functions, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.33-42, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103429]
	14	O. Goldreich , S. Goldwasser , D. Ron, Property testing and its connection to learning and approximation, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.339, October 14-16, 1996
	15	O. Goldreich and D. Ron. Property testing in bounded degree graphs. Available from http://theory, lcs .mit. edu/-danar, 1997.
	16	Johan Håstad, Testing of the long code and hardness for clique, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.11-19, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237820]
	17	David R. Karger, Global min-cuts in RNC, and other ramifications of a simple min-out algorithm, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.21-30, January 25-27, 1993, Austin, Texas, United States
	18	Hiroshi Nagamochi , Toshihide Ibaraki, Deterministic Õ(nm) time edge-splitting in undirected graphs, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.64-73, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237830]
	19	D. Naor, D. Gusfield, and C. Martel. A fast algorithm for optimally increasing the edge-connectivity. In 31st FO CS, pages 698-707, 1990.
	20	C.H. Papadimitriou and M. Yanakakis. Optimization, approximation and complexity classes. JCSS, 43:425-440, 1991.
	21	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]
	22	Toshimasa Watanabe , Akira Nakamura, Edge-connectivity augmentation problems, Journal of Computer and System Sciences, v.35 n.1, p.96-144, Aug. 1987 [doi>10.1016/0022-0000(87)90038-9]

CITED BY 27

	Ziv Bar-Yossef , Ravi Kumar , D. Sivakumar, Sampling algorithms: lower bounds and applications, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.266-275, July 2001, Hersonissos, Greece
	Matthias Miltrup , Georg Schnitger, Neural networks and efficient associative memory, Proceedings of the eleventh annual conference on Computational learning theory, p.235-246, July 24-26, 1998, Madison, Wisconsin, United States
	Michael Kearns , Dana Ron, Testing problems with sub-learning sample complexity, Proceedings of the eleventh annual conference on Computational learning theory, p.268-279, July 24-26, 1998, Madison, Wisconsin, United States
	Funda Ergün , Ravi Kumar , Ronitt Rubinfeld, Fast approximate PCPs, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.41-50, May 01-04, 1999, Atlanta, Georgia, United States
	Michal Parnas , Dana Ron, Testing metric properties, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.276-285, July 2001, Hersonissos, Greece
	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
	Artur Czumaj , Christian Sohler, Soft kinetic data structures, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.865-872, January 07-09, 2001, Washington, D.C., United States
	Eli Ben-Sasson , Oded Goldreich , Prahladh Harsha , Madhu Sudan , Salil Vadhan, Robust pcps of proximity, shorter pcps and applications to coding, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Michal Parnas , Dana Ron, Testing the diameter of graphs, Random Structures & Algorithms, v.20 n.2, p.165-183, March 2002
	Michael A. Bender , Dana Ron, Testing properties of directed graphs: acyclicity and connectivity, Random Structures & Algorithms, v.20 n.2, p.184-205, March 2002
	Beate Bollig , Ingo Wegener, Functions that have read-once branching programs of quadratic size are not necessarily testable, Information Processing Letters, v.87 n.1, p.25-29, 16 July 2003
	M. Kiwi, Algebraic testing and weight distributions of codes, Theoretical Computer Science, v.299 n.1-3, p.81-106, 18 April 2003
	Marcos Kiwi , Frédéric Magniez , Miklos Santha, Exact and approximate testing/correcting of algebraic functions: a survey, Theoretical aspects of computer science: advanced lectures, Springer-Verlag New York, Inc., New York, NY, 2002
	Noga Alon, Testing subgraphs in large graphs, Random Structures & Algorithms, v.21 n.3-4, p.359-370, October 2002
	Viraj Kumar , Mahesh Viswanathan, Conformance testing in the presence of multiple faults, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Eldar Fischer, On the strength of comparisons in property testing, Information and Computation, v.189 n.1, p.107-116, 25 February 2004
	Eldar Fischer , Eric Lehman , Ilan Newman , Sofya Raskhodnikova , Ronitt Rubinfeld , Alex Samorodnitsky, Monotonicity testing over general poset domains, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Funda Ergün , Sampath Kannan , S. Ravi Kumar , Ronitt Rubinfeld , Mahesh Viswanathan, Spot-checkers, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.259-268, May 24-26, 1998, Dallas, Texas, United States
	Eldar Fischer , Ilan Newman, Testing of matrix properties, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.286-295, July 2001, Hersonissos, Greece
	Kenji Obata, Approximate max-integral-flow/min-multicut theorems, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Hana Chockler , Dan Gutfreund, A lower bound for testing juntas, Information Processing Letters, v.90 n.6, p.301-305, 30 June 2004
	Hana Chockler , Orna Kupferman, ω-Regular languages are testable with a constant number of queries, Theoretical Computer Science, v.329 n.1-3, p.71-92, 13 December 2004
	Oded Goldreich, Property testing in massive graphs, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	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
	Abraham D. Flaxman , Alan M. Frieze, The diameter of randomly perturbed digraphs and some applications, Random Structures & Algorithms, v.30 n.4, p.484-504, July 2007
	Yuichi Yoshida , Masaki Yamamoto , Hiro Ito, An improved constant-time approximation algorithm for maximum~matchings, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Katalin Friedl , Miklos Santha , Frédéric Magniez , Pranab Sen, Quantum Testers for Hidden Group Properties, Fundamenta Informaticae, v.91 n.2, p.325-340, April 2009