# Invited plenary talks

## ESA

**Marc van Kreveld** (Utrecht University, the Netherlands)

**Trajectory Data Analysis**

**Abstract:**
Tracking devices have become more and more widespread, which has led to large collections of
movement data. The moving objects can be vehicles, animals, sports players, and people in general,
and the collected data consists of trajectories: sequences of points with a time stamp. In geographic
information science the analysis of these collections has become a highly important topic of research.
Clustering, similarity analysis, prediction, and flock detection are examples of the analysis of trajectories. All of these analyses requires efficient geometric algorithms.

After giving an introduction into trajectory analysis we will discuss several algorithms that operate on trajectories, including trajectory segmentation and grouping analysis.

**Thomas Rothvoß** (University of Washington, Seattle, USA)

**Lower bounds on the size of linear programs**

**Abstract:**
One of most powerful problems that admits polynomial time algorithms is linear
programming. Just in the last few years we have been able to better understand
its power and its limitations. In this talk, we will give a survey on recent
results which show that NP-hard problems like TSP cannot be solved with a
single linear program and even the matching polytope cannot be represented by a
polynomial size LP.

## ALGOSENSORS

**Phillip Gibbons** (Intel Labs Pittsburgh)

**Algorithmic Challenges in M2M**

**Abstract:**
The Internet of Things promises a world of billions to trillions of smart
objects/devices, communicating machine-to-machine (M2M) and providing us
valuable information and services. This talk highlights our recent work
addressing several key algorithmic challenges that arise in this setting.
Specifically, we focus on problems arising in aggregation, similarity search,
and machine learning on M2M’s massively distributed network. After surveying
these results, we present in greater detail upper and lower bounds
demonstrating the cost of fault tolerance in such networks. These bounds show
that across a communication-time trade-off curve, aggregation algorithms that
tolerate crash failures incur an exponential cost in communication relative to
non-fault-tolerant algorithms.

## ATMOS

**Renato Werneck** (Microsoft Research, USA)

**Building a Real-World Routing Engine**

**Abstract:**
Computing driving directions in road networks is a fundamental
problem with numerous applications. Although standard graph-search algorithms
can solve it in almost linear time, this is not fast enough to enable
interactive queries on continental road networks. Modern algorithms
thus work in two stages: an offline preprocessing routine first computes
some auxiliary data, which is then used to answer exact queries
interactively. In a true success story, the past decade has seen the
development of a diverse set of techniques providing various trade-offs
between preprocessing effort, query time, space usage, extensibility, and
simplicity. I will survey these techniques and discuss how they address
the requirements of real-world routing engines, with emphasis on the
the algorithm behind the system currently in use by Microsoft's Bing Maps.

## IPEC

**Hans Bodlaender** (Utrecht University, the Netherlands)

**Lowerbounds for Kernelization**

**Abstract:** Kernelization is the process of transforming the input of a
combinatorial problem to an equivalent input whose size is bounded by a
function of the parameter; the analysis of kernelization tells what we can
achieve with polynomial time preprocessing for combinatorial problems, and is a
recent active field in algorithm research. In this talk, a survey is given of a
number of recent techniques to show (under complexity theoretic assumptions)
lower bounds for the size of kernels. In particular, it is discussed how the
notion of compositionality can show that certain (parameterized) problems do
not have kernels of polynomial size.

## WABI

**Hélène Touzet** (University of Lille, France)

**Some algorithms for RNA analysis**

**Abstract:**
Ribonucleic acid (RNA) is one of the three major macromolecules, along with DNA
and proteins, that are essential for all forms of life. RNAs are now recognized
to play an active role in cells by catalyzing biological reactions and
controlling gene expression, and have attracted a lot of interest in molecular
biology and in computational biology recently.

Like DNA, RNA is made up of a chain of nucleotides. But a main difference is that RNAs are single stranded and fold into a three-dimensional structure. Due to this spatial structure, RNAs are modeled by complex combinatorial models, such as ordered trees or graphs. In this talk, I will present several basic problems raised by the analysis of RNA (alignment, structure inference) and introduce a universal framework to design dynamic programming algorithms that is especially well-suited for RNA analysis.

## WAOA

**Aleksander Mądry** (EPFL, Switzerland)

**From Graphs to Matrices, and Back: Bridging the Combinatorial and the Continuous**

**Abstract:**
Graphs are ubiquitous in all modern sciences. This motivates a need for
algorithmic tools that are capable of analyzing and computing on graphs in an
efficient manner. A need that is even more pressing now that the graphs we are
dealing with tend to be massive, rendering traditional methods no longer
adequate.

In this talk, I will discuss a recent progress on the maximum flow problem and use it as an illustration of a broader emerging theme in graph algorithms that employs optimization methods as an algorithmic bridge between our combinatorial and spectral understanding of graphs.

I will also briefly outline how this line of work brings a new perspective on some of the core continuous optimization primitives — most notably, interior-point methods.

# Invited tutorials

## IPEC

**Stefan Szeider** (Vienna University of Technology, Austria)

**Backdoors, Satisfiability, and Problems Beyond NP**

**Abstract:**
A backdoor is a small set of variables that represents a shortcut through the
search space. In this tutorial we will provide a survey of fixed-parameter
algorithms and parameterized complexity results for problems related to finding
and using backdoors, mainly focusing on the propositional satisfiability
problems (SAT) and its counting version (#SAT). In addition we will discuss
recent results on using backdoors to break through complexity barriers between
higher levels of the Polynomial Hierarchy. We will explain how this approach
can be used to extend the power of fixed-parameter algorithms for problems
beyond NP and sketch new hardness tools for establishing its limits.

## WAOA

**Monaldo Mastrolilli** (IDSIA, Switzerland)

**The Lasserre/Sum-of-Squares Hierarchy: a gentle introduction**

**Abstract:**
The Lasserre/Sum-of-Squares hierarchy is a systematic procedure to strengthen
LP relaxations by constructing a sequence of increasingly tight formulations.
For a wide variety of optimization problems, this approach captures the convex
relaxations used in the best available approximation algorithms.

The goal of this tutorial is to introduce the non-expert to this technique by giving the essential intuition behind the definition and key properties. We discuss some simple examples, applications and limitations.