Source
Fagin (1996; journal version 1999), LIT-1108, not read: no lawful copy could be fetched. The statement is as Fagin, Lotem and Naor (2001), LIT-1115, report it, read in NOTE-924.
What is claimed
A matching lower bound for THEORY-379’s upper bound. If the combining function is strict (score 1 exactly when every grade is 1), then under the same probability model every correct algorithm, in the worst case and with high probability, uses on the order of N^((m−1)/m) k^(1/m) accesses, so Fagin’s Algorithm is optimal up to a constant. For √(Nk) with two lists, this says no algorithm finds the top k of two independent lists with essentially fewer accesses.
What would confirm or reject it
A reading of Fagin’s proof, or a re-derivation, stating which accesses are counted and what “with high probability” quantifies over. A lower bound over all correct algorithms with random access allowed needs an adversary argument; the report gives none. It would be rejected by a correct algorithm beating the bound under the stated model.
What this does not say
- Anything for non-strict functions. For max, a simple algorithm uses at most mk sorted accesses (LIT-1115), so the bound fails there.
- Anything per instance. It is a worst-case, high-probability bound. Fagin, Lotem and Naor’s threshold algorithm is instance optimal (THEORY-363), a different kind of guarantee.
- That independence alone is the model. THEORY-379’s re-derivation of the upper bound needed at least m − 1 of the orderings to be uniformly random as well as independent: two deterministic lists in opposite orders are independent, and Fagin’s Algorithm then needs depth about N/2. What Fagin’s own model requires is the open part of this entry.