SPEAKER: Prasad Chebolu
TIME: Thursday 4:30-5:30 pm, November 16th, 2006
PLACE: PPB 300
TITLE: Thesis Proposal: Topics in Random Graphs
Thesis Committee: Alan Frieze(chair), Anupam Gupta, R Ravi
Abstract: We study the hamiltonicity property of a new class of random graphs- random lifts in both undirected and directed graphs. In the undirected case, we show that for sufficiently large h>0 random lifts of K_h and K_{h,h} are Hamiltonian. In the case of directed graphs, we obtain a similar result for the complete directed graph.
We also study the average performance of the greedy matching algorithm in sparse random hypergraphs. We are currently working on developing a matching algorithm for sparse random graphs which runs in time O(n) with high probability.
As future work, we would like to obtain conditions under which strong connectivity holds in random lifts of digraphs.
This proposal includes joint work with Kelley Burgin, Colin Cooper, Alan Frieze and Pall Melsted.
Friday, November 17th, 2006, 3:30 pm
Wean Hall 7220
Broadcasting on trees: Beliefs, Evolution and Reconstruction
Elchanan Mossel
UC Berkeley
Broadcasting processes on trees play a fundamental role in various algorithmic inference problems including: The reconstruction of evolutionary trees in biology, the reconstruction of language evolution in linguistics, network tomography and in the analysis of message passing algorithms such as Belief Propagation and Warning Propagation.
In the talk I will survey several theoretical and applied developments in this area obtained using and extending techniques from discrete probability and statistical physics.
SPEAKER: Don Sheehy
TIME: Wednesday 12-1pm, November 15, 2006
PLACE: NSH 1507
TITLE: Flips in Computational Geometry
ABSTRACT:
In this talk, we will be looking at a basic primitive in computational geometry, the flip. Also known as bistellar flips, edge-flips, rotations, and Pachner moves, this local change operation has been discovered and rediscovered in a variety of fields (thus the many names) and has proven useful both as an algorithmic tool as well as a proof technology. For algorithm designers working outside of computational geometry, one can consider the flip move as a higher dimensional analog of the tree rotations used in binary trees. I will survey some of the most important results about flips with an emphasis on developing a general geometric intuition that has led to many advances.
