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.