Distribution-Free Testing Lower Bounds for Basic Boolean Functions

DOI10.1007/978-3-540-74208-1_36zbMATH Open1171.68726OpenAlexW2123346810MaRDI QIDQ3603489FDOQ3603489

Rocco A. Servedio, Dana Glasner

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

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

Mathematics Subject Classification ID

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

Cited In (5)

• Title not available (Why is that?)
• Testing Basic Boolean Formulae
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Statistical estimation of the structure of a finite population
• Testing Odd-Cycle-Freeness in Boolean Functions

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)