Computational Complexity: Chernoff Turns 100

Guest post by Ravi Boppana

Herman
Chernoff celebrates a milestone today: he turns 100
years old.

We in theoretical computer science know Professor Chernoff
primarily for his ubiquitous Chernoff bounds.
The Chernoff bound is an exponentially small upper bound on the tail of a
random variable, in terms of its moment
generating function.  This bound is particularly useful for the sum of
independent random variables.

Many, many results in theoretical computer science use
Chernoff bounds.  For one set of examples, Chernoff bounds are employed in
the analysis of algorithms such as Quicksort, linear probing in
hashing, MinHash, and
a randomized algorithm for set balancing.  For
another example, Chernoff bounds are used to reduce the error probability in
complexity classes such as BPP.  These
examples merely scratch the surface of the wide-ranging impact that Chernoff
bounds have had.

Professor Chernoff introduced the Chernoff bound in
his seminal
paper from 1952.  Chernoff credits another
Herman (Herman Rubin) for the elegant proof of the bound in this paper.
Similar bounds had been established earlier by Bernstein and
by Cramér.

In his distinguished career, Chernoff was a professor for
decades at Stanford, MIT, and ultimately Harvard.  In May, Harvard proudly
hosted a symposium in
honor of Professor Chernoff’s centenary, which he attended.  The photo above shows him at the symposium, looking as cheerful as ever (photo credit: Professor Sally Thurston).

Beyond his remarkable research accomplishments,
Professor Chernoff has passionately guided an entire generation of exceptional
statisticians.  According to the Mathematical
Genealogy Project, he has advised 26 PhD students, leading to a lineage of
288 mathematical descendants.  Chernoff himself earned his PhD at Brown
University in 1948 under the supervision of Abraham Wald.

Professor Chernoff and his wife, Judy Chernoff, have
been married
for more than 75 years.  A Boston
TV news story said that the Chernoffs are believed to be the oldest
living couple in Massachusetts.  At the symposium in May, Professor
Chernoff doubted the claim, though he had previously acknowledged that it might
be true.  Maybe his cherished field of statistics can be used to
estimate the likelihood of the claim.

On this extraordinary milestone day, we extend our heartfelt
congratulations and warmest wishes to Professor Chernoff.  Happy 100th
birthday, Professor Chernoff!  Mazel tov.