Lower bounds for testing triangle-freeness in Boolean functions
From MaRDI portal
Publication:2353187
DOI10.1007/s00037-014-0092-1zbMath1332.68056OpenAlexW3136761595MaRDI QIDQ2353187
Publication date: 8 July 2015
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-014-0092-1
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)
Related Items (5)
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 ⋮ Sunflowers and testing triangle-freeness of functions ⋮ On arithmetic progressions in symmetric sets in finite field model
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A new proof of the graph removal lemma
- Matrix multiplication via arithmetic progressions
- Generalizations of the removal lemma
- A combinatorial proof of the removal lemma for groups
- A removal lemma for systems of linear equations over finite fields
- Sunflowers and testing triangle-freeness of functions
- A Szemerédi-type regularity lemma in abelian groups, with applications
- Regular Languages are Testable with a Constant Number of Queries
- An Arithmetic Analogue of Fox's Triangle Removal Argument
- A combinatorial characterization of the testable graph properties
- Graph limits and parameter testing
- Improved Lower Bounds for Testing Triangle-freeness in Boolean Functions via Fast Matrix Multiplication
- Testing low-degree polynomials over prime fields
- Testability and repair of hereditary hypergraph properties
- Property testing and its connection to learning and approximation
- Testing Polynomials over General Fields
- A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
- Every monotone graph property is testable
- Three theorems regarding testing graph properties
- Testing Basic Boolean Formulae
- Testing subgraphs in large graphs
- Robust Characterizations of Polynomials with Applications to Program Testing
- Green's conjecture and testing linear-invariant properties
- Convex and Discrete Geometry
- Testing Linear-Invariant Non-Linear Properties
- Some 3CNF Properties Are Hard to Test
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
- Testing subgraphs in directed graphs
- Efficient testing of large graphs
This page was built for publication: Lower bounds for testing triangle-freeness in Boolean functions
