[Colloquium] REMINDER: Ivona Bezakova/Dissertation Defense today

[Margery Ishmael]

	Department of Computer Science/The University of Chicago

			***  Dissertation Defense  ***


Candidate:  Ivona Bezakova

Date:  Friday, May 5, 2006

Time and Location:  2:30 p.m. in Ryerson 251

Title:  Faster Markov Chain Monte Carlo Algorithms for the Permanent
	and Binary Contingency Tables

Abstract:

Random sampling and combinatorial counting are important
building blocks in many practical applications. However, for
some problems exact counting in deterministic polynomial-time
is provably impossible (unless P=NP), in which case the best
hope is to devise suitable approximation algorithms. Markov
chain Monte Carlo (MCMC) methods give efficient
approximation algorithms for several important problems.

This thesis presents the fastest known (approximation)
algorithms for two such problems, the permanent and binary
contingency tables. The permanent counts the number of
(weighted) perfect matchings of a given bipartite graph, and it
has applications in statistical physics, statistics, and several
areas of computer science. Binary contingency tables count the
number of bipartite graphs with prescribed degree sequences,
and they are used in statistical tests in a number of fields
including ecology, education and psychology.

Our MCMC algorithms use the simulated annealing approach,
a popular heuristic in combinatorial optimization. It utilizes
intuition from the physical annealing process, where a substance
is heated and slowly cooled so that it moves from a disordered
configuration into a crystalline (i.e., ordered) state. In
optimization, simulated annealing starts at an easy instance at
high temperature, and slowly "cools" into the desired hard
instance at low temperature. Simulated annealing is widely used,
with much empirical success but little theoretical backing.

This work presents a new cooling schedule for simulated
annealing, with provable guarantees for several counting
problems. We also improve mixing time results over the
breakthrough work of Jerrum, Sinclair and Vigoda. This yields a
polynomial-time simulated annealing algorithm, which for a graph
with n vertices in time O*(n^7) outputs an arbitrarily close
approximation of the permanent. We present a new simulated
annealing algorithm for binary contingency tables, which relies on
an interesting combinatorial lemma. In fact, we obtain a more
general result: we give a polynomial-time algorithm for counting
bipartite graphs with prescribed degree sequence and an
arbitrary set of forbidden edges.

Finally, we discuss the importance sampling method, which is a
popular method for binary contingency tables. For any input
instance, this technique converges asymptotically to the correct
answer and in many cases it appears to converge fast, making it
especially suited for practical purposes. On the contrary, we
present a negative result: we describe a very simple instance for
which, in any subexponential number of steps, the sequential
importance sampling estimate differs from the correct answer by
an exponential factor (with high probability).

Candidate's Advisor: Prof. Eric Vigoda

A draft copy of Ms. Bezakova's dissertation will be available soon in  
Ry 161A.


=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey                             margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 161A)        (773) 702-6011
The University of Chicago                  http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=