The NVTI theory day 2008 is financially or otherwise sponsored 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). Nederlandse Vereniging voor Theoretische Informatica ==================================================== We are happy to invite you for the Theory Day 2008 of the NVTI. The Dutch Asssociation for Theoretical Computer Science (NVTI) supports the study of theoretical computer science and its applications. NVTI Theory Day 2008 Friday March 14, 2008, 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: Colin Stirling (University of Edinburgh) Marielle Stoelinga (University of Twente) Ronald de Wolf (Centrum voor Wiskunde en Informatica) Christos Papadimitriou (Berkeley) Please find the full program and abstracts of the lectures, and some other info 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: Prof. Colin Stirling (U. Edinburgh) Title: Higher-Order Matching, Games and Automata 11.00-11.30: Coffee/Tea 11.30-12.20: Lecture: Dr. Marielle Stoelinga (U Twente) Title: From Quality to Quantity: Logics, approximation and model checking of quantitative system models 12.20-12.40: Intermezzo: Dr. Mark Kas (NWO Physical Sciences) Title: And now for something (not) completely different. About changes at NWO 12.40-14.10: Lunch (see above for registration) 14.10-15.00: Lecture: Dr. Ronald de Wolf (CWI) Title: Fourier analysis of Boolean functions: Some beautiful examples 15.00-15.20: Coffee/Tea 15.20-16.10: Lecture: Prof. Christos Papadimitriou (Berkeley) Title: Computing Equilibria 16.10-16.20: Henriette Jensenius: Announcement Lorentz Center Leiden 16.20-16.45: Business meeting NVTI ==================================================================== Speaker : Colin Stirling (U. Edinburgh) Title : Higher-Order Matching, Games and Automata Abstract: A notable success in theoretical computer science is methods for verifying finite and infinite state systems such as model checking. An active research goal is to transfer these techniques to finite and infinite state systems with binding. In the talk, we report on some recent work in this direction on higher-order schema and on higher-order matching. ==================================================================== Speaker : Marielle Stoelinga (U Twente) Title : From Quality to Quantity: Logics, approximation and model checking of quantitative system models Abstract: Many system models contain quantitative information, such as time, probability, resource consumption, and continuous dynamics. Boolean analysis of such systems (based on a yes/no answer) is unsatisfying, for example because small perturbations in the system model may lead to opposite truth values. This talk presents a framework for quantitative specification, model checking and refinement. Starting point is the quantitative transition system (QTS) model, where predicates are assigned real numbers in [0,1]. We consider quantitative versions of LTL and CTL, called QLTL and QCTL, assigning to each formula a truth value in [0,1]. We define the linear and branching distances, which are the quantitative analogi of trace equivalence and bisimulation. Finally, we discuss how this framework generalizes to Markov Decision Processes and Stochastic 2-player games. ==================================================================== Speaker : Ronald de Wolf (CWI) Title : Fourier analysis of Boolean functions: Some beautiful examples Abstract: Fourier analysis of real-valued functions on the Boolean hypercube has been an extremely versatile tool in theoretical computer science in the last decades. Applications include the analysis of the behavior of functions with noisy inputs, cryptography, machine learning theory, design of probabilistically checkable proofs, threshold phenomena in random graphs, etc. In this talk we will give a brief introduction to this area, illustrated with a number of simple but elegant applications. ==================================================================== Speaker : Christos Papadimitriou (Berkeley) Title : Computing Equilibria Abstract: In 1951 Nash showed that every game has a mixed equilibrium; his proof is essentially a reduction to Brouwer's fixpoint theorem. Whether such an equilibrium can be found efficiently has been open since that time. This talk surveys some recent results that shed light to this problem, essentially by demonstrating a reduction in the opposite direction. We also discuss the many surrounding problems, such as approximate equilibria, correlated equilibria, and repeated games. ==================================================================== It is possible to participate in the organized lunch, for which 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 7, 2008). 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.