Sorting from Noisier Samples

DOI10.1137/1.9781611974782.60MaRDI QIDQ4575799zbMATH OpenOpenAlexFDO

Authors Aviad Rubinstein, Shai Vardi

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Combinatorics in computer science (68R05) Searching and sorting (68P10)

Recommendations

• Noisy sorting without resampling
• Sorting noisy data with partial information
• Separating signal from noise
• Noisy Component Extraction (NoiCE)
• Sorting by swaps with noisy comparisons
• Noise in Classification
• Denoising source separation
• Noisy sort, a memory-intensive sorting algorithm

Cited in

(10)

• Resilient Dictionaries for Randomly Unreliable Memory
• Minimax rates and efficient algorithms for noisy sorting
• Noisy sorting without resampling
• Sorting by swaps with noisy comparisons
• Optimal dislocation with persistent errors in subquadratic time
• On reconstructing a hidden permutation
• Optimal sorting with persistent comparison errors
• Top-\(k\) and clustering with noisy comparisons
• An attempt to understand noisy posets
• On the best order of observation in optimal stopping problems

This page was built for publication: Sorting from Noisier Samples

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