Exact Asymptotics in Channel Coding

Information-theoretic results describing the limits of reliable
communication over noisy channels are typically asymptotic in the
block length. In practice, however, small block lengths are desirable
and thus the speed of convergence of these characterizations is important.
Classical results show that the error probability converges to
zero exponentially fast with the block length if the data rate
is fixed. But this exponent is very small in the regime of practical
interest, so the subexponential "pre-factor" plays an important
role. Yet very little is known about the pre-factor.

Using techniques from probability theory, convex optimization.
and information theory, we characterize the order of the pre-factor
for all but a degenerate class of channels; for this class, the
results tightly bound the order. These results provide the first
order-improvement in pre-factor bounds in several decades. Time
permitting, I will also discuss error probability estimates in
the "moderate deviations" regime in which the rate approaches
capacity and the error probability tend to zero simultaneously.

Aaron Wagner is an Associate Professor in the School of Electrical and Computer
Engineering at Cornell University. He received the B.S. degree from
the University of Michigan, Ann Arbor, and the M.S. and Ph.D. degrees
from the University of California, Berkeley. During the 2005-2006
academic year, he was a Postdoctoral Research Associate in the
Coordinated Science Laboratory at the University of Illinois at
Urbana-Champaign and a Visiting Assistant Professor in the
School of Electrical and Computer Engineering at Cornell.
He has received the NSF CAREER award, the David J. Sakrison Memorial Prize
from the U.C. Berkeley EECS Dept., the Bernard Friedman Memorial
Prize in Applied Mathematics from the U.C. Berkeley Dept. of Mathematics,
and teaching awards at the Department, College, and University level.