A randomized algorithm for finding maximum with O(( n)^2) polynomial tests

DOI10.1016/0020-0190(94)90052-3MaRDI QIDQ1313712zbMATH OpenOpenAlexWikidataFDO

Authors Hing-Fung Ting, Andrew Chi-Chih Yao

Publication date 22 March 1994

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(94)90052-3

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Symbolic computation and algebraic computation (68W30)

Recommendations

• On the decisional complexity of problems over the reals
• A generalization of binary search
• Selecting the k largest elements with parity tests
• scientific article; zbMATH DE number 1303027
• Randomized selection in \(n+C+o(n)\) comparisons

Cites work

• Proving simultaneous positivity of linear forms

Cited in

(6)

• Randomization and the computational power of analytic and algebraic decision trees
• On the decisional complexity of problems over the reals
• An \(O(mn^ 2)\) algorithm for the maximin problem in \(E^ 2\)
• Selecting the k largest elements with parity tests
• scientific article; zbMATH DE number 1303027 (Why is no real title available?)
• Finding the maximum with linear error probabilities: a sequential analysis approach

This page was built for publication: A randomized algorithm for finding maximum with \(O((\log n)^2)\) polynomial tests

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