## Invited SpeakersAlexandr Andoni, Microsoft Research Mountain View Jörg Flum, Albert-Ludwigs-Universität Freiburg Mai Gehrke, Radboud Universiteit Nijmegen Daniel Kirsten, Humboldt-Universität zu Berlin Prasad Raghavendra, Georgia Tech Paul Wollan, Sapienza University of Rome
## Abstracts## Nearest Neighbor Search in High-Dimensional Spaces by Alexandr AndoniNearest neighbor search in high-dimensional spaces is a ubiquitous problem in searching and analyzing massive data sets. In this problem, the goal is to preprocess a set of objects (such as images), so that later, given a new query object, one can efficiently return the object most similar to the query. This problem is of key importance in several areas, including machine learning, information retrieval, image/video/music clustering, and others. For instance, it forms the basis of a widely used classification method in machine learning: to label a new object, just find a similar but already-labeled object. Nearest neighbor search also serves as a primitive for other computational problems such as closest pair, minimum spanning tree, or variants of clustering. ## Invariantization of listings by Jörg FlumWe consider a halting problem for nondeterministic Turing machines and show via invariantization of listings the relationship of its complexity to - the existence of almost optimal algorithms for the set of propositional tautologies;
- the existence of hard sequences for all algorithms deciding a given problem;
- the existence of logics capturing polynomial time.
## Duality and recognition by Mai GehrkeThe fact that one can associate a finite monoid with universal properties to each language recognised by an automaton is central to the solution of many practical and theoretical problems in automata theory. It is particularly useful, via the advanced theory initiated by Eilenberg and Reiterman, in separating various complexity classes and, in some cases it leads to decidability of such classes. In this talk I will give a general introduction to Stone duality and explain what this has to do with the connection between regular languages and monoids. This is joint work with Serge Grigorieff and Jean-Éric Pin. ## Some Variants of the Star Height ProblemIn the talk, we present a new approach to the decidability and the first upper complexity bound to Eggan's famous star height problem from 1963: is the star height (concerning rational expressions with union, concatenation, and iteration) of a given recognizable language effectively computable? ## Generic techniques to round SDP relaxations by Prasad RaghavendraThis talk will survey two general approaches to rounding solutions to SDP relaxations. ## New Proofs in Graph Minors by Paul WollanThe theory of Graph Minors developed by Robertson and Seymour has had wide reaching consequences in graph theory and theoretical computer science. The main result of the theory, known as the graph minor structure theorem, approximately describes the structure of graphs which do not contain a xed graph as a minor. The structure theorem is the central piece of many of the algorithmic applications of graph minor theory. Unfortunately, the statement of this structure theorem is quite complex and the only proof until now requires a series of 16 technical papers. |