Sunflowers and testing triangle-freeness of functions
From MaRDI portal
DOI10.1145/2688073.2688084zbMath1379.68340arXiv1411.4692OpenAlexW2497858693MaRDI QIDQ2410684
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
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
