Speaker: Professor Santosh S. Venkatesh (University of Pennsylvania)

Title: Coverage and Connectivity in Metric Random Graphs

Abstract: 
Metric random graphs are encountered in continuum percolation
and may be used to model random deployments of sensor networks. In this setting,
points are randomly deployed in, say, the unit disc with each point the centre
of a tiny ``disc of visibility.'' Coverage questions in this setting are
familiar in machine learning from Vapnik-Chervonenkis theory: Does the random
collection of tiny discs cover the unit disc? A related question deals with
connectivity. A graph is induced on the random collection of points by drawing edges
between neighbours, i.e., pairs of points that lie within each others discs of
visibility. Is the random graph connected? In this talk I will discuss
how a phase transition for connectivity manifests itself at a critical radius
of the disc of visibility, discuss the links with coverage phenomena, and
provide extensions to higher dimensions and graphs with node extinctions. The
latter question has implications for the lifetime of sensor networks.

Bio: 
Santosh S. Venkatesh received the B.Tech. degree in Electrical
Engineering from the Indian Institute of Technology, Bombay in 1981, and the Ph.D.
in Electrical Engineering from the California Institute of Technology in
1987.  Since 1986 he has been on the faculty of the Department of Electrical
and Systems Engineering at the University of Pennsylvania. His research
interests are in computational learning theory, information theory, wireless
communication, and neural networks.