Average-Case Lower Bounds for Noisy Boolean Decision Trees

DOI10.1137/S0097539796310102zbMATH Open0915.68010OpenAlexW1963494112MaRDI QIDQ4210156FDOQ4210156

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

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

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)

Cites Work

• Probability Inequalities for Sums of Bounded Random Variables
• Computing with Noisy Information
• Constant depth circuits, Fourier transform, and learnability
• Title not available (Why is that?)
• Lower bounds for the complexity of reliable Boolean circuits with noisy gates
• Title not available (Why is that?)

Cited In (7)

• Rounds vs queries trade-off in noisy computation
• On the power of parity queries in Boolean decision trees
• Title not available (Why is that?)
• RELIABLE INTERNET-BASED MASTER-WORKER COMPUTING IN THE PRESENCE OF MALICIOUS WORKERS
• 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)