Average-Case Lower Bounds for Noisy Boolean Decision Trees

DOI10.1137/S0097539796310102MaRDI QIDQ4210156zbMATH OpenOpenAlexFDO

Authors

Publication date 21 September 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539796310102

zbMATH Keywords

reliabilityfault-tolerancenoisy computationerror-correction

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Searching and sorting (68P10) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Recommendations

• Lower bounds for noisy Boolean decision trees
• Computing with Noisy Information
• On the complexity of finite random functions
• Decision trees with Boolean threshold queries
• Rounds vs queries trade-off in noisy computation

Cites work

• scientific article; zbMATH DE number 3568556 (Why is no real title available?)
• scientific article; zbMATH DE number 1256667 (Why is no real title available?)
• Computing with Noisy Information
• Constant depth circuits, Fourier transform, and learnability
• Lower bounds for the complexity of reliable Boolean circuits with noisy gates
• Probability Inequalities for Sums of Bounded Random Variables

Cited in

(8)

• Rounds vs queries trade-off in noisy computation
• On the power of parity queries in Boolean decision trees
• scientific article; zbMATH DE number 7758330 (Why is no real title available?)
• RELIABLE INTERNET-BASED MASTER-WORKER COMPUTING IN THE PRESENCE OF MALICIOUS WORKERS
• scientific article; zbMATH DE number 1179978 (Why is no real title available?)
• Tree tribes and lower bounds for switching lemmas
• Computing with Noisy Information
• On the decision tree complexity of threshold functions

This page was built for publication: Average-Case Lower Bounds for Noisy Boolean Decision Trees

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