CTIT University of Twente
Research Business & Innovation About CTIT Research Calls Looking for a job? Intranet

Nederlandse Vereniging voor Theoretische Informatica: Theory Day 2009

Nederlandse Vereniging voor Theoretische Informatica


We are happy to invite you for the Theory Day 2009 of the NVTI. The Dutch Asssociation for Theoretical Computer Science (NVTI) supports the study of theoretical computer science and its applications.

NVTI Theory Day 2009

Friday March 20, 2009, 9:30-16:45
Hoog Brabant, Utrecht (close to Central Station)

We have an interesting program with excellent speakers from The Netherlands and abroad, covering important streams in theoretical computer science. Below you will find the abstracts.


Barbara Terhal (IBM Watson, NY)
Frank de Boer (CWI, U Leiden)
E. Allen Emerson (U Texas, Austin)
Paul Vitanyi (CWI, U v Amsterdam)

It is possible to participate in the organized lunch, for which registration is required. Please register by E-mail (J.M.W.Lammerink@ewi.utwente.nl) or by phone (053-4893767), no later than one week before the meeting (March 13, 2009). The costs of 15 Euro can be paid at the location. We just mention that in the direct vicinity of the meeting room there are plenty of nice lunch facilities as well.

The NVTI theory day 2009 is sponsored (financially or in kind) by NOW (Netherlands Organisation for Scientific Research), Elseviers Science, CWI (Dutch Center of Mathematics and Computer Science) and the Dutch research schools IPA (Institute for Programming Research and Algorithmics), OzsL (Dutch Graduate school in Logic) and SIKS (Dutch research school for Information and Knowledge Systems).

Please find the full program and abstracts of the lectures below.


  • 9.30-10.00: Arrival with Coffee
  • 10.00-10.10: Opening
  • 10.10-11.00: Lecture: Barbara Terhal (IBM Watson, NY) Title: Quantum Complexity Theory:  Bringing Rigor to Computational Quantum Physics
  • 11.00-11.30: Coffee/Tea
  • 11.30-12.20: Lecture: Frank de Boer (CWI, U Leiden) Title: Tasks for Actors
  • 12.20-12.40: Dr. Mark Kas (NWO Physical Sciences)  Around the world (of Dutch computer science)  in 8 years and 80 million euros
  • 12.40-14.10: Lunch (see above for registration)
  • 14.10-15.00: Lecture: E. Allen Emerson (U Texas, Austin) Title: Model Checking: Theory, Themes, and Practice
  • 15.00-15.20: Coffee/Tea
  • 15.20-16.10: Lecture:Paul Vitanyi (CWI, U v Amsterdam) Title: Universal Similarity
  • 16.10-16.40: Business meeting NVTI


Speaker: Barbara Terhal (IBM Watson, NY)
Title: Quantum Complexity Theory:
 Bringing Rigor to Computational Quantum Physics


In the past century physicists have developed many heuristic computational techniques for understanding and analyzing quantum physical systems. While these techniques often work very well in practice, a rigorous understanding of the efficiency and limitations of these methods, that is, a quantum complexity theory, has been lacking. We will discuss several results in the emerging field of quantum complexity theory which address the complexity of problems in quantum physics. In particular we will consider problems which are QMA-complete or "quantum NP-complete".
Speaker: Frank de Boer (CWI, U Leiden)


This lecture presents a modular method for a schedulability analysis of real time distributed systems. Distributed systems are naturally described in terms of actors, which constitute an asynchronous model for concurrent objects. An extension of the actor model is presented with real time and behavioral interfaces for specifying the order and timings of the messages an actor may send and receive. Scheduling policies additionally determine the order in which the received messages are processed.

It is shown how to analyze the behavioral interface of an actor to check that every received message is processed within the specified deadline (schedulability analysis). The overall modular analysis of a system of actors is based on a technique for testing the compatibility of the actual use of an actor and its behavioral interface.

Speaker: E. Allen Emerson (U Texas, Austin)
Title: Model Checking: Theory, Themes, and Practice


Model checking is an automatic method of verifying finite state concurrent programs. The use of temporal logic and related frameworks to specify correctness has greatly facilitated simply thinking about the verification problem. Despite early worries about the intractability of state explosion, nowadays it can often be ameliorated, permitting verification of enormously large systems in practice. We will discuss various themes underlying the utility of model checking including expressive specification, efficient reasoning, and simplification.

Speaker: Paul Vitanyi (CWI, U v Amsterdam)
Title: Universal Similarity


We survey a new area of parameter-free similarity distance measures useful in data-mining, pattern recognition, learning and automatic semantics extraction. Given a family of distances on a set of objects, a distance is universal up to a certain precision for that family if it minorizes every distance in the family between every two objects in the set, up to the stated precision (we do not require the universal distance to be an element of the family). We consider similarity distances for two types of objects: literal objects that as such contain all of their meaning, like genomes or books, and names for objects. The latter may have literal embodyments like the first type, but may also be abstract like ``red'' or ``christianity.'' For the first type we consider a family of computable distance measures corresponding to parameters expressing similarity according to particular features between pairs of literal objects. For the second type we consider similarity distances generated by web users corresponding to particular semantic relations between the (names for) the designated objects. For both families we give universal similarity distance measures, incorporating all particular distance measures in the family. In the first case the universal distance is based on compression and in the second case it is based on Google page counts related to search terms. In both cases experiments on a massive scale give evidence of the viability of the approaches.