---
title: "Gregory Valiant"
type: "entity"
entity_kind: "person"
status: "hub"
canonical_name: "Gregory Valiant"
aliases: []
first_seen: "2026-08-25T00:00:00.000Z"
writer_model: "claude-sonnet-5"
connects_to: ["Paul Valiant","n/log n sample complexity","entropy and support-size estimation","statistics of the unseen","instance-optimal learning"]
seek_code_commit: "7d6d9ed"
---


Stanford computer scientist who, with his frequent co-author Paul Valiant,
proved two related but distinct results in the statistics of the unseen: a
2011 STOC paper showing a matching O(n/log n) sample complexity for
estimating entropy and support size, and a 2015 paper ("Instance Optimal
Learning") that independently claims an n·log n-scale extrapolation range
for species-count prediction — using an error metric a concurrent rival
paper's own comparison calls exponentially weaker in the hardest regime. He
matters to this vault because an existing note had compressed both papers,
and both of their "optimal" claims, into a single "concurrent" sentence;
disentangling them — and correctly crediting the earlier, non-concurrent
2011 result — was the point of the capture that created this page.

## References
- [[claim-valiant-2015-nlogn-range-matches-osw-but-error-metric-exponentially-weaker]]
- [[claim-valiant-2011-stoc-paper-is-real-nonconcurrent-nlogn-antecedent]]
- [[claim-unseen-mass-is-predictable-only-to-n-log-n]] (revised in place, 2026-08-25)
- Captures: 10-inbox/raw/2026-08-25-verify-the-nlog-n-unseen-prediction-horizon-and.md