Maximum selection and sorting with adversarial comparators

MaRDI QIDQ4614093zbMATH OpenFDO

Authors Jayadev Acharya, Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, Ananda Theertha Suresh

Publication date 30 January 2019

Full work available at URL http://jmlr.csail.mit.edu/papers/v19/17-165.html

zbMATH Keywords

adversarial comparatorsdensity estimationnoisy sortingScheffe estimator

Mathematics Subject Classification ID

Density estimation (62G07) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Approximate minimum selection with unreliable comparisons
• Tolerant algorithms
• A sort of an adversary

Cites work

• A nearly instance optimal algorithm for top-k ranking under the multinomial logit model
• A theory of the learnable
• A Useful Convergence Theorem for Probability Distributions
• Combinatorial analysis of quicksort algorithm
• Combinatorial methods in density estimation
• Competitive analysis of the top-K ranking problem
• Computing with Noisy Information
• scientific article; zbMATH DE number 1003289 (Why is no real title available?)
• scientific article; zbMATH DE number 5719289 (Why is no real title available?)
• scientific article; zbMATH DE number 1099195 (Why is no real title available?)
• scientific article; zbMATH DE number 742989 (Why is no real title available?)
• scientific article; zbMATH DE number 3073477 (Why is no real title available?)
• Large Deviations for Quicksort
• Noisy binary search and its applications
• Noisy sorting without resampling
• On the learnability of discrete distributions
• Parallel algorithms for select and partition with noisy comparisons
• Rank Centrality: Ranking from Pairwise Comparisons
• Robust estimators in high-dimensions without the computational intractability
• Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues

Cited in

(2)

• Efficient Sorting in a Dynamic Adverse-Selection Model
• On the sample complexity of privately learning unbounded high-dimensional Gaussians

This page was built for publication: Maximum selection and sorting with adversarial comparators

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