(Details on registration and student travel awards for the 2012 IEEE Conference on
Computational Complexity in Porto available at
New York Area Theory Day information here.
Tom Cover passed away recently. Today we have a guest post about him from Yoav Freund which was
written with help from Gabor Lugosi, Nicolo Cesa-Bianchi, Avrim Blum, Rob Schapire,
Sanjoy Dasgupta and Manfred Warmuth.
Tom Cover was a leading light, a mentor and an inspiration. I was shocked to hear of his passing away.
It was only a few weeks ago that I saw him in the recent ITA conference in San Diego. As usual,
engrossed in conversation with a young colleague, gesticulating with his long arms to punctuate his words.
I was first introduced to Cover's work when, as a graduate student in UCSC, I read the classical book of
Cover and Thomas on Information theory. Lured by the psychedelic cover I was enchanted by
the lucid examples (betting in the horse races) and the elegant math. Like me, many computer scientists
were introduced to the deep connections between probability, information, coding and prediction.
It is a standard reference for information theory in computer science.
Beyond the book, Cover wrote wrote many of the foundational papers in information theory and
its applications. A very partial list of his contribution include his work with Peter Hart on
the convergence of the nearest neighbor classifier, His work on the capacity of linear
classifiers preceded Vapnik and Chevonenkis. His work on finite memory algorithm for deciding
whether the bias of a coin is rational or irrational is a beautiful mind-bender. His papers on
gambling and portfolio management started much of the work on online learning.
Speaking of online learning, Cover took part in the first workshop on online learning that was held
in UC Santa Cruz at 1992. Cover, with his typical sense of humor, suggested we call the workshop
something for nothing
. Later we had a bon-fire by the beach, I will always remember
Cover as he was that day, a brilliant scientist, a wonderful communicator, a pursuer of beauty and of fun.
There's also his work on "Nearest neighbor pattern classification"
(mid-60s, with Hart).
Yes, that's a very important one. He had two other early influential
papers on nearest neighbor classification:
Thomas M. Cover. Rates of Convergence for Nearest Neighbor Procedures.
Proceedings of The Hawaii International Conference on System Sciences
Honolulu, Hawaii, January 1968.
Thomas M. Cover. Estimation by the Nearest Neighbor Rule. IEEE
Transactions on Information Theory, IT-14(1):50--55, January 1968.
Even before Vapnik-Chervonenkis, he calculated the VC shatter coefficient for half spaces:
Thomas M. Cover. Capacity Problems for Linear Machines. Chapter in the
book Pattern Recognition,
Thompson Book Co., 1968. ed. by L. Kanal.
Then, of course, he was among the pioneers of online learning:
Thomas M. Cover. Universal Gambling Schemes and the Complexity
Measures of Kolmogorov and Chaitin. Stanford University Dept. of
Statistics Technical Report No. 12, October 1974.
Robert M. Bell and Thomas M. Cover. Competitive Optimality of
Logarithmic Investment. Mathematics of Operations Research,
5(2):161--166, May 1980.
Thomas M. Cover. Log Optimal Portfolios. Chapter in Gambling Research:
Gambling and Risk Taking
, Seventh International Conference, Vol 4:
Quantitative Analysis and Gambling, ed. by W.E. Eadington, 1987, Reno,
Paul H. Algoet and Thomas M. Cover. Asymptotic Optimality and
Asymptotic Equipartition Properties of Log-Optimum Investment.
The Annals of Probability,
, 16(2): 876-898, 1988.
Robert Bell and Thomas M. Cover. Game-Theoretic Optimal Portfolios.
34(6): 724-733, June 1988.
He was among the first to use Blackwell's approachability for online
Thomas M. Cover and David H. Gluss. Empirical Bayes Stock Market
Portfolios. Advances in Applied Mathematics,
This one was a big seminal paper for structural risk minimization:
Andrew R. Barron and Thomas M. Cover. Minimum Complexity Density
Estimation. IEEE Transactions on Information Theory,
Avrim Blum says:
I don't know if the following had a big influence on COLT but I
remember Ron Rivest describing this result which totally blew my mind:
COVER, THOMAS M (1973). On determining the irrationality of the mean
of a random variable. Ann. Math. Statist. 1862-871.
COVER & HIRSCHLER (1975). A finite memory test of the irrationality of
the parameter of a coin. Annals of Statistics,
You are observing a sequence of flips of a coin of unknown bias p, and
after each flip must predict if p is rational or irrational. Shows that
with prob 1 you can do this making only a finite number of