A Canonical Form for Testing Boolean Function Properties

DOI10.1007/978-3-642-22935-0_39zbMath1343.68293OpenAlexW1803383448MaRDI QIDQ3088118

Dana Dachman-Soled, Rocco A. Servedio

Publication date: 17 August 2011

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22935-0_39

zbMATH Keywords

Boolean functionsproperty testing

Mathematics Subject Classification ID

Boolean functions (06E30) Randomized algorithms (68W20)

Related Items (1)

Two new perspectives on multi-stage group testing

Cites Work

• Testing juntas
• Self-testing/correcting with applications to numerical problems
• Testing Halfspaces
• Three theorems regarding testing graph properties
• Testing Basic Boolean Formulae
• Testing juntas nearly optimally
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Testing Fourier Dimensionality and Sparsity
• Exact learning of DNF formulas using DNF hypotheses

This page was built for publication: A Canonical Form for Testing Boolean Function Properties