Theory Lunch: Schedule for Fall 2005


jan 20
MiRC 102
Amihood Amir, Bar-Ilan University Asynchronous Pattern Matching - Metrics
Traditional Approximate Pattern Matching (e.g. Hamming distance errors, edit distance errors) assumes that various types of errors may occur to the data, but an implicit assumption is that the order of the data remains unchanged.

Over the years, some applications identified types of "errors" were the data remains correct but its order is compromised. The earliest example is the "swap" error motivated by a common typing error. Other widely known examples such as transpositions, reversals and interchanges are motivated by biology.

We propose that it is time to formally split the concept of "errors in data" and "errors in address" since they present different algorithmic challenges solved by different techniques. The "errors in address" model, which we call asynchronous pattern matching, since the data does not arrive in a synchronous sequential manner, is rich in problems not addresses hitherto.

We will consider some reasonable metrics for asynchronous pattern matching, such as the number of inversions, or the number of generalized swaps, and show some efficient algorithms for these problems. As expected, the techniques needed to solve the problems are not taken from the standard pattern matching "toolkit".

(joint work with Y. Aumann, G. Benson, A. Levy, O. Lipsky, E. Porat, S. Skienna and U. Vishne)

dec 02
ccb 102
Elitza Maneva, UC Berkeley Probabilistic Inference Heuristics for Satisfiability
The known NP-hardness results imply that for most combinatorial optimization problems there are no efficient algorithms that find an optimal, or even a near optimal solution, on every instance. A heuristic for an NP-hard problem is a polynomial time algorithm that produces such solutions on some input instances, but may fail on others. One of the existing methods for evaluating heuristics is to study their performance on inputs coming from a particular distribution. I will talk about heuristics based on probabilistic inference, which have recently been applied to Boolean satisfiability problems, and exhibit unprecedented success over the uniform distribution on formulas with fixed ratio of clauses to variables. I will show how intuition about the structure of the space of solutions of such formulas influences the design of these heuristics.
nov 18
ccb 102
Nayantara Generating bipartite graphs with a prescribed degree sequence by simulated annealing.
We present an algorithm to generate a random labeled bipartite graph with a given degree sequence. Previously the only algorithm known for this problem was via reduction to approximating the permanent, which causes a quadratic increase in the size of the instance. We prove a combinatorial lemma that allows us to bypass this reduction and define a simulated annealing algorithm. The algorithm is inspired by the Jerrum-Sinclair-Vigoda annealing algorithm for the permanent. Our approach can be generalized to generating subgraphs with a prescribed degree sequence of any given bipartite graph, this includes the permanent as a special case.

This is joint work with Ivona Bezakova and Eric Vigoda.

nov 11
ccb 102
Eric/Daniel Mixture Models for Phylogeny
We consider phylogenetic reconstruction when the data is generated from a mixture distribution (i.e., the mutation rate varies). We first show the pitfalls of popular methods -- maximum likelihood and MCMC. We then determine in which evolutionary models, reconstructing the phylogeny, under a mixture distribution, is impossible (due to ambiguity) or possible (via a linear test). This uses ideas from linear programming duality.
oct 7
darts lab
Dana Slow mixing of Glauber dynamics for independent sets via topological obstructions
sep 30
darts lab
Parikshit Algorithms for Polynomial Interpolation over Composites
sep 23
darts lab
Subhash Non-embeddability Theorems via Fourier analysis

maintained by Tejas Iyer (ti at cc dot gatech dot edu)