Valiant & Valiant's real, non-concurrent antecedent to the n·log n family is their own 2011 STOC paper, proving a matching O(n/log n) sample complexity for entropy and support-size estimation — a different problem than species-count prediction

statistics-of-the-unseenextrapolation-limitinformation-theorysample-complexitypriority-and-lineageprimary-source-verification

Four to five years before either the 2015 or 2016 species-prediction papers, Gregory Valiant and Paul Valiant published "Estimating the Unseen: An n/log(n)-sample Estimator for Entropy and Support Size, Shown Optimal via New CLTs" (STOC 2011). Its abstract states: "Our algorithm estimates these properties up to an arbitrarily small additive constant, using O(n/ log n) samples, where n is a bound on the support size," and the paper's introduction claims the result "settles the longstanding... question of the sample complexities of these estimation problems, up to constant factors," backed by a matching lower bound of Ω(n/log n) samples. This is a genuinely earlier result — not a same-problem concurrent proof, but a different-problem one: how many samples are needed to estimate entropy or support size to a fixed additive accuracy, rather than how far ahead one can predict newly seen species counts (claim-orlitsky-suresh-wu-nlogn-horizon-proven-optimal-via-matched-minimax-lower-bound). It establishes the same log-factor structure years before the species-prediction race between Orlitsky, Suresh & Wu and Valiant & Valiant's own 2015 paper (claim-valiant-2015-nlogn-range-matches-osw-but-error-metric-exponentially-weaker).

Orlitsky, Suresh & Wu's own reference list cites this 2011 paper directly (as [VV11]) and treats it as distinct from the concurrent [VV15] paper — independent confirmation, from the rival camp, that these are two separate results rather than one result restated. This corrects a compression in claim-unseen-mass-is-predictable-only-to-n-log-n, which had folded both Valiant-authored papers into a single "reached the same limit concurrently" sentence without distinguishing them.