[Colloquium] Narayanan/Dissertation Defense/May 29, 2009

[Margaret Jaffey]

       Department of Computer Science/The University of Chicago

                     *** Dissertation Defense ***


Candidate:  Hariharan Narayanan

Date:  Friday, May 29, 2009

Time:  2:45 PM

Place:  Ryerson 277

Title: Applications of Diffusion in Computer Science and Statistics

Abstract:
In this thesis, we investigate diffusion as an algorithmic and
analytic tool in statistics and computer science.

We address a question arising from computational linguistics, where we
wish to understand the behavior of a network of agents modeled as
nodes of a graph that adaptively modify their lexicon using data from
their neighbors. By introducing a model of memory and a family of
coalescing random walks, we prove that they eventually reach a
consensus with probability 1.

We devise a distributed algorithm using a diffusion process having two
time scales.

Addressing the question of routing in a network, we use steady-state
diffusions corresponding to electrical flow in a network of resistors
for oblivious routing and prove that this scheme performs well under a
variety of performance measures.

Based on a microscopic view of diffusion as an ensemble of particles
executing independent Brownian motions, we develop the fastest
currently known algorithm for computing the area of the boundary of a
convex set. A similar technique is used to produce samplers for the
boundaries of convex sets and smooth hypersurfaces that are the
boundaries of open sets in Euclidean space, assuming access to
samplers for the interior. These algorithms are motivated by
Goodness-of-Fit tests in statistics.

The half plane capacity, a quantity used to parameterize conformally
invariant stochastic processes known as Schramm-Loewner evolutions, is
shown to be comparable to a more geometric notion defined in terms of
the areas of neighborhoods. Schramm-Loewner evolutions are important
in statistical physics.

We analyze a class of a natural random walks on a Riemannian manifold,
and give bounds on the Mixing times in terms of the Cheeger constant
and a notion of smoothness that relates the random walk to the metric.

A Markov chain having a stationary distribution that is uniform on the
interior of a polytope is developed. This is the first chain whose
mixing time is strongly polynomial when initiated in the vicinity of
the center of mass. This Markov chain can be interpreted as a random
walk on a certain manifold. The resulting algorithm for sampling
polytopes outperforms known algorithms when the number of constraints
is of the same order of magnitude as the dimension. We use a variant
of this Markov chain to design a randomized version of Dikin's affine
scaling algorithm for linear programming. We provide polynomial-time
guarantees which do not exist for Dikin's algorithm.

Addressing a question from machine learning, under certain smoothness
conditions, we prove that a form of weighted surface area is the limit
of the weight of graph cuts in a family of random graphs arising in
the context of clustering. This is done by relating both to the amount
of diffusion across the surface in question.

Addressing a related issue on manifolds, we obtain an upper bound on
the annealed entropy of the collection of open subsets of a manifold
whose boundaries are well conditioned with respect to a bounded
density. This result leads to an upper bound on the number of random
samples needed before it is possible to accurately classify data lying
on a manifold.

Candidate's Advisor: Prof. Partha Niyogi

Login to the Computer Science Department website for details,
including a draft copy of the dissertation:

 https://www.cs.uchicago.edu/phd/phd_announcements#hari

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