scientific article; zbMATH DE number 7053342

zbMath1423.68321MaRDI QIDQ5743465

Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira, Prasad Raghavendra

Publication date: 10 May 2019

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

Fourier analysisBoolean functionsCayley graphsproperty testing

Mathematics Subject Classification ID

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)

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
• Testability and repair of hereditary hypergraph properties
• 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
• Green's conjecture and testing linear-invariant properties
• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: