Date  Speaker  Speaking 


 
jan 20 MiRC 102 12pm 
Amihood Amir, BarIlan 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 1pm 
Elitza Maneva, UC Berkeley 
Probabilistic Inference Heuristics for Satisfiability
The known NPhardness 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 NPhard 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 1pm 
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 JerrumSinclairVigoda 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 1pm 
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 1pm 
Dana 
Slow mixing of Glauber dynamics for independent sets via topological obstructions 
sep 30 darts lab 1pm 
Parikshit 
Algorithms for Polynomial Interpolation over Composites 
sep 23 darts lab 1pm 
Subhash 
Nonembeddability Theorems via Fourier analysis 