Computing with Noisy Information
From MaRDI portal
Publication:4312419
DOI10.1137/S0097539791195877zbMath0813.68057MaRDI QIDQ4312419
Eli Upfal, Prabhakar Raghavan, Uriel Feige, David Peleg
Publication date: 29 November 1994
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Searching and sorting (68P10) Combinatorics in computer science (68R05) Reliability, testing and fault tolerance of networks and computer systems (68M15)
Related Items
Skyline Computation with Noisy Comparisons, A fast randomized LOGSPACE algorithm for graph connectivity, Towards a reverse Newman's theorem in interactive information complexity, Optimal Dislocation with Persistent Errors in Subquadratic Time, Partial sorting problem on evolving data, Improved algorithms for quantum identification of Boolean oracles, Fast error-tolerant quartet phylogeny algorithms, Unnamed Item, Energy efficient sorting, selection and searching, Resilient level ancestor, bottleneck, and lowest common ancestor queries in dynamic trees, Unnamed Item, The communication complexity of functions with large outputs, Edge and pair queries-random graphs and complexity, Unnamed Item, Unnamed Item, External-memory sorting with comparison errors, The \(K\)-armed dueling bandits problem, Unnamed Item, Designing reliable algorithms in unreliable memories, Spin-the-bottle sort and annealing sort: oblivious sorting via round-robin random comparisons, Information complexity and applications., Binary search in graphs revisited, Searching a Tree with Permanently Noisy Advice, Fast Error-Tolerant Quartet Phylogeny Algorithms, Optimal dislocation with persistent errors in subquadratic time, Resilient dynamic programming, The communication complexity of addition, Optimization with uniform size queries, Improved direct product theorems for randomized query complexity, Unnamed Item, Computing in fault tolerant broadcast networks and noisy decision trees, Longest increasing subsequence under persistent comparison errors, Searching games with errors -- fifty years of coping with liars, Sorting and searching in faulty memories, A novel technique for stochastic root-finding: enhancing the search with adaptive \(d\)-ary search, Resilient Dictionaries for Randomly Unreliable Memory, The price of resiliency: a case study on sorting with memory faults, Approximate minimum selection with unreliable comparisons, Optimal resilient sorting and searching in the presence of memory faults, Unnamed Item, Unnamed Item, Average-Case Lower Bounds for Noisy Boolean Decision Trees, Binary Search in Graphs Revisited, On the decisional complexity of problems over the reals, Playing by searching: Two strategies against a linearly bounded liar, Sorting with Recurrent Comparison Errors, RELIABLE INTERNET-BASED MASTER-WORKER COMPUTING IN THE PRESENCE OF MALICIOUS WORKERS, An efficient noisy binary search in graphs via Median approximation, Quantum walks can find a marked element on any graph, The power of adaptivity in source identification with time queries on the path
