More Web Proxy on the site http://driver.im/

research-article

Sunflowers and Testing Triangle-Freeness of Functions

Authors:

Ning XieAuthors Info & Claims

ITCS '15: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science

Pages 357 - 366

https://doi.org/10.1145/2688073.2688084

Published: 11 January 2015 Publication History

Abstract

A function f : Fn/2 → {0,1} is triangle-free if there are no x₁, x₂, x₃ ∈ Fn/2 satisfying x₁ + x₂ + x₃ --0 and f(x₁) -- f(x₂) -- f(x₃) -- 1. In testing triangle freeness, the goal is to distinguish with high probability triangle-free functions from those which are ε-far from being triangle-free. It was shown by Green that the query complexity of the canonical tester for the problem is upper bounded by a function that depends only on ε (GAFA, 2005), however the best known upper bound is a tower type function of 1/ε. The best known lower bound on the query complexity of the canonical tester is 1/ε^13.239 (Fu and Kleinberg, RANDOM, 2014).

In this work we introduce a new approach to proving lower bounds on the query complexity of triangle-freeness. We relate the problem to combinatorial questions on collections of vectors in Zn/D and to sunflower conjectures studied by Alon, Shpilka, and Umans (Comput. Complex., 2013). The relations yield that a refutation of the Weak Sunflower Conjecture over Z₄ implies a super-polynomial lower bound on the query complexity of the canonical tester for triangle-freeness. Our results are extended to testing k-cycle-freeness of functions with domain Fn/p for every k > 3 and a prime p. In addition, we generalize the lower bound of Fu and Kleinberg to k-cycle-freeness for k > 4 by generalizing the construction of uniquely solvable puzzles due to Coppersmith and Winograd (J. Symbolic Comput., 1990).

References

[1]

N. Alon. Testing subgraphs in large graphs. Random Struct. Algorithms, 21(3--4):359--370, 2002. Preliminary version in FOCS'01.

Digital Library

[2]

N. Alon and R. B. Boppana. The monotone circuit complexity of boolean functions. Combinatorica, 7(1):1--22, 1987.

Digital Library

[3]

N. Alon, E. Fischer, I. Newman, and A. Shapira. A combinatorial characterization of the testable graph properties: It's all about regularity. SIAM J. Comput., 39(1):143--167, 2009. Preliminary version in STOC'06.

Digital Library

[4]

N. Alon, R. Hod, and A. Weinstein. On active and passive testing. CoRR, abs/1307.7364, 2013.

[5]

N. Alon, A. Shpilka, and C. Umans. On sunflowers and matrix multiplication. Computational Complexity, 22(2):219--243, 2013. Preliminary version in CCC'12.

[6]

M. Bateman and N. H. Katz. New bounds on cap sets. J. Amer. Math. Soc., 25(2):585--613, 2012.

[7]

F. A. Behrend. On sets of integers which contain no three terms in arithmetical progression. Proc. National Academy of Sciences USA, 32(12):331--332, 1946.

[8]

A. Bhattacharyya. Guest column: On testing affine-invariant properties over finite fields. SIGACT News, 44(4):53--72, 2013.

Digital Library

[9]

A. Bhattacharyya, E. Grigorescu, and A. Shapira. A unified framework for testing linear-invariant properties. In FOCS, pages 478--487, 2010.

Digital Library

[10]

A. Bhattacharyya and N. Xie. Lower bounds for testing triangle-freeness in boolean functions. In SODA, pages 87--98, 2010.

Digital Library

[11]

C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós, B. Szegedy, and K. Vesztergombi. Graph limits and parameter testing. In STOC, pages 261--270, 2006.

Digital Library

[12]

H. Cohn, R. D. Kleinberg, B. Szegedy, and C. Umans. Group-theoretic algorithms for matrix multiplication. In FOCS, pages 379--388, 2005.

Digital Library

[13]

D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. J. Symb. Comput., 9(3):251--280, 1990. Preliminary version in STOC'87.

Digital Library

[14]

I. Dinur and S. Safra. On the hardness of approximating minimum vertex cover. Annals of Mathematics, 162(1):439--485, 2005. Preliminary version in STOC'02.

[15]

Y. Edel. Extensions of generalized product caps. Des. Codes Cryptography, 31(1):5--14, 2004.

Digital Library

[16]

M. Elkin. An improved construction of progression-free sets. Israel J. of Math., 184(1):93--128, 2011. Preliminary version in SODA'10.

[17]

P. Erdös and R. Rado. Intersection theorems for systems of sets. J. London Math. Soc., 35:85--90, 1960.

[18]

P. Erdös and E. Szemerédi. Combinatorial properties of systems of sets. J. Comb. Theory, Ser. A, 24(3):308--313, 1978.

[19]

J. Fox. A new proof of the graph removal lemma. Annals of Mathematics, 174(1):561--579, 2011.

[20]

H. Fu and R. Kleinberg. Improved lower bounds for testing triangle-freeness in boolean functions via fast matrix multiplication. In RANDOM, pages 669--676, 2014.

[21]

O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning and approximation. J. ACM, 45(4):653--750, 1998. Preliminary version in FOCS'96.

Digital Library

[22]

B. Green. A Szemerédi-type regularity lemma in Abelian groups. Geom. and Funct. Anal., 15(2):340--376, 2005.

[23]

P. Hatami, S. Sachdeva, and M. Tulsiani. An arithmetic analogue of Fox's triangle removal argument. CoRR, abs/1304.4921, 2013.

[24]

T. Kaufman and M. Sudan. Algebraic property testing: the role of invariance. In STOC, pages 403--412, 2008.

Digital Library

[25]

A. V. Kostochka. A bound of the cardinality of families not containing Δ-systems. In The Mathematics of Paul Erdös II, Algorithms and Combinatorics, volume 14, pages 229--235. Springer, Berlin, 1997.

[26]

D. Král', O. Serra, and L. Vena. A combinatorial proof of the removal lemma for groups. J. Comb. Theory, Ser. A, 116(4):971--978, 2009.

Digital Library

[27]

D. Král', O. Serra, and L. Vena. A removal lemma for systems of linear equations over finite fields. Israel J. of Math., 187(1):193--207, 2012.

[28]

Y.-R. Liu and C. V. Spencer. A generalization of Meshulam's theorem on subsets of finite Abelian groups with no $3$-term arithmetic progression. Des. Codes Cryptography, 52(1):83--91, 2009.

Digital Library

[29]

R. Meshulam. On subsets of finite Abelian groups with no 3-term arithmetic progressions. J. Comb. Theory, Ser. A, 71(1):168--172, 1995.

Digital Library

[30]

A. A. Razborov. Lower bounds for the monotone complexity of some boolean functions. Soviet Mathematics Doklady, 31(2):354--357, 1985.

[31]

R. Rubinfeld and M. Sudan. Robust characterizations of polynomials with applications to program testing. SIAM J. Comput., 25(2):252--271, 1996. Preliminary version in SODA'92.

Digital Library

[32]

R. Salem and D. C. Spencer. On sets of integers which contain no three terms in arithmetical progression. In Proc. National Academy of Sciences USA, volume 28, pages 561--563, 1942.

[33]

A. Shapira. A proof of Green's conjecture regarding the removal properties of sets of linear equations. J. London Math. Soc., 81(2):355--373, 2010. Preliminary version in STOC'09.

[34]

A. J. Stothers. On the complexity of matrix multiplication. PhD thesis, The University of Edinburgh, 2010.

[35]

M. Sudan. Guest column: Testing linear properties: some general theme. SIGACT News, 42(1):59--80, 2011.

Digital Library

[36]

J. H. van Lint and R. M. Wilson. A course in combinatorics. Cambridge University Press, second edition, 2001.

[37]

V. V. Williams. Multiplying matrices faster than Coppersmith-Winograd. In STOC, pages 887--898, 2012.

Digital Library

Cited By

Christandl MVrana PZuiddam J(2021)Universal points in the asymptotic spectrum of tensorsJournal of the American Mathematical Society10.1090/jams/99636:1(31-79)Online publication date: 23-Nov-2021
https://doi.org/10.1090/jams/996
Christandl MVrana PZuiddam J(2019)Asymptotic tensor rank of graph tensorsComputational Complexity10.1007/s00037-018-0172-828:1(57-111)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1007/s00037-018-0172-8
Christandl MVrana PZuiddam JDiakonikolas IKempe DHenzinger M(2018)Universal points in the asymptotic spectrum of tensorsProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188766(289-296)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188766
Show More Cited By

Index Terms

Sunflowers and Testing Triangle-Freeness of Functions
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Sunflowers and Testing Triangle-Freeness of Functions

A function $${f : {\mathbb F}_{2}^{n} \rightarrow {\{0,1\}}}$$f:F2nź{0,1} is triangle-free if there are no $${x_{1},x_{2},x_{3} \in {\mathbb F}_{2}^{n}}$$x1,x2,x3źF2n satisfying $${x_{1} + x_{2} + x_{3} = 0}$$x1+x2+x3=0 and $${f(x_{1}) = f(x_{2}) = f(x_{...
Testing Triangle-Freeness in General Graphs

In this paper we consider the problem of testing whether a graph is triangle-free and, more generally, whether it is $H$-free, for a fixed subgraph $H$. The algorithm should accept graphs that are triangle-free and reject graphs that are far from being ...
Monotone Circuit Lower Bounds from Robust Sunflowers
Abstract
Robust sunflowers are a generalization of combinatorial sunflowers that have applications in monotone circuit complexity Rossman (SIAM J. Comput. 43:256–279, 2014), DNF sparsification Gopalan et al. (Comput. Complex. 22:275–310 2013), randomness ... $^{}$ $^{}$ $^{}$ $^{}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ITCS '15: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science

January 2015

404 pages

ISBN:9781450333337

DOI:10.1145/2688073

Program Chair:
Tim Roughgarden
Stanford University

Copyright © 2015 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

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 January 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

ITCS'15

Sponsor:

SIGACT

ITCS'15: Innovations in Theoretical Computer Science

January 11 - 13, 2015

Rehovot, Israel

Acceptance Rates

ITCS '15 Paper Acceptance Rate 45 of 159 submissions, 28%;

Overall Acceptance Rate 172 of 513 submissions, 34%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
57
Total Downloads

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

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Christandl MVrana PZuiddam J(2021)Universal points in the asymptotic spectrum of tensorsJournal of the American Mathematical Society10.1090/jams/99636:1(31-79)Online publication date: 23-Nov-2021
https://doi.org/10.1090/jams/996
Christandl MVrana PZuiddam J(2019)Asymptotic tensor rank of graph tensorsComputational Complexity10.1007/s00037-018-0172-828:1(57-111)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1007/s00037-018-0172-8
Christandl MVrana PZuiddam JDiakonikolas IKempe DHenzinger M(2018)Universal points in the asymptotic spectrum of tensorsProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188766(289-296)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188766
Lovász LSauermann L(2018)A lower bound for the k‐multicolored sum‐free problem in ZmnProceedings of the London Mathematical Society10.1112/plms.12223119:1(55-103)Online publication date: 16-Dec-2018
https://doi.org/10.1112/plms.12223
Fox JLovász LKlein P(2017)A tight bound for green's arithmetic triangle removal lemma in vector spacesProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039792(1612-1617)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039792

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