NVTI Theory Day, March 10, 2006
===============================
We are happy to invite you for the Theory Day 2006 of the NVTI
(Nederlandse Vereniging voor Theoretische Informatica).
This event will take place on Friday March 10, 2006, 9:30 - 16:45,
at Hoog Brabant, Utrecht (close to Utrecht Central Station).
The NVTI theory day 2006 is financially or otherwise sponsored by NWO
(Netherlands Organisation for Scientific Research), Elsevier 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).
Lecturers:
==========
Martin Abadi - Reconciling Two Views of Cryptography
Mark de Berg - I/O- and cache-efficient algorithms for spatial data
Mark Kas - The Research Agenda for Computer Science in The Netherlands
Wan Fokkink - Oh Mega Completeness
Kurt Mehlhorn - Reliable Geometric Computation
As in previous years we have a strong program featuring excellent
foreign and Dutch speakers, covering important streams in theoretical
computer science. Two lectures cover algorithms and complexity theory;
the other two cover logic and semantics.
Please find below the program, location, details on lunch registration,
sponsors, and last but not least the abstracts, and a CV of the speakers
Program:
========
9.30-10.00: Arrival with Coffee
10.00-10.10: Opening
10.10-11.00: Prof. Dr. Martin Abadi
(Microsoft Research and U. California at Santa Cruz)
Reconciling Two Views of Cryptography
11.00-11.30: Coffee/Tea
11.30-12.20: Prof. Dr. Mark T. de Berg (TU/e)
I/O- and cache-efficient algorithms for spatial data
12.20-12.40: Dr. Mark Kas (NWO Exacte Wetenschappen/Physical Sciences)
The Research Agenda for Computer Science in The Netherlands
12.40-14.10: Lunch (see below for registration)
14.10-15.00: Prof. Dr. Wan Fokkink (VU and CWI)
Oh Mega Completeness
15.00-15.20: Coffee/Tea
15.20-16.10: Prof. Dr. Kurt Mehlhorn
(Max-Planck-Institute and University of Saarland)
Reliable Geometric Computation
16.10-16.40: Business meeting NVTI
Location
========
From the big hall of Utrecht Central station, follow sign 'Centrum'.
At 'Radboudkwartier' it is only 100 meter. You find 'Hoog Brabant'
behind the info desk from shopping center 'Hoog Catharijne'.
Lunch registration
==================
It is possible to participate in the organized lunch. Registration is
required. Please register by E-mail (Susanne.van.Dam@cwi.nl) or by
phone (020-5924189), no later than one week before the meeting (March 3).
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.
Abstracts:
==========
Reconciling Two Views of Cryptography Martin Abadi
Two distinct, rigorous views of cryptography have developed over the
years, in two mostly separate communities. One of the views relies
on a simple but effective formal approach; the other, on a detailed
computational model that considers issues of complexity and
probability. There is an uncomfortable and interesting gap between
these two approaches to cryptography. In this talk, we discuss this
gap and the current research efforts that aim to bridge it. We focus
on computational justifications for the formal treatment of
encryption, and their recent applications to the study of guessing
attacks and to XML access control.
I/O- and cache-efficient algorithms for spatial data
Mark de Berg
Modern computer systems have a hierarchal memory consisting of a disk,
main memory, and several levels of cache. The difference between the
times to access these different levels of memory is quite large. This is
holds in particular for main memory and disk: accessing the disk is
typically about 100,000 times slower than accessing the main memory.
Hence, it is important to take caching- and I/O-behavior into account
when designing and analyzing algorithms. In this talk I discuss some of
the recent results that have been obtained on I/O- and cache-efficient
algorithms, focusing on algorithms and data structures for spatial data.
Oh Mega Completeness
Wan Fokkink
In his CONCUR'90 paper, Rob van Glabbeek introduced sound and
ground-complete axiomatizations for the basic process algebra BCCSP,
modulo the semantics in his linear time - branching time spectrum.
Also at CONCUR'90, Jan Friso Groote was the first to address the
question whether these axiomatizations are omega-complete.
Since then, positive and negative results have been obtained
regarding the existence of omega-complete axiomatizations for BCCSP
modulo the semantics in the aforementioned spectrum. In this talk I
will give an overview of these results, the methods that were used
to obtain them, and the remaining open questions.
Reliable Geometric Computation Kurt Mehlhorn
Reliable implementation of geometric algorithms is a notoriously
difficult task. Algorithms are usually designed for the Real-RAM,
capable of computing with real numbers in the sense of mathematics,
and for non-degenerate inputs. But, real computers are not Real-RAMs
and inputs are frequently degenerate. We start with a short collection
of failures of geometric programs. We then go on to discuss approaches
to reliable geometric computation:
- realization of an efficient Real-RAM as far as it is
needed for geometry,
- design of algorithms with reduced arithmetic demand,
- controlled perturbation.
Curricula Vitae of the Lecturers
================================
Martin Abadi is Professor of Computer Science at UCSC (since 2001)
and Senior Researcher at Microsoft (since 2006). Earlier, he studied
at Stanford University and worked at Digital's System Research
Center and other industrial labs. His research is on computer and
network security, programming languages, and specification and
verification methods. He has contributed, for example, to the design
and analysis of security protocols, to the foundations of
object-oriented languages, and to temporal-logic verification
techniques. His web page is at www.soe.ucsc.edu/~abadi/home.html.
Mark de Berg received an M.Sc. in computer science from Utrecht
University in 1988, and he received a Ph.D. from the same university
in 1992. Currently he is a full professor at TU Eindhoven. His main
research interest is in computational geometry and its application
to areas like GIS, computer graphics, and CAD/CAM. He is (co-)author
of two books on computational geometry and he has published over 100
papers in journals and conferences.
Wan Fokkink obtained a PhD degree in Computer Science at the
University of Amsterdam in 1994. After a postdoc at Utrecht
University and a lectureship at the University of Wales Swansea, he
became head of the Embedded Systems Group in CWI in 2000. Since 2004
he is full professor at the Free University in Amsterdam, and head
of the Theoretical Computer Science Group. He is still affiliated
to CWI one day a week.
Kurt Mehlhorn is Professor of Computer Science at the University of
Saarland, and Director of the Max-Planck-Institute in
Saarbruecken. His research interests are data structures, graph
algorithms, computational geometry with exact computation, algorithm
engineering, and theoretical complexity. He is the founder of many
software libraries, among which the widely used LEDA software
library.