[ut.theory] seminar

gulak@eecg.toronto.edu (Glenn Gulak) (05/25/89)

			
			     SEMINAR

			Monday, May 29, 1989
			   2:00 - 3:00 pm
		      Room 202, Galbraith Bldg	




               Who should speak when I want to talk:

                feedback in discrete communication


                           Alon Orlitsky

                      AT&T Bell Laboratories


S_X and S_Y are finite sets.  (X,Y) is a random variable distributed over 
S_X \times S_Y according to some probability distribution p(x,y).  Person 
P_X knows X, Person P_Y knows Y, and both know p.  They communicate in order 
for P_Y to learn X. P_X may or may not learn Y.  How many information bits 
must be transmitted (by both persons) in the worst case? 

C_1(p) is the number of bits required when only one message is allowed, 
necessarily from P_X to P_Y.  C_2(p) is the number of bits required when 
only two messages are permitted:  P_Y transmits a message to P_X then P_X 
responds with a message to P_Y.  C_\infty(p) is the number of bits required 
when P_X and P_Y can communicate back and forth.  Messages from P_Y to P_X 
are called feedback. 

The maximal reduction in communication achievable via feedback is one bit 
away from logarithmic:  C_\infty(p) >= log C_1(p) + 1 for all probability 
distributions p, while there are distributions for which equality holds. 
Therefore C_1(p) can be exponentially larger than C_\infty(p).  Yet C_2(p) 
cannot.   With just one feedback message the number of bits required is at 
most four times larger than the minimal:  C_2(p) <= 4*C_\infty(p)+2.

Surprisingly, for almost all sparse probability distributions, P_Y who 
wants to say nothing must transmit almost all the bits in order to achieve 
the minimal number: C_\infty(p). The number of bits transmitted by P_Y can 
be appreciably reduced only if P_X transmits exponentially more than 
C_\infty(p) bits. 

__________________________________________________________________________

rackoff@ai.toronto.edu (Charles Rackoff) (05/25/89)

Don't forget Silvio Micali's seminar tomorrow at 11:00.   Charlie