TIME: 1:30-2:20 pm,  February 19, 2008

PLACE: CSE 503  

SPEAKER: Mohsen Bayati
         Microsoft Research

TITLE: Sequential Importance Sampling and Message-Passing Algorithms:
       A new class of efficient algorithms for large-scale networks


ABSTRACT:
Large-scale complex networks have been the objects of study for the past
two decades,  and two problems have been the main focus: constructing or
designing realistic models for large-scale networks and making statistical
inferences in such networks.  These problems appear in a variety of
research areas including coding theory, combinatorial optimization, and
biological systems.  In this presentation, I will explain the use of the
techniques Sequential Importance Sampling (SIS) and Belief Propagation (BP)
for designing and making inferences in large-scale networks.

I will start with an algorithm for designing random graphs that is an
important tool in simulating protocols on Internet topology and detecting
motifs in genetic networks. Unfortunately, the existing algorithms for this
problem have large running times, making them impractical to use for networks
with thousands of vertices.  Our approach is based on SIS that has been
recently introduced as a successful heuristic for counting graphs.  We
analyze validity of SIS and obtain the fastest algorithm for generating
random graphs with given degree sequences.

The second portion of my talk will be about a mysterious message-passing
algorithm called Belief Propagation (BP).  Despite spectacular success of
the BP in inference on large-scale networks, theoretical results concerning
the correctness and convergence of the method are known only in few cases.
We will prove correctness and convergence of the BP for finding maximum
weight matching. This also yields a simple and distributed algorithm and
offers the possibility of implementation in hardware for scheduling in high
speed routers.