Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Mutual Search

Algebra & Discrete Mathematics

Speaker: Prof. Matthew Franklin, UC Davis Computer Science
Location: 693 Kerr
Start time: Thu, Feb 6 2003, 12:10PM

Two (or more) agents are dispersed among n possible locations. How many queries of the form "Anybody at location i?" does it take for them to find each other? We derive lower and upper bounds for several variants of this new search problem. This is joint work with Harry Buhrman, Juan Garay, Jaap-Henk Hoepman, John Tromp, and Paul Vitanyi.