20 March 2009
Utrecht, The Netherlands
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.
Lecturers:
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 NWO
(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.
Kind regards,
Jaco van de Pol,
NVTI secretary.
====================================================================
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)
Title: Tasks for Actors
=============================
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.