We consider the problem of determining whether or not there exists a path from a source vertex to a target vertex in a directed graph from which vertices may have been deleted at random. This problem has been studied in the past as one of global search, assuming the status of any vertex may be queried at any time. We consider how the answer differs in the case of local search, where the status of a vertex may be queried only if a path from the source to it has already been established. We show that for some graphs (which have been studied as telephone switching networks) local search may require exponentially more queries on average than global search. This talk presents joint work with Andrew Hunter.

Nicholas Pippenger was born in Abington, PA, in 1947. He received the B.S. degree in Natural Science from Shimer College, Mt. Carroll (currently Chicago), IL, in 1965. He received the B.S., M.S. and Ph.D. degrees, all in Electrical Engineering, from the Massachusetts Institute of Technology, Cambridge, MA, in 1967, 1969 and 1974, respectively.

He was with the MIT Instrumentation Laboratory (currently the Charles Stark Draper Laboratory), Cambridge, MA, from 1969 to 1973. He worked for IBM at the Thomas J.Watson Research Center, Yorktown Heights, NY, from 1973 to 1980, and at the San Jose Research Laboratory (currently the Almaden Research Center), San Jose, CA, from 1980 to 1989, where he was named an IBM Fellow in 1987. He was Professor of Computer Science at the University of British Columbia, Vancouver, BC, Canada from 1988 to 2003, where he was appointed to a Canada Research Chair in 2001. He was Professor of Computer Science at Princeton University, Princeton, NJ, from 2003 to 2006. He is currently Professor of Mathematics at Harvey Mudd College, Claremont, CA. His research interests center in discrete mathematics and probability, but also extend into communication theory and theoretical computer science. He is the author of Theories of Computability, published by Cambridge University Press in 1997.

Dr. Pippenger is also a Fellow of the Royal Society of Canada (Academy of Science), a Fellow of the Institute of Electrical and Electronics Engineers (IEEE) and a Fellow of the Association for Computing Machinery (ACM). He is a member of the American Mathematical Association, the Mathematical Association of America and the Society for Industrial and Applied Mathematics.