-------------------------------------------------------------------------------
                                       
                                       
                   B O S T O N   U N I V E R S I T Y
                                       
                      Computer Science Department
                                       
                          C O L L O Q U I U M

		Practical ESP: the set reconciliation problem
                
                           Ari Trachtenberg 
			    
                 Electrical and Computer Engineering 
                           Boston University

   			 Wednesday, February 28
			       3:00 PM
                       (Coffee served at 2:45PM)

                                       
                         Seminar Room / MCS 135
                                       

We describe a practical emulation of Extra Sensory Perception
based on recent research with Yaron Minsky (Cornell) and Richard
Zippel (CRL).  The specific problem at hand, that of set reconciliation,
involves determining the mutual difference of the sets of two physically
separated hosts using a minimum communication complexity.  This type of
problem arises naturally from gossip protocols used to disseminate
information, but also has applications to resource discovery, routing,
and mobile synchronization.  We show that two hosts with sets A and B
respectively can be reconciled with one transmission of |A-B| packets,
independently of the individual sizes |A| or |B|.  This is very close to
the information theoretic bound attained by two hosts with ESP.

Host:  Gene Itkis

-------------------------------------------------------------------------------
For colloquium info, including directions, see http://cs-www.bu.edu/colloquium
-------------------------------------------------------------------------------