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.

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.