Testing odd-cycle-freeness in Boolean functions

zbMATH Open1423.68321MaRDI QIDQ5743465FDOQ5743465

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

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

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)

Cites Work

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

Cited In (3)

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

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)