Testing Odd-Cycle-Freeness in Boolean Functions
From MaRDI portal
Publication:3168444
DOI10.1017/S0963548312000363zbMath1259.68149arXiv1105.1325MaRDI QIDQ3168444
Asaf Shapira, Prasad Raghavendra, Arnab Bhattacharyya, Elena Grigorescu
Publication date: 31 October 2012
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1105.1325
Graph theory (including graph drawing) in computer science (68R10) Boolean functions (06E30) Randomized algorithms (68W20) Density (toughness, etc.) (05C42) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items (2)
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
Cites Work
- Generalizations of the removal lemma
- Self-testing/correcting with applications to numerical problems
- A removal lemma for systems of linear equations over finite fields
- Random sampling and approximation of MAX-CSPs
- Tolerant property testing and distance approximation
- A Szemerédi-type regularity lemma in abelian groups, with applications
- Testing k-colorability
- Property testing and its connection to learning and approximation
- Testing Reed–Muller Codes
- A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
- The Algorithmic Aspects of the Regularity Lemma
- Three theorems regarding testing graph properties
- Tight Bounds for Testing Bipartiteness in General Graphs
- Testing subgraphs in large graphs
- Regularity Lemma for k-uniform hypergraphs
- Robust Characterizations of Polynomials with Applications to Program Testing
- Invariance in Property Testing
- The counting lemma for regular k‐uniform hypergraphs
- Algorithmic Aspects of Property Testing in the Dense Graphs Model
- Testing Fourier Dimensionality and Sparsity
- Efficient testing of large graphs
This page was built for publication: Testing Odd-Cycle-Freeness in Boolean Functions
