research-article

Nearly tight bounds for testing function isomorphism

Authors:

Sourav Chakraborty,

David García-Soriano,

Arie MatsliahAuthors Info & Claims

SODA '11: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms

Pages 1683 - 1702

Published: 23 January 2011 Publication History

Abstract

We study the problem of testing isomorphism (equivalence up to relabelling of the variables) of two Boolean functions f,g: {0, 1}ⁿ → {0, 1}. Our main focus is on the most studied case, where one of the functions is given (explicitly) and the other function may be queried.

We prove that for every k ≤ n, the worst-case query complexity of testing isomorphism to a given k-junta is Ω(k) and O(k log k). Consequently, the query complexity of testing function isomorphism is θ(n).

Prior to this work, only lower bounds of Ω(log k) queries were known, for limited ranges of k, proved by Fischer et al. (FOCS 2002), Blais and O'Donnell (CCC 2010), and recently by Alon and Blais (RANDOM 2010). The nearly tight O(k log k) upper bound improves on the Õ(k⁴) upper bound from Fischer et al. (FOCS 2002).

Extending the lower bound proof, we also show polynomial query-complexity lower bounds for the problems of testing whether a function can be computed by a circuit of size ≤ s, and testing whether the Fourier degree of a function is ≤ d. This answers questions posed by Diakonikolas et al. (FOCS 2007).

We also address two closely related problems --

1. Testing isomorphism to a k-junta with one-sided error: we prove that for any 1 < k < n − 1, the query complexity is Ω(log (ⁿ_k)), which is almost optimal. This lower bound is a consequence of a proof that the query complexity of testing, with one-sided error, whether a function is a k-parity is Θ(log (ⁿ_k).

2. Testing isomorphism between two unknown functions that can be queried: we prove that the query complexity in this setting is Ω(√2ⁿ) and O(√2ⁿn log n).

References

[1]

{AB10} Noga Alon and Eric Blais. Testing boolean function isomorphism. In Proc. RANDOM-APPROX, pages 394--405, 2010.

Digital Library

[2]

{AKK⁺03} Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron. Testing low-degree polynomials over GF(2). In Proc. RANDOM-APPROX, pages 188--199, 2003.

[3]

{AS92} Noga Alon and Joel H. Spencer. The Probabilistic Method. Wiley, New York, 1992.

[4]

{BC10} Laszlo Babai and Sourav Chakraborty. Property testing of equivalence under a permutation group action. To appear in The ACM Transactions on Computation Theory (ToCT), 2010.

[5]

{BEHL09} Ido Ben-Eliezer, Rani Hod, and Shachar Lovett. Random low degree polynomials are hard to approximate. In Proc. RANDOM-APPROX, pages 366--377, 2009.

Digital Library

[6]

{BFF⁺01} T. Batu, L. Fortnow, E. Fischer, R. Kumar, R. Rubinfeld, and P. White. Testing random variables for independence and identity. Proc. IEEE Symposium on Foundations of Computer Science, 0:442, 2001.

Digital Library

[7]

{Bla09} Eric Blais. Testing juntas nearly optimally. In Proc. ACM symposium on the Theory of computing, pages 151--158, New York, NY, USA, 2009. ACM.

Digital Library

[8]

{BO10} Eric Blais and Ryan O'Donnell. Lower bounds for testing function isomorphism. In IEEE Conference on Computational Complexity, pages 235--246, 2010.

Digital Library

[9]

{DLM⁺07} Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, and Andrew Wan. Testing for concise representations. Proc. IEEE Symposium on Foundations of Computer Science, 0:549--558, 2007.

Digital Library

[10]

{Fis01} Eldar Fischer. The art of uninformed decisions. Bulletin of the EATCS, 75:97, 2001.

[11]

{FKR⁺02} Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, and Alex Samorodnitsky. Testing juntas. In FOCS, pages 103--112, 2002.

[12]

{FM08} Eldar Fischer and Arie Matsliah. Testing graph isomorphism. SIAM J. Comput., 38(1):207--225, 2008.

Digital Library

[13]

{FNS04} Eldar Fischer, Ilan Newman, and Jiří Sgall. Functions that have read-twice constant width branching programs are not necessarily testable. Random Struct. Algorithms, 24(2):175--193, 2004.

Digital Library

[14]

{FR87} P. Frankl and V. Rödl. Forbidden intersections. Trans. Amer. Math. Soc. 300, pages 259--286, 1987.

[15]

{FW81} P. Frankl and M. Wilson. Intersection theorems with geometric consequences. Combinatorica 1, pages 357--368, 1981.

[16]

{JPRZ04} Charanjit S. Jutla, Anindya C. Patthak, Atri Rudra, and David Zuckerman. Testing low-degree polynomials over prime fields. Proc. IEEE Symposium on Foundations of Computer Science, 0:423--432, 2004.

Digital Library

[17]

{KR04} Tali Kaufman and Dana Ron. Testing polynomials over general fields. In Proc. IEEE Symposium on Foundations of Computer Science, pages 413--422, Washington, DC, USA, 2004. IEEE Computer Society.

Digital Library

[18]

{KS05} Peter Keevash and Benny Sudakov. Set systems with restricted cross-intersections and the minimum rank of inclusion matrices. SIAM J. Discrete Math., 18(4):713--727, 2005.

Digital Library

[19]

{PRS02} Michal Parnas, Dana Ron, and Alex Samorodnitsky. Testing basic boolean formulae. SIAM J. Discrete Math., 16(1):20--46, 2002.

Digital Library

[20]

{SSS95} Jeanette P. Schmidt, Alan Siegel, and Aravind Srinivasan. Chernoff-Hoeffding bounds for applications with limited independence. SIAM J. Discrete Math., 8(2):223--250, 1995.

Digital Library

Cited By

Alon NWeinstein A(2015)Local Correction with Constant Error RateAlgorithmica10.1007/s00453-013-9817-971:2(496-516)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1007/s00453-013-9817-9
Bhattacharyya AGrigorescu EShapira A(2015)A unified framework for testing linear-invariant propertiesRandom Structures & Algorithms10.1002/rsa.2050746:2(232-260)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1002/rsa.20507
Arvind VVasudev Y(2014)Isomorphism testing of Boolean functions computable by constant-depth circuitsInformation and Computation10.1016/j.ic.2014.08.003239:C(3-12)Online publication date: 1-Dec-2014
https://dl.acm.org/doi/10.1016/j.ic.2014.08.003
Show More Cited By

Nearly tight bounds for testing function isomorphism
1. Computing methodologies
  1. Symbolic and algebraic manipulation
2. Theory of computation

Recommendations

Nearly Tight Bounds for Testing Function Isomorphism

We study the problem of testing isomorphism (equivalence up to relabeling of the input variables) between Boolean functions. We prove the following: (1) For most functions $f:\{0,1\}^n \to \{0,1\}$, the query complexity of testing isomorphism to $f$ is $\...
Tight lower bounds for certain parameterized NP-hard problems

Based on the framework of parameterized complexity theory, we derive tight lower bounds on the computational complexity for a number of well-known NP-hard problems. We start by proving a general result, namely that the parameterized weighted ...
Lower Bounds for Testing Function Isomorphism
CCC '10: Proceedings of the 2010 IEEE 25th Annual Conference on Computational Complexity

We prove new lower bounds in the area of property testing of boolean functions. Specifically, we study the problem of testing whether a boolean function $f$ is isomorphic to a fixed function $g$ (i.e., is equal to $g$ up to permutation of the input ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '11: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms

January 2011

1785 pages

Program Chair:
Dana Randall
Georgia Institute of Technology

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 23 January 2011

Check for updates

Qualifiers

Research-article

Conference

SODA '11

Sponsor:

SIGACT

SODA '11: 22nd ACM-SIAM Symposium on Discrete Algorithms

January 23 - 25, 2011

California, San Francisco

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
58
Total Downloads

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

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Alon NWeinstein A(2015)Local Correction with Constant Error RateAlgorithmica10.1007/s00453-013-9817-971:2(496-516)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1007/s00453-013-9817-9
Bhattacharyya AGrigorescu EShapira A(2015)A unified framework for testing linear-invariant propertiesRandom Structures & Algorithms10.1002/rsa.2050746:2(232-260)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1002/rsa.20507
Arvind VVasudev Y(2014)Isomorphism testing of Boolean functions computable by constant-depth circuitsInformation and Computation10.1016/j.ic.2014.08.003239:C(3-12)Online publication date: 1-Dec-2014
https://dl.acm.org/doi/10.1016/j.ic.2014.08.003
Arvind VVasudev Y(2012)Isomorphism testing of boolean functions computable by constant-depth circuitsProceedings of the 6th international conference on Language and Automata Theory and Applications10.1007/978-3-642-28332-1_8(83-94)Online publication date: 5-Mar-2012
https://dl.acm.org/doi/10.1007/978-3-642-28332-1_8
Chakraborty SGarcía-Soriano DMatsliah A(2011)Efficient sample extractors for juntas with applicationsProceedings of the 38th international colloquim conference on Automata, languages and programming - Volume Part I10.5555/2027127.2027185(545-556)Online publication date: 4-Jul-2011
https://dl.acm.org/doi/10.5555/2027127.2027185

View Options

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