Title: fMRI Brain Image Retrieval Based on ICA Components

We proposes a content-based retrieval system for fMRI brain images, to find a similarity metric that supports queries for retrieval of ``similar tasks'' in a large collection of brain experiments. The system uses a novel similarity measure between the results of Probabilistic Independent Component Analysis (PICA) of the brain images. Specifically, the time series of an fMRI dataset will be represented using a number of ICA components that are associated with low frequency time courses, as high level task-related features. The most effective similarity between two datasets is the value of the Maximum Weight Bipartite matching (MWB) defined on the component-wise similarities. The component-wise similarities are calculated based on the size of the overlap between the ``highly activated'' regions in the corresponding activation maps. We have evaluated the performance of the proposed method on a moderate size fMRI database with considerable variety. The low-frequency component selection, in combination with the bipartite matching similarity measure, outperforms several other component selection methods and similarity measures.

Title: Round and Approx: A new general technique for multidimensional packing problems

I will describe a new general framework for set covering problems, based on the combination of randomized rounding of the Linear Programming relaxation, leading to a partial integral solution, and the application of a certain well-behaved approximation algorithm to complete this solution. Applying this framework, I will describe a 1.525 approximation the 2-dimensional bin packing problem, and a \ln d +1 approxmation for the d-dimensional vector packing problem, improving upon the previous guarantees of 1.69 and O(\ln d) respectively.

Joint work with Alberto Caprara and Maxim Sviridenko.

Title: Design is as Easy as Optimization

Over the last four decades, theoreticians have identified and studied several fundamental genres of algorithmic problems. These include decision, search, optimization, counting, enumeration, random generation, and approximate counting problems.

We identify a new genre of algorithmic problems -- design problems. Every optimization problem leads to a natural design problem. For instance, the minimum spanning tree problem leads to: given an undirected graph $G = (V,E)$ and a bound $B$, find a way of distributing weight $B$ on the edges of $G$ so that the weight of the minimum spanning tree is maximized.

Practitioners have always been faced with design problems and such problems have been studied individually by theoreticians as well. However, this genre has not been subjected to a systematic complexity-theoretic study before. Using techniques of Freund-Schapire and its follow-up works in learning theory, we show that for a large class of problems, the design version is as easy as the optimization version in the following sense: given an oracle (exact or approximation) for the optimization version, the design version can be solved (exactly or with the same approximation factor) in polynomial time.

Joint work with Deeparnab Chakrabarty and Vijay V. Vazirani.

Paper available at: http://www-static.cc.gatech.edu/~aranyak/design-fullversion.pdf

Title: Building a data base for the global dynamics of multi-parameter systems

It is well accepted that nonlinear dynamical systems can exhibit a wide variety of complex dynamics that may be sensitive to changes in parameters. It is also quite common in applications that not all values of the parameters have been determined. We outline a proposed method for building a data base that can be queried to determine parameter values at which particular types of dynamical structures can be found or values at which specific types of bifurcations occur. The fundamental idea is to use topological methods that are computationally efficient to store essential features of the dynamics in terms of a directed graph with equivalence classes of homology maps at the nodes. The directed graph represents information about the existence of a global Lyapunov function and the homology maps at the nodes encode information about the recurrent dynamics.

We explain these ideas in the context of a density dependent Leslie model arising from population biology.

This is based on ongoing work with W. Kalies and P. Pilarczyk.

Title: Linguistic side effects

How does the meaning of an utterance determine its effects on the discourse and its participants? I study this question using tools from programming-language theory. In particular, how do utterances interact with each other in context?

For example, pronouns in natural languages and variable references in programming languages both retrieve values from the context. In general, "computational side effects" in programming languages and "apparently noncompositional phenomena" in natural languages both let expressions access their contexts. This link stresses the dynamic, "operational" view on meaning.

Title: The Erdoes 1932 Conjecture on Squares in a Square & Trains of Thought It Has Inspired

Dedicated to Paul Erdoes on the 10th Anniversary of His Passing on

In 1932 Paul Erdoes looked at the maximal sum f(n) of side lengths of n squares packed in a unit square. He conjectured ($50) that f(k2+1) =f(k2). While the conjecture, surprisingly, is still alive, it has inspired a good number of problems and results about packing and covering of squares, triangles, and more generally convex figures. We will look at some of them on November 10, 2006 @ Princeton.