Sunflowers and testing triangle-freeness of functions

DOI10.1145/2688073.2688084zbMath1379.68340arXiv1411.4692OpenAlexW2497858693MaRDI QIDQ2410684

Ning Xie, Ishay Haviv

Publication date: 18 October 2017

Published in: Computational Complexity, Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1411.4692

zbMATH Keywords

lower boundsproperty testingsunflowerstriangle-freeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Related Items (6)

Universal points in the asymptotic spectrum of tensors ⋮ A polynomial bound for the arithmetic \(k\)-cycle removal lemma in vector spaces ⋮ A tight bound for Green's arithmetic triangle removal lemma in vector spaces ⋮ Asymptotic tensor rank of graph tensors: beyond matrix multiplication ⋮ The asymptotic induced matching number of hypergraphs: balanced binary strings ⋮ Lower bounds for testing triangle-freeness in Boolean functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On sunflowers and matrix multiplication
• A new proof of the graph removal lemma
• On the hardness of approximating minimum vertex cover
• Matrix multiplication via arithmetic progressions
• A generalization of Meshulam's theorem on subsets of finite abelian groups with no 3-term arithmetic progression
• A combinatorial proof of the removal lemma for groups
• The monotone circuit complexity of Boolean functions
• Combinatorial properties of systems of sets
• Extensions of generalized product caps
• An improved construction of progression-free sets
• A removal lemma for systems of linear equations over finite fields
• On subsets of finite Abelian groups with no 3-term arithmetic progressions
• Lower bounds for testing triangle-freeness in Boolean functions
• A Szemerédi-type regularity lemma in abelian groups, with applications
• New bounds on cap sets
• Graph limits and parameter testing
• Improved Lower Bounds for Testing Triangle-freeness in Boolean Functions via Fast Matrix Multiplication
• Property testing and its connection to learning and approximation
• Intersection Theorems for Systems of Sets
• A proof of Green's conjecture regarding the removal properties of sets of linear equations
• Testing subgraphs in large graphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• A unified framework for testing linear‐invariant properties
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• On Active and Passive Testing
• Multiplying matrices faster than coppersmith-winograd
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression

This page was built for publication: Sunflowers and testing triangle-freeness of functions