Georgia Institute of Technology College of Sciences

There has been substantial work on approximation algorithms for clustering data under distance-based objective functions such as k-median, k-means, and min-sum objectives. This work is fueled in part by the hope that approximating these objectives well will indeed yield more accurate solutions. That is, for problems such as clustering proteins by function, or clustering images by subject, there is some unknown correct "target" clustering and the implicit assumption is that clusterings that are approximately optimal in terms of these distance-based measures are also approximately correct in terms of error with respect to the target. In this work we show that if we make this implicit assumption explicit -- that is, if we assume that any c-approximation to the given clustering objective Phi is epsilon-close to the target -- then we can produce clusterings that are O(epsilon)-close to the target, even for values c for which obtaining a c-approximation is NP-hard. In particular, for the k-median, k-means, and min-sum objectives, we show that we can achieve this guarantee for any constant c > 1. Our results show how by explicitly considering the alignment between the objective function used and the true underlying clustering goals, one can bypass computational barriers and perform as if these objectives were computationally substantially easier. This talk is based on joint work with Avrim Blum and Anupam Gupta (SODA 2009), Mark Braverman (COLT 2009), and Heiko Roeglin and Shang-Hua Teng (ALT 2009).

This talk considers the following sequence shufling problem: Given a biological sequence (either DNA or protein) s, generate a random instance among all the permutations of s that exhibit the same frequencies of k-lets (e.g. dinucleotides, doublets of amino acids, triplets, etc.). Since certain biases in the usage of k-lets are fundamental to biological sequences, effective generation of such sequences is essential for the evaluation of the results of many sequence analysis tools. This talk introduces two sequence shuffling algorithms: A simple swapping-based algorithm is shown to generate a near-random instance and appears to work well, although its efficiency is unproven; a generation algorithm based on Euler tours is proven to produce a precisely uniforminstance, and hence solve the sequence shuffling problem, in time not much more than linear in the sequence length.

Given an "infinite symmetric matrix" W we give a simple condition, related to the shift operator being expansive on a certain sequence space, under which W is positive. We apply this result to AAK-type theorems for generalized Hankel operators, providing new insights related to previous work by S. Treil and A. Volberg. We also discuss applications and open problems.

Fermi acceleration is a phenomenon where a classical particle canacquires unlimited energy upon collisions with a heavy moving wall. Inthis talk, I will make a short review for the one-dimensional Fermiaccelerator models and discuss some scaling properties for them. Inparticular, when inelastic collisions of the particle with the boundaryare taken into account, suppression of Fermi acceleration is observed.I will give an example of a two dimensional time-dependent billiardwhere such a suppression also happens.