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

DOI10.1016/0020-0190(94)90052-3zbMath1028.68948OpenAlexW2045310612WikidataQ127248473 ScholiaQ127248473MaRDI QIDQ1313712

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) Symbolic computation and algebraic computation (68W30) Randomized algorithms (68W20)

Related Items

Randomization and the computational power of analytic and algebraic decision trees, Selecting the \(k\) largest elements with parity tests, On the decisional complexity of problems over the reals

Cites Work

• Proving simultaneous positivity of linear forms