Title: Research Issues for Data Mining with High-Dimensional Spectra and Image Sensor Signals

Spectra data or image sensor signals are increasingly used in order to assess the quality of products and processes. The structure of in-process functional data (or images) is often both highly correlated and very high-dimensional. This seminar will introduce some important data mining issues with high-dimensional spectra and image sensor signals. Some important issues are dimensionality reduction, wavelength selection, and robust calibration. Some real-life case studies will be presented to illustrate the proposed methodology.

Title: Simultaneous graph embedding

Traditional problems in graph visualization deal with a single graph while simultaneous graph visualization involves multiple related graphs. In the latter case nodes are placed in the same locations in all graphs and the graphs are simultaneously embeddable if crossing-free drawings for each graph can be found. We present polynomial time algorithms for simultaneous embedding of several classes of planar graphs and prove that some classes of graphs cannot be simultaneously embedded. More interesting are the half dozen variations: simultaneous geometric embedding, with and without mapping, colored simultaneous embeddings, near simultaneous embeddings, and matched embeddings. Dozens of related problems of varying difficulty remain open.

Stephen Kobourov's research interests include information visualization, graph drawing and geometric algorithms, emphasizing problems relating to graph visualization. He received a BS in Computer Science and Mathematics from Dartmouth College in 1995 and PhD in Computer Science from Johns Hopkins University in 2000. He worked at the University of Arizona where he received a NSF Career grant and was tenured in 2006. As a Fulbright Scholar he spent a sabbatical year at the University of Botswana. He is an editor of the Journal of Graph Algorithms and Applications and has served on program committees for SODA, ESA, GD and SoftVis, and as program committee chair for the 10th Symposium on Graph Drawing.

Title: Cops and robbers in random graphs

We will study the following game known as cops and robbers. There is a finite, connected, undirected graph $G$, and $m$ cops and one robber. At the start, each cop chooses one vertex, and then the robber makes his choice of a vertex. Then they move alternately (first the cops then the robber). In the cops' turn, each cop may move to an adjacent vertex, or remain where he is, and similarly for the robber. The cops win the game if one of the cops catches the robber, i.e. lands on the same vertex. We denote by $c(G)$ the `cop-number' of $G$, meaning the minimal $m$ such that $m$ cops have a winning strategy in $G$, and by $c(n)$ the maximum of $c(G)$ over all graphs with $n$ vertices. Maamoun and Meyniel determined the cop-number for grids. Aigner and Fromme proved that in the case of planar graphs three cops can catch the robber. Frankl gave lower bounds on $c(G)$ in the case of large girth graphs. Meyniel conjectured that $c(n)=O(\sqrt{n})$. Our main aim is to prove that the conjecture essentially holds for sparse random graphs: in this case the cop-number has order of magnitude $\Omega(n^{1/2+o(1)})$. Joint work with Bela Bollobas and Imre Leader.

Title: New rounding methods for large-domain SDPs

Semidefinite programming (SDP) is a useful technique for obtaining near-optimal solutions for hard optimization problems. So far, SDP-based techniques have been successfully applied to problems involving boolean or comparably small domains, but it is not well understood how to round and analyze SDP solutions for problems with larger domains. In this talk, we present SDP-rounding methods for a large-domain optimization problem closely related to linear equations mod p.

Given a system of linear equations of the form x_j - x_i = c_ij mod p, the standard objective is to maximize the number of (exactly) satisfied equations. We consider a related objective of satisfying a given system of equations as much as possible. In other words, we consider an objective function in which we award partial credit for an almost satisfied equation rather than only for an exactly satisfied equation. In particular, given an assignment for the variables x_i and x_j from the integral domain [0,p), suppose an equation has actual value x_j - x_i = c_ij +- y_ij (mod p), where y_ij is an integer in [0,p/2]. We say that this equation is satisfied to the extent 1-2(y_ij/p), which has a value in the range [0,1]. A value of `1' indicates a completely satisfied equation and a value of `0' indicates a completely unsatisfied equation. Our goal is then to satisfy all equations to the maximum total extent possible. This problem can be viewed as one in which the objective is to find a layout of elements on a circle so as to preserve specified (directed) pairwise distances. We discuss several SDP-based rounding techniques for approximating this problem.

This is based on joint works with Kevin L. Chang and Konstantin Makarychev.

Title: Incentive-compatible routing

We revisit the problem of incentive-compatible interdomain routing, examining the, quite realistic, special case in which the autonomous systems' (ASes') utilities are linear functions of the traffic in the incident links, and the traffic leaving each AS. We show that incentive-compatibility towards maximizing total welfare is achievable efficiently, and, in the uncapacitated case, by an algorithm that can be easily implemented by BGP, the standard protocol for interdomain routing.

This is joint work with Alexander Hall and Christos Papadimitriou

Title:Long code tests and the dichotomy conjecture for CSPs.

The dichotomy conjecture of Feder and Vardi states that every constraint satisfaction problem is either NP complete or polynonial time solvable. Some special cases of the conjecture are settled. Shaeffer has a solution, when the underlying alphabet is binary, which was generalized by Bulatov for trinary alphabets. Hell and Nesetril have proved the conjecture, when the CSP contains a single binary symmetric relation.

We establish a three ways connection between the dichotomy conjecture, the type of long code tests used in the theory of PCPs and between higher order dynamical systems. Using this relation we give a simple proof for the Hell Nesetril theorem binding it to a recent result of Dinur, Friedgut and Regev.

This is joint work with Gabor Kun.