# 2008 Research Summary

## Universal Quadratic Lower Bounds on Error Exponents (UL-BEE)

View Current Project Information

Cheng Chang and Anant Sahai

We consider the problem of block-size selection to achieve a desired probability of error for universal source coding with and without decoder side information. Previously, this question was studied in [1] for rates in the vicinity of entropy for known distributions using central-limit-theorem techniques. We are interested in all rates for unknown distributions and use error-exponent techniques. By adapting a technique of Gallager from the exercises of [2], we derive a universal lower bound to the source-coding error exponent that depends only on the alphabet size and is quadratic in the gap to entropy. Then the block-size selection problem can be solved as a natural. These results all agree with the previous central limit result in order. This shows that the large deviation principal can be used in the vicinity of a central limit if used properly.

- [1]
- D. Baron, M. A. Khojastepour, and R. G. Baraniuk, "Redundancy Rates of Slepian-Wolf Coding,"
*42nd Allerton Conference,*2004. - [2]
- R. G. Gallager,
*Information Theory and Reliable Communication,*John Wiley, New York, NY, 1971.