Computing with Noisy Information
From MaRDI portal
Publication:4312419
DOI10.1137/S0097539791195877zbMath0813.68057MaRDI QIDQ4312419
Prabhakar Raghavan, David Peleg, Uriel Feige, Eli Upfal
Publication date: 29 November 1994
Published in: SIAM Journal on Computing (Search for Journal in Brave)
68P10: Searching and sorting
68R05: Combinatorics in computer science
68M15: Reliability, testing and fault tolerance of networks and computer systems
Related Items
Searching games with errors -- fifty years of coping with liars, Improved algorithms for quantum identification of Boolean oracles, Sorting and searching in faulty memories, The price of resiliency: a case study on sorting with memory faults, Optimal resilient sorting and searching in the presence of memory faults, A fast randomized LOGSPACE algorithm for graph connectivity, Playing by searching: Two strategies against a linearly bounded liar, On the decisional complexity of problems over the reals, Computing in fault tolerant broadcast networks and noisy decision trees, Average-Case Lower Bounds for Noisy Boolean Decision Trees