Theoriedag 2004 van de NVTI
(Nederlandse Vereniging voor Theoretische Informatica)

Vrijdag 5 maart 2004
Vergadercentrum Hoog Brabant, Utrecht



De Theorie-dag 2004 wordt mede mogelijkgemaakt door 
de ondersteuning van NWO/EW, CWI, de Onderzoeksschool
SIKS, de Onderzoekschool IPA, Elsevier Science B.V.




Programma (samenvattingen volgen beneden)
---------

9.30-10.00: Ontvangst met koffie

10.00-10.10: Opening

10.10-11.00: Lezing Prof.dr. U. Schoening (University of Ulm)
             Titel: Algorithms for satisfiability testing

11.00-11.30: Koffie

11.30-12.20: Lezing Dr. P. Gruenwald (CWI)
             Titel: Two theories of information: Shannon & Kolmogorov

12.20-12.50: Lezing Dr. M. Kas (NWO/EW)
             Titel: De omgekeerde wereld. Over de informaticaplannen
                    van het NWO-gebied Exacte Wetenschappen.

12.50-14.10: Lunch (Zie beneden voor registratie)

14.10-15.00: Lezing Prof.dr. S. Abramsky (University of Oxford)
             Titel: nog niet bekend.

15.00-15.20: Thee

15.20-16.10: Lezing Prof.dr. J. van Benthem (UvA, Stanford University)
             Titel: Games, logic and computation

16.10-16.40: Algemene ledenvergadering NVTI

Lunchdeelname
-------------

Het is mogelijk aan een georganiseerde lunch
deel te nemen; hiervoor is aanmelding verplicht.
Dit kan per email of telefonisch bij Susanne van Dam
(susanne@cwi.nl, 020-592 4189), tot een week
voor de bijeenkomst (27 februari).
De kosten kunnen ter plaatse voldaan worden;
deze bedragen ongeveer Euro 14.
Wij wijzen erop dat in de onmiddellijke nabijheid van de vergaderzaal
ook uitstekende lunchfaciliteiten gevonden kunnen worden, voor wie niet
aan de georganiseerde lunch wenst deel te nemen.



Lidmaatschap NVTI
-----------------

Alle leden van de voormalige WTI (Werkgemeenschap Theoretische
Informatica) zijn automatisch lid van de NVTI geworden.
Aan het lidmaatschap zijn geen kosten verbonden; u krijgt de
aankondigingen van de NVTI per email of anderszins toegestuurd.
Was u geen lid van de WTI en wilt u lid van de NVTI worden:
u kunt zich aanmelden bij Susanne van Dam (susanne@cwi.nl),
met vermelding van de relevante gegevens (naam, voorletters,
affiliatie indien van toepassing, correspondentieadres,
email, URL, telefoonnummer).



Samenvattingen van de lezingen
------------------------------

Two Theories of Information: Shannon & Kolmogorov
Spreker: Peter Grunwald, CWI

We introduce, compare and contrast the theories of Shannon information
and Kolmogorov complexity.
We investigate the extent to which these theories have a common purpose
and where they are fundamentally different. We discuss the fundamental
relations 'entropy = expected Kolmogorov complexity' and 'Shannon mutual
information = expected algorithmic information'. We show how 'universal
coding/modeling' (a central idea in practical data compression) may be
viewed as a middle ground between the two theories, and how it leads to
the 'minimum description length principle', a practically useable theory
for statistical inference with arbitarily complex models.  (Joint work
with P.M.B. Vitanyi.)


******************************************************************

Games, logic and computation
Spreker: Johan van Benthem
http://staff.science.uva.nl/~johan/

Games are a natural model for interaction and communication.
Logic and games go well together, witness the widespread
use of 'logic games' for argumentation, semantic evaluation,
or model comparison. But the connection runs more deeply.
Logic provides a natural fine-structure to game theory. In
particular, both strategic and extensive game forms look
like models that logicians are used to in studies of actions,
knowledge, and belief revision. We will show how key issues
in analyzing games link up with recent work in modal logics of
knowledge, communication and action. Our examples are (a)
reasoning about strategic equilibrium, (b) information update
during a game, (c) revision of expectations about the future.

Literature

1999 - ..., "Logic in Games", electronic lecture notes, ILLC
        Amsterdam & philosophy Stanford (occasional paper versions).
2001A, 'An Essay on Sabotage and Obstruction', ILLC Amsterdam.
        To appear in D. Hutter ed., "Festschrift for Joerg Siekmann",
        Springer Verlag.
2001B, 'Dynamic Epistemic Logic', "Bulletin of Economic Research"
        53:4, 219-248 (Proceedings LOFT-4, Torino).
2002A, 'Extensive Games as Process Models', in M. Pauly &
        P. Dekker, eds., special issue of "Journal of Logic,
        Language and Information" 11, 289-313.
2002, 'One is a Lonely Number: on the logic of communication',
        Tech Report PP-2002-27, ILLC Amsterdam. To appear in
        P. Koepke et al. eds., "Colloquium Logicum, Muenster 2001",
        ASL Publications, Providence.
2003, 'Rational Dynamics and Epistemic Logic in Games', in
        S. Vannucci, ed., "Logic, Game Theory and Social Choice III",
        University of Siena, department of political economy, 19-23.
See also the ILLC Preprint server for a bunch of recent papers
        on the interface of logic and game theory.

******************************************************************

Algorithms for Satisfiability Testing
Spreker: Uwe Schoening

Despite its NP-completeness, designing good satisfiability testing
algorithms (SAT solver) has a lot of practical applications.
Such SAT solvers use various heuristics which make them hard
to analyze theoretically. We present a couple of theoretically
well understood algorithms for k-SAT. It was especially realized
during the last years that certain probabilistic algorithms can have
better running times than the best known deterministic ones.