Article

Efficient testing of groups

Authors:

Katalin Friedl,

Gábor Ivanyos,

Miklos SanthaAuthors Info & Claims

STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing

Pages 157 - 166

https://doi.org/10.1145/1060590.1060614

Published: 22 May 2005 Publication History

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

[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 and A. Russell. Efficient probabilistically checkable proofs and applications to approximations. In Proceedings of 25th ACM STOC, pp. 294--304, 1993.]]

Digital Library

[4]

M. Bellare and M. Sudan. Improved non-approximability results. In Proceedings of 26th ACM STOC, pp. 184--193, 1994.]]

Digital Library

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

H. Buhrman, L. Fortnow, I. Newman and H. Röhrig, Quantum property testing, In Proceedings of the 14th ACM-SIAM SODA, pp. 480--488, 2003.]]

Digital Library

[7]

E. Ben-Sasson, M. Sudan, S. Vadhan and A. Wigderson. Randomness-efficient Low Degree Tests and Short PCPs via Epsilon Biased Sets. In Proceedings of 35th ACM STOC, pp. 612--621, 2003.]]

Digital Library

[8]

M. Blum, M. Luby, and R. Rubinfeld. Self--testing/correcting with applications to numerical problems. J. of Computer and System Sciences, 47(3), pp. 549--595, 1993.]]

Digital Library

[9]

K. Cheung and M. Mosca. Decomposing finite Abelian groups, Quantum Information and Computation, 1(3), pp. 26--32, 2001.]]

Digital Library

[10]

F. Ergün, S. Kannan, R. Kumar, R. Rubinfeld and M. Viswanathan. Spot-Checkers. J. of Computer and System Sciences, 60(3), pp. 717--751, 2000.]]

Digital Library

[11]

O. Goldreich. Combinatorial property testing --- A survey. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 43, pp. 45--60, 1998.]]

[12]

J. Håastad and A. Wigderson. Simple analysis of graph tests for linearity and PCP. Random Structures and Algorithms, vol. 22, no. 2, pp. 139-160, 2003.]]

Digital Library

[13]

M. Kiwi, F. Magniez and M. Santha. Exact and approximate testing/correcting of algebraic functions: A survey. In Proceedings of 1st Summer School on Theoretical Aspects of Computer Science, LNCS vol. 2292 pp. 30--83, 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]

S. Rajagopalan and L. Schulman. Verification of Identities. SIAM J. Computing, 29(4), pp. 1155--1163, 2000.]]

Digital Library

[16]

M. Mosca and A. Ekert, The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer, In Proceedings of the 1st NASA Int. Conf. on Quantum Computing and Quantum Communication, (QCQC'98), LNCS vol. 1509, pp. 174--188, 1999.]]

Digital Library

[17]

D. Ron. Property testing (A tutorial). Handbook on Randomized Computing, Kluwer Press, 2001.]]

[18]

A. Samorodnitsky and L. Trevisan. A PCP characterisation of NP with optimal amortized query complexity. In Proceedings of 32nd ACM STOC, pp. 191--199, 2000.]]

Digital Library

[19]

P. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. on Computing, vol. 26(5), pp. 1484--1509, 1997.]]

Digital Library

[20]

A. Shpilka and A. Wigderson. Derandomizing homomorphism testing in general groups. In Proceedings of 36th ACM STOC, pp. 427--435, 2004.]]

Digital Library

Cited By

Inui YGall F(2019)Quantum Property Testing of Group SolvabilityAlgorithmica10.5555/3118774.311916359:1(35-47)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.5555/3118774.3119163
Joos FKim JKuhn DOsthus D(2017)A Characterization of Testable Hypergraph Properties2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2017.84(859-867)Online publication date: Oct-2017
https://doi.org/10.1109/FOCS.2017.84
Mosca M(2016)Abelian Hidden Subgroup ProblemEncyclopedia of Algorithms10.1007/978-1-4939-2864-4_1(1-5)Online publication date: 22-Apr-2016
https://doi.org/10.1007/978-1-4939-2864-4_1
Show More Cited By

Index Terms

Efficient testing of groups
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Property testing for cyclic groups and beyond

This paper studies the problem of testing if an input ( Γ , ), where Γ is a finite set of unknown size and is a binary operation over Γ given as an oracle, is close to a specified class of groups. Friedl et al. (Proc. of STOC, 2005 ) have ...
The intractability of computing the Hamming distance

Given a string x and a language L, the Hamming distance of x to L is the minimum Hamming distance of x to any string in L. The edit distance of a string to a language is analogously defined.First, we prove that there is a language in AC⁰ such that both ...
Streaming algorithms for embedding and computing edit distance in the low distance regime
STOC '16: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing

The Hamming and the edit metrics are two common notions of measuring distances between pairs of strings x,y lying in the Boolean hypercube. The edit distance between x and y is defined as the minimum number of character insertion, deletion, and bit ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing

May 2005

778 pages

ISBN:1581139608

DOI:10.1145/1060590

General Chair:
Hal Gabow
University of Colorado
,
Program Chair:
Ronald Fagin
IBM Almaden Research Center

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 May 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

STOC05

Sponsor:

STOC05: Symposium on Theory of Computing

May 22 - 24, 2005

MD, Baltimore, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
421
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Inui YGall F(2019)Quantum Property Testing of Group SolvabilityAlgorithmica10.5555/3118774.311916359:1(35-47)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.5555/3118774.3119163
Joos FKim JKuhn DOsthus D(2017)A Characterization of Testable Hypergraph Properties2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2017.84(859-867)Online publication date: Oct-2017
https://doi.org/10.1109/FOCS.2017.84
Mosca M(2016)Abelian Hidden Subgroup ProblemEncyclopedia of Algorithms10.1007/978-1-4939-2864-4_1(1-5)Online publication date: 22-Apr-2016
https://doi.org/10.1007/978-1-4939-2864-4_1
Mosca M(2015)Abelian Hidden Subgroup ProblemEncyclopedia of Algorithms10.1007/978-3-642-27848-8_1-2(1-6)Online publication date: 3-Aug-2015
https://doi.org/10.1007/978-3-642-27848-8_1-2
Le Gall FYoshida Y(2013)Property testing for cyclic groups and beyondJournal of Combinatorial Optimization10.1007/s10878-011-9445-826:4(636-654)Online publication date: 1-Nov-2013
https://dl.acm.org/doi/10.1007/s10878-011-9445-8
Mosca M(2012)Quantum AlgorithmsComputational Complexity10.1007/978-1-4614-1800-9_144(2303-2333)Online publication date: 2012
https://doi.org/10.1007/978-1-4614-1800-9_144
Le Gall FYoshida Y(2011)Property testing for cyclic groups and beyondProceedings of the 17th annual international conference on Computing and combinatorics10.5555/2033094.2033132(432-443)Online publication date: 14-Aug-2011
https://dl.acm.org/doi/10.5555/2033094.2033132
Le Gall FYoshida Y(2011)Property Testing for Cyclic Groups and BeyondComputing and Combinatorics10.1007/978-3-642-22685-4_38(432-443)Online publication date: 2011
https://doi.org/10.1007/978-3-642-22685-4_38
Inui YLe Gall F(2009)Quantum Property Testing of Group SolvabilityAlgorithmica10.1007/s00453-009-9338-859:1(35-47)Online publication date: 11-Jul-2009
https://doi.org/10.1007/s00453-009-9338-8
Mosca M(2009)Quantum AlgorithmsEncyclopedia of Complexity and Systems Science10.1007/978-0-387-30440-3_423(7088-7118)Online publication date: 2009
https://doi.org/10.1007/978-0-387-30440-3_423
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents