Average-Case Lower Bounds for Noisy Boolean Decision Trees

DOI10.1137/S0097539796310102zbMath0915.68010OpenAlexW1963494112MaRDI QIDQ4210156

No author found.

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-toleranceerror-correctionnoisy computation

Mathematics Subject Classification ID

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

Related Items (2)

Unnamed Item ⋮ RELIABLE INTERNET-BASED MASTER-WORKER COMPUTING IN THE PRESENCE OF MALICIOUS WORKERS

Cites Work

• Constant depth circuits, Fourier transform, and learnability
• Lower bounds for the complexity of reliable Boolean circuits with noisy gates
• Computing with Noisy Information
• Probability Inequalities for Sums of Bounded Random Variables
• Unnamed Item
• Unnamed Item

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