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

摘要

Understanding the query complexity for testing linear-invariant properties has been a central open problem in the study of algebraic property testing. Triangle-freeness in Boolean functions is a simple property whose testing complexity is unknown. Three B