Proclaiming dictators and juntas or testing Boolean formulae

DOI10.1007/3-540-44666-4_30MaRDI QIDQ4780801zbMATH OpenFDO

Authors Michal Parnas, Dana Ron, Alex Samorodnitsky

Publication date 21 November 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2129/21290273

Mathematics Subject Classification ID

Boolean functions (06E30) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Recommendations

• Testing Basic Boolean Formulae
• An improved dictatorship test with perfect completeness
• Testing juntas nearly optimally
• Distribution-Free Testing Lower Bounds for Basic Boolean Functions
• Tight bounds for the distribution-free testing of monotone conjunctions

Cited in

(7)

• A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem.
• A lower bound for testing juntas
• Testing Basic Boolean Formulae
• An improved dictatorship test with perfect completeness
• \(\omega\)-regular languages are testable with a constant number of queries
• Distribution-free connectivity testing for sparse graphs
• Attribute estimation and testing quasi-symmetry

This page was built for publication: Proclaiming dictators and juntas or testing Boolean formulae

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