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.