Efficient testing of groups

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient testing of groups

Full text

Pdf (230 KB)

Source

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

Baltimore, MD, USA

SESSION: Session 4A table of contents

Pages: 157 - 166

Year of Publication: 2005

ISBN:1-58113-960-8

Authors

Katalin Friedl	Budapest University of Technology and Economics, Budapest, Hungary
Gábor Ivanyos	Computer and Automation Res. Inst. of Hung. Acad. Sci., Budapest, Hungary
Miklos Santha	UniversitéParis--Sud, Orsay, France

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): 6, Downloads (12 Months): 42, Citation Count: 1

Additional Information:

abstract 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/1060590.1060614 What is a DOI?

ABSTRACT

We construct an efficient probabilistic algorithm that, given a finite set with a binary operation, tests if it is an abelian group. The distance used is an analogue of the edit distance for strings. The query complexity of the tester is polylogarithmic in the size of the set. Previous testers used Hamming type distances and had superlinear query complexity. A building block for our construction is a constant query complexity homomorphism tester for functions mapping an given finite group into an arbitrary set equipped with a binary operation.

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. Spencer. The probabilistic method. John Wiley & Sons, 1992.
	2	M. Bellare, D. Coppersmith, J. Håastad, M. Kiwi, and M. Sudan. Linearity testing in characteristic two. IEEE Transactions on Information Theory, 42(6), pp. 1781--1795, 1996.
	3	M. Bellare , S. Goldwasser , C. Lund , A. Russeli, Efficient probabilistically checkable proofs and applications to approximations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.294-304, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167174]
	4	Mihir Bellare , Madhu Sudan, Improved non-approximability results, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.184-193, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195129]
	5	M. Ben-Or, D. Coppersmith, M. Luby and R. Rubinfeld. Non-abelian homomorphism testing, and distributions close to their self-convolutions. In Proceedings of 8th RANDOM, LNCS vol. 3122, pp. 273--285, 2004.
	6	Harry Buhrman , Lance Fortnow , Ilan Newman , Hein Röhrig, Quantum property testing, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	7	Eli Ben-Sasson , Madhu Sudan , Salil Vadhan , Avi Wigderson, Randomness-efficient low degree tests and short PCPs via epsilon-biased sets, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780631]
	8	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]
	9	K. Cheung and M. Mosca. Decomposing finite Abelian groups, Quantum Information and Computation, 1(3), pp. 26--32, 2001.
	10	Funda Ergün , Sampath Kannan , S. Ravi Kumar , Ronitt Rubinfeld , Mahesh Viswanathan, Spot-checkers, Journal of Computer and System Sciences, v.60 n.3, p.717-751, June 2000 [doi>10.1006/jcss.1999.1692]
	11	O. Goldreich. Combinatorial property testing --- A survey. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 43, pp. 45--60, 1998.
	12	Johan Håstad , Avi Wigderson, Simple analysis of graph tests for linearity and PCP, Random Structures & Algorithms, v.22 n.2, p.139-160, March 2003 [doi>10.1002/rsa.10068]
	13	Marcos A. Kiwi , Frédéric Magniez , Miklos Santha, Exact and Approximate Testing/Correcting of Algebraic Functions: A Survey, Theoretical Aspects of Computer Science, Advanced Lectures [First Summer School on Theoretical Aspects of Computer Science, Tehran, Iran, July 2000], p.30-83, July 01, 2000
	14	R. Lipton. New directions in testing. Series in Discrete Mathematics and Theoretical Computer Science, ACM/AMS, Vol. 2, pp. 191--202, 1991.
	15	Sridhar Rajagopalan , Leonard J. Schulman, Verification of Identities, SIAM Journal on Computing, v.29 n.4, p.1155-1163, Feb. 2000 to March 2000 [doi>10.1137/S0097539797325387]
	16	Michele Mosca , Artur Ekert, The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer, Selected papers from the First NASA International Conference on Quantum Computing and Quantum Communications, p.174-188, February 17-20, 1998
	17	D. Ron. Property testing (A tutorial). Handbook on Randomized Computing, Kluwer Press, 2001.
	18	Alex Samorodnitsky , Luca Trevisan, A PCP characterization of NP with optimal amortized query complexity, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.191-199, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335329]
	19	Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, v.26 n.5, p.1484-1509, Oct. 1997 [doi>10.1137/S0097539795293172]
	20	Amir Shpilka , Avi Wigderson, Derandomizing homomorphism testing in general groups, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007421]