Distribution-Free Testing Lower Bounds for Basic Boolean Functions

DOI10.1007/978-3-540-74208-1_36MaRDI QIDQ3603489zbMATH OpenOpenAlexFDO

Authors Dana Glasner, Rocco A. Servedio

Publication date 17 February 2009

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-540-74208-1_36

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational learning theory (68Q32) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Distribution-free testing lower bound for basic Boolean functions
• Tight bounds for the distribution-free testing of monotone conjunctions
• Distribution-free property testing
• Distribution-Free Property-Testing
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

Cited in

(8)

• Distribution-free testing lower bound for basic Boolean functions
• Testing Odd-Cycle-Freeness in Boolean Functions
• Tight bounds for the distribution-free testing of monotone conjunctions
• scientific article; zbMATH DE number 1833420 (Why is no real title available?)
• Testing Basic Boolean Formulae
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Statistical estimation of the structure of a finite population
• Distribution-free proofs of proximity

This page was built for publication: Distribution-Free Testing Lower Bounds for Basic Boolean Functions

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