Selecting the \(k\) largest elements with parity tests

DOI10.1016/S0166-218X(99)00193-6zbMath0953.68149DBLPjournals/dam/LamT00OpenAlexW2034302955WikidataQ58063071 ScholiaQ58063071MaRDI QIDQ1975371

Hing-Fung Ting, Tak-Wah Lam

Publication date: 9 April 2000

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(99)00193-6

zbMATH Keywords

selectionrandomized algorithmlower boundparity tests

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items (1)

Neural Simpletrons: Learning in the Limit of Few Labels with Directed Generative Networks

Cites Work

• On selecting the k largest with median tests
• On selecting the \(k\) largest with restricted quadratic queries
• A randomized algorithm for finding maximum with \(O((\log n)^2)\) polynomial tests
• A Unified Lower Bound for Selection and Set Partitioning Problems
• Bounds for Selection
• A Counting Approach to Lower Bounds for Selection Problems
• Decision trees
• Unnamed Item

This page was built for publication: Selecting the \(k\) largest elements with parity tests