Course Description

Franz Baader (Technische Dresden), intermediate, 6 hours

Reasoning in Description Logics

Description Logics (DLs) are a successful family of logic-based knowledge representation formalisms, which can be used to represent the conceptual knowledge of an application domain in a structured and formally well-understood way. They are employed in various application domains, such as natural language processing, configuration, and databases, but their most notable success so far is the adoption of the DL-based language OWL as standard ontology language for the semantic web.

This tutorial concentrates on designing and analyzing reasoning procedures for DLs. After a short introduction and a brief overview of the research of the last 20 years, it will on the one hand present approaches for reasoning in expressive DLs, which are the foundation for reasoning in OWL DL. On the other hand, it will consider tractable reasoning in the more light-weight DL EL, which is employed in bio-medical ontologies, and which is the foundation for the OWL 2 profile OWL 2 EL.


Manfred Droste (Leipzig), introductory/advanced, 8 hours

Weighted Automata and Weighted Logic

A weighted automaton is a classical nondeterministic automaton in which each transition carries a weight describing e.g. the resources used for its execution, the length of time needed, or its reliability. We will first describe basic results from the theory of such quantitative automata. In the second part, we develop syntax and semantics of a weighted logic; the semantics counts 'how often' a formula is true. Then we show that the behaviors of weighted automata are precisely the functions definable by sentences of our weighted logic. This extends Büchi's classical result relating (unweighted) finite automata and monadic second order logic to a quantitative setting.


Venkatesan Guruswami (Carnegie Mellon), intermediate, 6 hours

The Complexity of Approximate Constraint Satisfaction

Constraint satisfaction is a versatile paradigm for specifying problems in various areas of computer science. An instance of a constraint satisfaction problem (CSP) consists of a finite set of variables, a domain over which the variables are to be assigned values, and a finite collection of constraints which place local restrictions on the values the variables may take in relation to the others. CSPs capture several fundamental problems like SAT, graph and hypergraph coloring, etc. The optimization problem corresponding to a CSP consists of finding an assignment that satisfies as many constraints of the CSP instance as possible.

For most CSPs, including many for which satisfiability can be decided in polynomial time, the associated optimization problem is NP-hard. To cope with this intractability, the approximate solvability of CSPs by polynomial time algorithms and limits on the performance guarantees ofsuch algorithms have been extensively studied. For many problems we now have good approximation algorithms as well as strong (or even tight) complementary hardness results. This series of lectures is an advanced introduction to this subject. Its aim will be to discuss a few central algorithmic and hardness results concerning approximability of CSPs, and provide a peek into some its exciting research frontiers.

On the algorithmic side, linear and semidefinite programming relaxations have been the most successful tool for designing good approximation algorithms for CSPs. We will discuss how to write canonical LP and SDP relaxations for CSPs, and see some examples of algorithms based on them and the non-trivial approximation ratios they are able to guarantee.

On the hardness side, we will review the PCP theorem and state some strong (sometimes even optimal) non-approximability results obtained by reductions from a CSP called Label Cover. We will discuss the notion of Dictatorship testing and its utility in the context of proving non-approximability results via reductions from a special form of Label Cover called Unique Games. For illustration, we will discuss a tight hardness result for the Boolean CSP consisting of 3-variable linear equations.

We will then touch upon recent progress based on the "Unique Games conjecture" which is able to identify the approximation threshold of every CSP as the integrality gap of a natural semidefinite programming relaxation, using the simplest binary CSP, MaxCut, for illustration. Time permitting, we may draw a parallel with the algebraic dichotomy conjecture in the world of CSP dichotomy, and comment how --- under the Unique Games conjecture --- the approximability of a CSP is precisely governed by the existence of non-trivial approximate polymorphisms.

No formal prerequisites beyond undergraduate algorithms, complexity, and probability is required, but the material will be challenging and fast paced, so mathematical maturity will be of significant help.

References: (some of the material is based on recent research, and no textbook covers all the topics to be discussed. See two references below, though we won't follow either one of them in the lectures. During the lectures at the school, some slides or notes may be made available to the students)

Tao Jiang (California Riverside), intermediate, 6 hours

Average-case Analysis and Lower Bounds by the Incompressibility Method

A string x is said to be incompressible if the shortest algorithmic description of x (which is also called the Kolmogorov complexity of x) has length at least |x|. Strings that are incompressible are patternless since a pattern could be used to reduce the description length. The incompressibility method is an elementary yet powerful proof technique based on the fact that most strings are incompressible. It has been used successfully in many areas including lower bounds for computational models, formal language and automata theory, combinatorics, and average-case analysis of algorithms.

In this short course, we first give a brief exposition of Kolmogorov complexity and the incompressibility method, and then focus on some representative applications of the method in average-case analysis and proving lower bounds. The examples considered here include some well-known sorting algorithms such as Heapsort and Shellsort as well as string matching automata, and the proofs presented are so elementary that they can be easily understood by anyone with basic knowledge of data structures and algorithms.


Helmut Seidl (Technische München), intermediate, 6 hours

Macro Treetransducers for XML Processing

This course gives a gentle introduction to various classes of macro tree transducers. It illustrates how these can be used as a formal model for XML transformations. We show how basic constructions for tree transducers allow to derive practical algorithms for type checking tree transformations. Here, a type is given by a regular set of admissible terms. Type checking then verifies that a given transformation will always produce legal outputs whenever it is applied to legal inputs.

If there is time, then in a second part we will discuss unique normal-forms for particular simple classes of deterministic tree transducers. These normal forms can be considered as generalizations of minimal automata as wellknown for deterministic finite automata on strings or trees to tree transducers. Such normal forms may be considered as the first step of developing algorithms to automatically learn transductions from examples.


Alan Selman (Buffalo), intermediate, 10 hours

Probabilistic Complexity Classes

In this course we study the benefits of adding randomness to computations. We treat randomness as a resource. Probabilistic algorithms allow computations to depend on the outcomes of an ideal random generator (i.e. on unbiased coin tosses). They can be classified by classifying the languages they are defined to accept. Important computational problems that seem to be infeasible by ordinary deterministic computations have efficient solutions using probabilistic algorithms. Such algorithms can be easily implemented, and fast and reliable solutions to otherwise difficult problems are then possible. There is a cost to this added efficiency, however, in that probabilistic algorithms do sometimes make errors.


Jeffrey Shallit (Waterloo), intermediate, 6 hours

Automatic Sequences, Decidability, and Enumeration

A sequence (an){n ≥ 0} is said to be k-automatic if it can be generated by a finite automaton with output mapping f as follows: the automaton accepts as input the base-k expansion of n, in processing the input it ends up in a state p, and f(p) = an. The class of automatic sequences includes such important examples as the Thue-Morse and Rudin-Shapiro sequences.

Many interesting questions about such sequences are mechanically decidable. This includes, for example, whether the sequence contains repetitions of order r ("rth powers"), whether the sequence is recurrent (every factor occurs infinitely often), etc. Furthermore, we can also mechanically enumerate related sequences, such as the number of distinct factors of length n.

In this short course, this material will be covered. No previous experience with automatic sequences will be assumed.