A canonical form for testing Boolean function properties

DOI10.1007/978-3-642-22935-0_39MaRDI QIDQ3088118zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Testing Odd-Cycle-Freeness in Boolean Functions
• Testing odd-cycle-freeness in Boolean functions
• A characterization of constant-sample testable properties
• Testing properties of graphs and functions
• Lower bounds for testing triangle-freeness in Boolean functions

Cites work

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

Cited in

(6)

• Testing Odd-Cycle-Freeness in Boolean Functions
• Testing 2-asummability using a property of canonical extremal vertices
• Two new perspectives on multi-stage group testing
• scientific article; zbMATH DE number 6129640 (Why is no real title available?)
• A characterization of constant-sample testable properties
• Statistical estimation of the structure of a finite population

This page was built for publication: A canonical form for testing Boolean function properties

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