Improved Lower Bounds for Testing Triangle-freeness in Boolean Functions via Fast Matrix Multiplication

On sets of integers which contain no three in arithmetic progression

Salem, R. and Spencer, D. (1942) · 1942

Earlier work this paper cites.

On sets of integers which contain no three terms in arithmetical progression

Behrend, F. A. (1946) · 1946

Earlier work this paper cites.

Matrix multiplication via arithmetic progressions

Coppersmith, D. and Winograd, S. (1990) · 1990

Earlier work this paper cites.

Private communication

Xie, N. (2010) · 1990

Earlier work this paper cites.

Robust characterizations of polynomials with applications to program testing

Rubinfeld, R. and Sudan, M. (1996) · 1996

Earlier work this paper cites.

Property testing and its connection to learning and approximation

Goldreich, O., Goldwasser, S., and Ron, D. (1998) · 1998

Earlier work this paper cites.

Testing subgraphs in large graphs

Alon, N. (2002) · 2002

Earlier work this paper cites.

Testing subgraphs in directed graphs

Alon, N. and Shapira, A. (2004) · 2004

Earlier work this paper cites.

A characterization of the (natural) graph properties testable with one-sided error

Alon, N. and Shapira, A. (2005) · 2005

Cited alongside, same era.

Group-theoretic algorithms for matrix multiplication

Cohn, H., Kleinberg, R. D., Szegedy, B., and Umans, C. (2005) · 2005

Cited alongside, same era.

A Szemerédi-type regularity lemma in abelian groups, with applications

Green, B. (2005) · 2005

Cited alongside, same era.

A combinatorial characterization of the testable graph properties: it’s all about regularity

Alon, N., Fischer, E., Newman, I., and Shapira, A. (2006) · 2006

Cited alongside, same era.

Algebraic property testing: the role of invariance

Kaufman, T. and Sudan, M. (2008) · 2008

Cited alongside, same era.

Generalizations of the removal lemma

Rödl, V. and Schacht, M. (2009) · 2009

Cited alongside, same era.

A unified framework for testing linear-invariant properties

Bhattacharyya, A., Grigorescu, E., and Shapira, A. (2010) · 2010

Later among the works it cites.

Lower bounds for testing triangle-freeness in boolean functions

Bhattacharyya, A. and Xie, N. (2010) · 2010

Later among the works it cites.

An improved construction of progression-free sets

Elkin, M. (2010) · 2010

Later among the works it cites.

On the Complexity of Matrix Multiplication

Stothers, A. J. (2010) · 2010

Later among the works it cites.

Testing linear-invariant non-linear properties

Bhattacharyya, A., Chen, V., Sudan, M., and Xie, N. (2011) · 2011

Later among the works it cites.

Testing odd-cycle-freeness in boolean functions

Bhattacharyya, A., Grigorescu, E., Raghavendra, P., and Shapira, A. (2012) · 2012

Later among the works it cites.