Testing odd-cycle-freeness in Boolean functions

MaRDI QIDQ5743465zbMATH OpenFDO

Authors Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira

Publication date 10 May 2019

Full work available at URL https://dl.acm.org/citation.cfm?id=2095206

zbMATH Keywords

Cayley graphsFourier analysisBoolean functionsproperty testing

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Density (toughness, etc.) (05C42) Boolean functions (06E30)

Recommendations

• Testing Odd-Cycle-Freeness in Boolean Functions
• Testing linear-invariant non-linear properties
• Testing linear-invariant non-linear properties
• Lower bounds for testing triangle-freeness in Boolean functions
• Lower bounds for testing triangle-freeness in Boolean functions

Cites work

• scientific article; zbMATH DE number 3609704 (Why is no real title available?)
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• A Szemerédi-type regularity lemma in abelian groups, with applications
• A removal lemma for systems of linear equations over finite fields
• Algebraic property testing: the role of invariance
• Algorithmic aspects of property testing in the dense graphs model
• Efficient testing of large graphs
• Generalizations of the removal lemma
• Green's conjecture and testing linear-invariant properties
• Lower bounds for testing triangle-freeness in Boolean functions
• Property testing and its connection to learning and approximation
• Random sampling and approximation of MAX-CSPs
• Regularity Lemma for k-uniform hypergraphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Self-testing/correcting with applications to numerical problems
• Testability and repair of hereditary hypergraph properties
• Testing Fourier Dimensionality and Sparsity
• Testing Reed–Muller Codes
• Testing \(k\)-colorability
• Testing linear-invariant non-linear properties
• Testing subgraphs in large graphs
• The Algorithmic Aspects of the Regularity Lemma
• The counting lemma for regular k‐uniform hypergraphs
• Three theorems regarding testing graph properties
• Tight Bounds for Testing Bipartiteness in General Graphs
• Tolerant property testing and distance approximation

Cited in

(3)

• Testing Odd-Cycle-Freeness in Boolean Functions
• A canonical form for testing Boolean function properties
• Verification, Model Checking, and Abstract Interpretation

This page was built for publication: Testing odd-cycle-freeness in Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5743465)