Logic List Mailing Archive

NVTI Theory Day 2006: Utrecht, March 10

NVTI Theory Day 2006
              (Nederlandse Vereniging voor Theoretische Informatica)
   Friday March 10, 2006. 9:30 - 16:45
   Hoog Brabant, Utrecht                  (close to Central Station)

Lecturers:
   Martin Abadi: Reconciling Two Views of Cryptography
   Kurt Mehlhorn: Reliable Geometric Computation
   Mark de Berg: I/O- and cache-efficient algorithms for spatial data
   Wan Fokkink: Oh Mega Completeness

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

As in previous years we have a strong program featuring
excellent speakers from the Netherlands and abroad, covering
important streams in theoretical computer science.

Below, please find a list of speakers, titles, and abstracts.
A full programme and other details will follow later.

Kind regards,
Jaco van de Pol,
NVTI secretary.

======================================================================
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.


                     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.


         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 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.