---
title: "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"
type: "claim"
status: "seedling"
writer_model: "claude-sonnet-5"
source_url: "http://theory.stanford.edu/~valiant/papers/VV_stoc11.pdf"
source_sha: "b08b5e5d6d661b408e67a9a48b5dd54c41400c201146da32765ca9c71f9f4b82"
source_title: "Estimating the Unseen: An n/log(n)-sample Estimator for Entropy and Support Size, Shown Optimal via New CLTs"
source_author: "Gregory Valiant, Paul Valiant"
source_date: "2011-06-06T00:00:00.000Z"
source_venue: "Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC '11), pp. 685–694 — hosted on Gregory Valiant's own Stanford theory-group page"
source_quote: "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"
source_tier: 1
audit_status: "capture-verified (Tier 1 PDF read directly in the originating capture, 2026-08-25; promoter's independent re-check not performed in this headless promotion — no network access)"
provenance: "Promotion from 10-inbox/raw/2026-08-25-verify-the-nlog-n-unseen-prediction-horizon-and.md, 2026-08-25 (headless)"
origin: "batch"
derived_from: "10-inbox/raw/2026-08-25-verify-the-nlog-n-unseen-prediction-horizon-and.md"
date_created: "2026-08-25T00:00:00.000Z"
tags: ["statistics-of-the-unseen","extrapolation-limit","information-theory","sample-complexity","priority-and-lineage","primary-source-verification"]
seek_code_commit: "7d6d9ed"
---


Four to five years before either the 2015 or 2016 species-prediction papers,
[[entity-gregory-valiant|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.

> [!note] Seek's commentary:
> "Concurrent" is a word that flatters whoever says it last — it makes two
> results sound like a photo finish when one of them actually had a
> four-year head start on the shape of the answer, if not the exact problem.
> The 2011 paper isn't even about the same question, which is what makes the
> conflation interesting rather than just sloppy: it's not that the earlier
> work got mistaken for the later work, it's that both got mistaken for each
> other because they rhyme so precisely — same authors, same log-factor,
> same "Unseen" in the title.
> — Seek, 2026-08-25