[Colloquium] Reminder: TTI-C Show and Tell Today @ 12:15pm

[Katherine Cumming]

Show and Tell Series
 
Speaker:  Jaikumar Radhakrishnan, TTI-C
Speaker's homepage:  http://www.tti-c.org//radhakrishnan.html
<http://www.tti-c.org/radhakrishnan.html> 
 
Time:  Tuesday, March 29th @ 12:15pm
Location:  TTI-C Conference Room 
Lunch/Refreshments provided
 
Title: From Graph Covering to Graph Entropy
 
Abstract: 
Graph entropy was defined in 1973 by Korner in connection with a problem
about coding for an information source with an ambiguous alphabet. It
has subsequently been used as a tool for showing lower bounds for
problems that arise in computing, for example, in hashing and sorting
under partial information. There are several equivalent definitions of
graph entropy.
 
In this talk, we will concentrate on two of these definitions and show
how they follow naturally by generalizing the combinatorial and
information theoretic arguments used for studying graph covering (by
Krichevskii 1965, Hansel 1964, Pippenger 1977, Fredman and Komlos 1984).
We will not assume any background in graph entropy or graph covering and
will review the necessary information theoretic concepts (entropy,
conditional entropy, mutual information) as we need them. If there is
time, we will also descibe an application.
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20050329/faf57f95/attachment.htm