A sublinear bipartiteness tester for bounded degree graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A sublinear bipartiteness tester for bounded degree graphs

Full text

Pdf (1.44 MB)

Source

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

Dallas, Texas, United States

Pages: 289 - 298

Year of Publication: 1998

ISBN:0-89791-962-9

Authors

Oded Goldreich	Department of Computer Science, Weizmann Institute of Science, Rehovot, Israel
Dana Ron	Laboratory 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): 0, Downloads (12 Months): 12, Citation Count: 5

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/276698.276767 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	N. Alon and J. H. Spencer. The Probabilistic Method, John Wiley ~ Sons, Inc., 1992.
	2	8. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and intractability of approximation problems. In Proceedings of the Thirty. Third Annual Symposium on Foundations of Computer Science, pages 14-23, 1992.
	3	S. Arora and S. Safra. Probabilistic checkable proofs: A new characterization of NP. In Proceedings of the Thirty. Third Annual Symposium on Foundations of Gomputer Science, pages 1-13, 1992.
	4	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]
	5	L, Bahai, L. Fortnow, and C. Lurid. Non-deterministic exponential time has two-prover interactive protocols. Gomputational Complezittj, 1(1):3-40, 1991.
	6	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]
	7	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]
	8	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
	9	O. Goldreich and D. Ron. Testing properties of bounded.dgree graphs, in Proceedings of the Twenty. Ei#lJth Annual A CM Symposium on the Theory of Computing, page~ 339-348, 1996.
	10	O, Goldreich and D. Ron. A subliniear biparrifeness tester for bounded degree graphs. Long veroion of this extended abstract, available from http://theory .lcs.nit. edu/~danar, 1997.
	11	M. Mihail. Conductance and convergence of Markov chains. A combinatorial treatment of expanders. In Proceedin#8 80th Annual Conference on Foundations of Oomputar Science, pages 526-531, 1989.
	12	R. Rubinfcld. Robust functional equations and their applications to program testing. In Proceedings of the Thirt~l. Fifih Annual Symposium on Foundations of Oomputer Science, 1994.
	13	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]

CITED BY 5

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