Algorithms Workshop

 Details of the new Algorithms Group at Oxford.

 News: Some of the slides are now online.

All talks will be held in St John's College in the New Seminar Room (no. 5 on the map of St John's College at the bottom of the page), except Christos Papadimitriou's Strachey Lecture which will be held in Lecture Theatre A in the Department of Computer Science (see map of Oxford below).

Programme

Monday 15 October

9:30 - 10:00	Opening
10:00 - 10:45	Monika Henzinger: Breaking the O(n m) Barrier for Buechi Games and Maximal End-Component Decomposition	PDF
10:45 - 11:30	Elias Koutsoupias: Approaching Utopia: Strong Truthfulness and Externality-Resistant Mechanisms
11:30 - 12:00	Coffee break
12:00 - 12:45	Leslie Goldberg: The Complexity of Computing the Sign of the Tutte Polynomial	PDF
12:45 - 14:00	Lunch
14:00 - 14:45	Paul Goldberg: Towards Zillions of PSPACE-completeness Results	PDF
14:45 - 15:30	Joan Feigenbaum: DISSENT: Accountable, Anonymous Communication on the Internet	PDF
15:30 - 16:00	Coffee break
16:00 - 16:45	Peter Jeavons: Discrete Optimisation - The Big Picture	PDF
16:45 - 17:30	Richard Lipton: Is the Halting Problem Really Undecidable?

 

Tuesday 16 October

10:00 - 10:45	Raphaël Clifford: Lower Bounds for Streaming Problems	PDF
10:45 - 11:30	Phil Blunsom: A Bayesian Approach to Learning the Structure of Human Languages	PDF
11:30 - 12:00	Coffee break
12:00 - 12:45	Georg Gottlob: Hypergraph Transversals and Monotone Boolean Formula Dualization
12:45 - 14:00	Lunch
14:00 - 14:45	Joël Ouaknine: Decision Problems for Linear Recurrence Sequences	PDF
14:45 - 15:30	Robert Tarjan: Algorithm Design: Theory and Practice	PDF
15:30 - 16:30	Coffee break
16:30 - 17:30	Christos Papadimitriou (Strachey Lecture): Computational Insights and the Theory of Evolution	PPT

Organisation

This Algorithms Workshop is jointly organised by the Oxford University Department of Computer Science and St John's College, Oxford, to mark the launch of the new Algorithms Group at Oxford. We gratefully acknowledge financial support from both institutions as well as St Anne's College, Oxford.

For information, please email Georg Gottlob or Joel Ouaknine at <firstname.lastname@cs.ox.ac.uk>.

Location

Getting to Oxford

Different options to travel to Oxford are described here:

http://www.ox.ac.uk/visitors_friends/maps_and_directions/directions.html

Local information

Travelers to Oxford typically arrive at the train station or Gloucester Green Bus Station. (St John's College is a couple of minutes' walk from Gloucester Green Bus Station, and about 10 minutes' walk from the train station.)

The workshop will take place in the New Seminar Room (no. 5 on the map below) in St John's College, Oxford (click on the image below to obtain a detailed college map).

Note that Christos Papadimitriou's Strachey Lecture which will be held in Lecture Theatre A in the Department of Computer Science (see map of Oxford above).