Georgia Institute of Technology College of Sciences

Slow Feature Analysis (SFA) is a method for extracting slowly varying features from input signals. In this talk, we generalize SFA to vector-valued functions of multivariables and apply it to the problem of blind source separation, in particular image separation. When the sources are correlated, we apply the following technique called decorrelation filtering: use a linear filter to decorrelate the sources and their derivatives, then apply the separating matrix obtained on the filtered sources to the original sources. We show that if the filtered sources are perfectly separated by this matrix, then so are the original sources.We show how to numerically obtain such a decorrelation filter by solving a nonlinear optimization problem. This technique can also be applied to other linear separation methods, whose output signals are uncorrelated, such as ICA.This is joint work with Laurenz Wiskott (Proceedings of the 13th IEEE International Conference in Computer Vision, ICCV 2011, Barcelona, Spain).

We derive optimal strategies for a pursuit-and-evasion game and show that when pitted against each other, the two strategies construct a small set containing unit-length line segments at all angles. Joint work with Y. Babichenko, Y. Peres, R. Peretz, and P. Sousi.

Classical vertex coloring problems ask for the minimum number of colors needed to color the vertices of a graph, such that adjacent vertices use different colors. Vertex coloring does have quite a few practical applications in communication theory, industry engineering and computer science. Such examples can be found in the book of Hansen and Marcotte. Deciding whether a graph is 3-colorable or not is a well-known NP-complete problem, even for triangle-free graphs. Intutively, large girth may help reduce the chromatic number. However, in 1959, Erdos used the probabilitic method to prove that for any two positive integers g and k, there exist graphs of girth at least g and chromatic number at least k. Thus, restricting girth alone does not help bound the chromatic number. However, if we forbid certain tree structure in addition to girth restriction, then it is possible to bound the chromatic number. Randerath determined several such tree structures, and conjectured that if a graph is fork-free and triangle-free, then it is 3-colorable, where a fork is a star K1,4 with two branches subdivided once. The main result of this thesis is that Randerath's conjecture is true for graphs with odd girth at least 7. We also give an outline of a proof that Randerath's conjecture holds for graphs with maximum degree 4.