14/12/06 (NEW DATE)
On faces of the Symmetric and Graphical Traveling Salesman Polyhedra
Dirk Oliver Theis (University of Heidelberg)
Abstract: The famous Symmetric Traveling Salesman Problem consists in finding a shortest round trip through a number of cities. To date, the most successful approach to solving it involves a series of minimizations of a linear function over convex polyhedra. The theoretical core of this method is the study of the Symmetric Traveling Salesman Polytope, STSP(n), which is defined as the convex hull of all Hamiltonian cycles in a complete graph on n vertices.
The Graphical Traveling Salesman Polyhedron, GTSP(n), has been proposed as a tool in the investigation of the Symmetric Traveling Salesman Polytope. A close relationship between the two classes of polyhedra has been proved by Naddef & Rinaldi in a the early '90s: STSP(n) is a face of GTSP(n) in such a way that (``essentially'') every facet of the latter contains at most one facet of the former. However, the precise nature of this connection has remained unclear for a long time. (This has even lead to conjecturing that, for each n, the two polyhedra have actually essentially the same sets of facets.)
In this talk, a result is presented which characterizes this relationship. It is shown how, for each face F of STSP(n), the complex of faces of GTSP(n) containing F can be determined solely out of the STSP-information about F, namely the inequalities defining the facets of STSP(n) containing F. Informally speaking, this means that GTSP(n) is just a ``blown up'' version of STSP(n). This is a far-reaching generalization of the results of Naddef & Rinaldi and a mathematically rigorous confirmation of the wide-spread intuition that the facial structures of the two polyhedra are very closely linked. As an example application of this result, we present a theorem about the ridge-graph of GTSP(n).

26/10/06
Acyclic orientations with path constraints
Rosa Maria Videira de Figueiredo (ULB)
Abstract: Many well-known combinatorial optimization problems can be stated over the set of acyclic orientations of an undirected graph. For example, acyclic orientations with certain diameter constraints are closely related to the optimal solutions of the vertex coloring and frequency assignment problems. We introduce a linear programming formulation of acyclic orientations with path constraints, and discuss its use in the solution of the vertex coloring problem and some versions of the frequency assignment problem. A study of the polytope associated with the formulation is presented.

19/10/06
Halfplane Proximity Queries and Incremental Voronoi Diagrams
Stefan Langerman (ULB)
Abstract: We consider preprocessing a set S of n points in the plane that are in convex position into a data structure supporting queries of the following form: given a point q and a directed line l in the plane, report the point of S that is farthest from (or, alternatively, nearest to) the point q subject to being to the left of line l. We present two data structures for this problem. The first data structure uses O(n^(1+eps)) space and preprocessing time, and answers queries in O(2^(1/eps) log n) time. The second data structure uses O(n log3 n) space and polynomial preprocessing time, and answers queries in O(log n) time. These are the first solutions to the problem with O(log n) query time and o(n^2) space. In the process of developing the second data structure, we develop a new representation of nearest-point and farthest-point Voronoi diagrams of points in convex position. This representation supports insertion of new points in counterclockwise order using only O(log n) amortized pointer changes, subject to supporting O(log n)-time point-location queries, even though every such update may make theta(n) combinatorial changes to the Voronoi diagram. This data structure is the first demonstration that deterministically and incrementally constructed Voronoi diagrams can be maintained in o(n) pointer changes per operation.

12/10/06
An optimal randomized algorithm for d-variate zonoid depth
Pat Morin (Carleton U., Canada)
Abstract: Zonoid depth (Dyckerhoff et al. 1996, Mosler 2002) is a means of interpolating between the convex hull and the average of a set of points and that can be used as a set of robust multivariate statistics. In this talk we present a randomized linear-expected-time algorithm to compute the zonoid depth of a point with respect to a fixed-dimensional point set.

CANCELED
12/10/06
On Unfolding Lattice Trees and Polygons
Sheung-Hung Poon (TU Eindhoven)
Abstract: Graph reconfiguration problems have wide applications in contexts including robotics, molecular conformation, animation, wire bending, rigidity and knot theory. The motivation for reconfiguration problems of lattice graphs arises in applications in molecular biology and robotics. For instance, the bonding-lengths in molecules are often similar, as are the segments of robot arms.
We consider the problems of straightening polygonal trees and convexifying polygons by continuous motions such that rigid edges can rotate around vertex joints and no edge crossings are allowed. A tree can be straightened if all its edges can be aligned along a common straight line such that each edge points "away" from a designated leaf node. A polygon can be convexified if it can be reconfigured to a convex polygon. A lattice tree (resp. lattice polygon) is a tree (resp. polygon) containing only edges from a square or cubic lattice. We show that a 2D lattice chain or a 3D lattice tree can be straightened efficiently in O(n) moves and time, where n is the number of tree edges. We also show that a 2D lattice tree can be straightened efficiently in O(n^2) moves and time. Furthermore, we show that a 2D lattice polygon or a 3D lattice polygon with simple shadow can be convexified efficiently in O(n^2) moves and time. Finally we pose several open problems.

07/09/06
Exact Computation of Feedback Vertex Set
Igor Razgon (University College, Cork, Ireland)
Abstract: In this talk I will present a O(1.8899^n) algorithm for solving the Feedback Vertex Set (FVS) problem, a well-known intractable optimization problem. This is the first algorithm solving this problem faster than O(2^n). The talk consists of 3 parts.
In the first part (approx. 10 minutes), I will define the notion of the exact algorithm, describe a very simple algorithm for the Maximum Independent Set (MIS) problem (just to let the audience feel the spirit of design of such algorithms), and provide motivation to do research in this area.
In the second part (approx. 25 minutes) I will present the proposed algorithm for solving FVS. This algorithm computes the complement of FVS, the Maximum Induced Forest (MIF). The algorithm is based on an observation that the MIF problem can be "transformed" to a MIS problem and the latter is easy to solve faster than in O(2^n). I will show the process of design of the algorithm and the most interesting details of the complexity analysis.
In the third part (approx. 5 minutes) I will present concluding remarks related to the ways of improvement of the proposed approach and its connection to the parameterized version of FVS problem.

14/07/06
EXCEPTIONALLY ON FRIDAY 10:30am
Constraint-Database Tools for Software Verification
Peter Revesz (Max Planck Institute for Informatik and University of Nebraska-Lincoln)
Abstract: One approach to software verification is based on finding (an approximation of) the reachability set of transition systems. Such an approximation then can be used for either falsification or verification of given complex error conditions about transitions systems. To make this approach practical, we rely on several deep and interesting connections between constraint databases and transition systems. We show how the reachability sets of transition systems can be computed using existing constraint database systems, such as the MLPQ or other constraint database systems that can compute a precise, overapproximation, or underapproximation of the least fixed point model of recursive (Datalog-based) constraint database queries. After giving some examples of how this works in practice, we explain the essence of the constraint database theory which makes this possible. We explain that often the constraint database query optimization and evaluation techniques are more sophisticated than any of their analogues in the software verification area. For example, the constraint database techniques involve new quantifier elimination methods that are more powerful than that for Presburger arithmetic and "simplification rules" that can be favorably compared with "meta-transitions" and "accelerations" used in transition systems.

29/06/06
Reachability Analysis of Hybrid Systems with PHAVer
Goran Frehse (Verimag Grenoble)
Abstract: Embedded controllers can exhibit complex behavior because instantaneous, event-driven changes may interact with the continuous, time-driven evolution of the physical environment in ways that are difficult to predict. Because of their mixed discrete-continuous nature, such systems are called hybrid. Our verification tool PHAVer computes the set of reachable states for hybrid systems with affine dynamics in a formally, i.e., algorithmically as well as numerically, sound way. It does so by partitioning the state space and computing piecewise constant bounds on the derivatives for each partition. The reachable states can then be efficiently computed with geometric operations on polyhedra. In this talk, we present PHAVer's reachability algorithm and important improvements such as comlexity reduction for polyhedra, directing the search based on a topological sort, and forward/backward-refinement. The approach is illustrated with benchmark examples and a voltage controlled oscillator circuit that was previously beyond the capabilities of verification tools. PHAVer is available here.

15/06/06
Cross-Language Systems
Roel Wuyts (ULB)
Abstract: Cross-language systems are systems where more than one language need to interact. Some examples are for example ProfessorJ or JScheme (Java/Scheme), Soul (Prolog/Smalltalk), LogicAJ (Java AOP/Prolog), Agora (prototype-based OO/Java-C++-Smalltalk), etc. This talk discusses several of these languages, and has a look at how data, behaviour and concepts need to be mapped when making a cross-language system.

01/06/06
Reflections on Reflection in Dynamically Typed Languages
Roel Wuyts (ULB)
Abstract: Research is all about innovation. Innovation is essentially about being the first. Being the first, especially in so-called "hot" research topics, is not only about having the idea the first, but also about being efficient in validating it. The claim I will defend in this talk is the following: when your research lies in programming languages and software engineering, as in my case, using a fully reflective, dynamically typed programming language is much more efficient than using a statically typed language. This talk will reflect on this statement, as well as on scientific validation and applicability of scientific results in the real-world in general. This will be done using real scientific case studies, and by exposing some of the inherent difficulties in statically typed programming languages.

11/05/06
Combinatorics of geometrically distributed random variables
Helmut Prodinger (Stellenbosch University, South Africa)
Abstract: The analysis of a then new data structure called skip lists, introduced by Pugh intrigued this author to have a closer look at words x_1...x_n, where the letters x are natural numbers, and the probability of occurrence given by the geometric distribution. This is a rich source of q-analogs of classical combinatorial quantities, such as secant and tangent numbers, Eulerian numbers, etc. It also leads to urn models that are useful when analysing algorithms such as probabilistic and approximate counting. There are also many interesting asymptotic problems, that can be addressed by such techniques as Mellin transforms, Rice's method, and Louchard's method that usually works when the Gumbel distribution is lurking in the background.
This talk is suitable to computer scientists, probabilists, combinatorialists and everyone else.

27/04/06
Colourful Simplicial Depth
Tamon Stephen (Magdeburg University, Germany, and Simon Fraser University, Canada)
Abstract: Inspired by Barany's colourful Caratheodory theorem, we introduce a colourful generalization of Liu's simplicial depth. We examine the possible colourful depths of a core point in a colourful configuration of points. In particular, we exhibit a configuration with a core point of colourful depth d^2+1, and conjecture that this is minimal. We then prove a quadratic lower bound for this depth, and apply our results to the problem of bounding monochrome simplicial depth.

20/04/06
Decomposition of consecutive-1 matrices and applications
Horst W. Hamacher (Kaiserslautern University, Germany)
Abstract: Any integer matrix A can be decomposed into a non-negative linear combination of (0,1) matrices with the consecutive-1 property (either in rows or in columns). In this talk we will review results on how to do this decomposition with various objectives to be minimized such as
- sum of coefficients
- number of consecutive-1 matrices to be used
Moreover a sequencing problem of the consecutive-1 matrices is considered. As applications we discuss the modulation of radiation in cancer therapy, the design of stops in public transportation systems, and the solution of integer programs via (semi-)simultaneous network flows. The presentation will be based on joint work with Ravi Ahuja, Davaatseren Baatar, Natshia Boland, Alexander Engau, Frank Lenzen, Annegret Liebers, Anita Schobel and Dorothea Wagner.

23/03/06
On real-time logics and faulty Turing machines
James Worrell (Oxford, UK)
Abstract: In this talk we exhibit a two-way reduction between satisfiability problems for real-time temporal logics and language-emptiness questions for channel machines with insertion errors. This connection has led to the first proof that Metric Temporal Logic (MTL) is undecidable over timed words. It also allows us isolate a decidable fragment of MTL, where the decision procedure uses an an algorithm developed for channel machines.

09/03/06
Computationally sound implementations of equational theories against passive adversaries
Steve Kremer (ENS Cachan, France)
Abstract: In this talk, we report on a recent study of the link between formal and cryptographic models for security protocols in the presence of a passive adversary. In contrast to other works, we do not consider a fixed set of primitives but aim at results for an arbitrary equational theory. We define a framework for comparing a cryptographic implementation and its idealization with respect to various security notions. In particular, we concentrate on the computational soundness of static equivalence, a standard tool in cryptographic pi calculi. We present a soundness criterion, which for many theories is not only sufficient but also necessary. Finally, we establish new soundness results for the exclusive OR and a theory of ciphers and lists.
Joint work with Mathieu Baudet and Véronique Cortier

23/02/06
Aggregating Inconsistent Information: Ranking and Clustering
Alantha Newman (Max Planck Institute)
Abstract: A ranking of n web pages is to be chosen from outputs of k search engines. How do we choose one ranking minimizing the "disagreement" with the k rankings?
A clustering of n genes is to be chosen from outputs of k clustering algorithms. How do we choose one clustering minimizing the "disagreement" with the k clusterings?
These information aggregation problems date back to 1785, when the French philosophers Condorcet and Borda considered voting systems in which each voter specifies a full ranking of a set of candidates. Recently, their algorithmic and complexity aspects have been studied.
We obtain improved algorithms for both these problems using a remarkably simple principle. Our techniques also apply to related graph optimization problems such as the minimum feedback arc set problem on tournaments and the correlation clustering problem on complete graphs. Additionally, we show that the problem of finding a minimum feedback arc set on tournaments has no polynomial-time algorithm, assuming NP is not contained in BPP. This almost settles a long-standing conjecture of Bang-Jensen and Thomassen that the problem is NP-hard.
This is joint work with Nir Ailon and Moses Charikar.

16/02/06
On the expressiveness of MTL and TPTL
Nicolas Markey (ENS Cachan, France)
Abstract: TPTL and MTL are two classical timed extensions of LTL. In this paper, we positively answer a 15-year-old conjecture that TPTL is strictly more expressive than MTL. But we show that, surprisingly, the TPTL formula proposed by Alur and Henzinger for witnessing this conjecture can be expressed in MTL. More generally, we show that TPTL formulae using only the F modality can be translated into MTL.