Distribution-free testing lower bound for basic Boolean functions

DOI10.4086/TOC.2009.V005A010MaRDI QIDQ3002810zbMATH OpenOpenAlexFDO

Authors Dana Glasner, Rocco A. Servedio

Publication date 24 May 2011

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2009.v005a010

zbMATH Keywords

conjunctiondecision listdistribution-free testinglinear threshold functionproperty testing

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Theory of computing (68Q99) Randomized algorithms (68W20)

Recommendations

• Distribution-Free Testing Lower Bounds 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

(11)

• Distribution-Free Testing Lower Bounds for Basic Boolean Functions
• Improved approximation of linear threshold functions
• Tight bounds for the distribution-free testing of monotone conjunctions
• Testing Basic Boolean Formulae
• Almost optimal distribution-free junta testing
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Distribution-free property testing
• On one-sided testing affine subspaces
• Almost Optimal Testers for Concise Representations.
• On one-sided testing affine subspaces
• Relative-error testing of conjunctions and decision lists

This page was built for publication: Distribution-free testing lower bound for basic Boolean functions

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