Programme

Monday, April 6, 2009
15:00–17:00	Registration. Rootes
Session 1	LMS Keynote Speaker in Discrete Maths. Chair: Artur CzumajRoom MS.01
17:00–18:00	Noga Alon Tel Aviv University	Combinatorial Reasoning in Information Theory
18:00–19:00	Reception at The Street
19:00–20:30	Dinner at Rootes

Tuesday, April 7, 2009
Session 2	Plenary Session. Chair: Sara Kalvala Room MS.01
9:00–10:00	Andrew D. Gordon Microsoft Research	Principles and Applications of Refinement Types
Session 3	A Chair: Sara Kalvala Room MS.01		B Chair: Amin Coja-Oghlan Room MS.02
10:00–10:25	Mark New Swansea Unversity	Modular Type Systems	Ambreen Shahnaz University of Leicester	Approximating Node-Weighted Multicast Trees in Wireless Ad-Hoc Networks
10:25–10:50	Neil Sculthorpe University of Nottingham	Dependently Typed Functional Reactive Programming	Andrew Handley University of Leeds	Flipping Regular Graphs and a Peer to Peer Network
10:50–11:20	Coffee break
Session 4	A Chair: Julian Bradfield Room MS.01		B Chair: Martin Dyer Room MS.02
11:20–11:45	Bjarki Holm Cambridge University	The Expressive Power of Rank Logics	Julian Merschen LSE	Solving Simple Stochastic Games with Interior Point Methods
11:45–12:10	Maria Teresa Llano Heriot-Watt University	UML Specification and Correction of Object-Oriented Antipatterns	John Fearnley University of Warwick	LCP Algorithms For Discounted Games
12:10–12:35	George Giorgidze University of Nottingham	Embedding a Functional Hybrid Modelling Language in Haskell	Anne Balthasar LSE	Computation of the Index of a Component of Nash Equilibria
12:35–13:00	Dominic Orchard University of Cambridge	Lucian: Dataflow and Object Orientation	Haris Aziz University of Warwick	Spanning Connectivity Games
13:00–14:15	Lunch at Rootes
Session 5	A Chair: Hajo BroersmaRoom MS.01		B Chair: Faron Moller Room MS.02
14:15–14:40	Vadim Lozin University of Warwick	FPT Algorithms for the Maximum Independent Set and Maximum Clique Problems	Richard P. Brent Australian National Univ.	Three Ways to Test Irreducibility
14:40–15:05	Pim van 't Hof Durham University	Partitioning Graphs into Connected Parts	Arno Pauly University of Cambridge	On the (semi)lattices Induced by Certain Reducibilities
15:05–15:30	Eun Jung Kim Royal Holloway	Algorithm for Finding k-Vertex Out-trees and its Application to k-Internal Out-branching Problem	Aris Pagourtzis Nat. Techn. Univ. Athens	Counting Interval Sizes vs. Counting Nondeterministic Computation Paths
15:30–16:00	Coffee break
Session 6	Plenary Session. Chair: Marcin Jurdzinski Room MS.01
16:00–17:00	Paul W. Goldberg University of Liverpool	Recent Progress in Computing Approximate Nash Equilibria
Session 7	A Chair: Graham Hutton Room MS.01		B Chair: David Manlove Room MS.02
17:00–17:25	Julian Gutierrez University of Edinburgh	Logics and Bisimulation Games for Concurrency, Causality and Conflict	Matthew Gwynne Swansea Unversity	Attacking AES via SAT
17:25–17:50	Andras Salamon Oxford University	How to Avoid Wasting Parallel Performance	James Gate Durham University	Descriptive Complexity of Optimisation Problems
17:50–18:15	Ebrahim A Larijani Swansea Unversity	Consistency Statements in the Fragments of Equational Theory PV	Yuguo He University of Cambridge	Parameterized Complexity Classes under Logical Reductions
19:00–20:00	Dinner at Rootes

Wednesday, April 8, 2009
Session 8	Plenary Session. Chair: Mike Paterson Room MS.01
9:00–10:00	Alistair Sinclair UC Berkeley	Phase Transitions and Mixing Times
Session 9	A Chair: Mike Paterson Room MS.01		B Chair: Rick Thomas Room MS.02
10:00–10:25	Markus Jalsenius University of Liverpool	The Complexity of Weighted Boolean #CSP with Mixed Signs	Stephan Reiff-Marganiec University of Leicester	Flexible Business Processes using StPowla
10:25–10:50	Mark Jerrum Queen Mary	A Complexity Dichotomy for Partition Functions with Mixed Signs	Clive Blackwell Royal Holloway	Recent Theoretical and Practical Developments with Bigraphs
10:50–11:20	Coffee break
Session 10	A Chair: Mark Jerrum Room MS.01		B Chair: Arnold Beckmann Room MS.02
11:20–11:45	Leslie Ann Goldberg University of Liverpool	A Complexity Dichotomy for Hypergraph Partition Functions	Temesghen Kahsai Swansea University	Property Verification of an Electronic Payment System: EP2
11:45–12:10	John Faben Queen Mary	The Complexity of Counting Independent Sets modulo k, with Applications to CSP	Djihed Afifi University of Manchester	Formal Simulation of Supervised Componentry Models and Their Execution
12:10–12:35	Páidí Creed University of Edinburgh	Generating and Counting Euler Tours of Random Graphs	Karim Kanso Swansea University	Automated Generation of Verified Railway Interlocking Systems
12:35–13:00	Velumailum Mohanaraj University of Leeds	A Rational Pavlov Strategy	Phillip James Swansea University	Verifying Train Control Software
13:00–14:15	Lunch at Rootes
Session 11	A Chair: Vadim Lozin Room MS.01		B Chair: Thomas Erlebach Room MS.02
14:15–14:40	Stanislav Zivny Oxford University	The Expressive Power of Binary Submodular Functions	Eric McDermid University of Glasgow	A 3/2-Approximation Algorithm for General Stable Marriage
14:40–15:05	Ian Pratt-Hartmann University of Manchester	Functions Definable by Arithmetic Circuits	Anna Adamaszek University of Warwick	PTAS for the k-Tour Cover Problem on the Euclidean Plane for Moderately Large Values of k
15:05–15:30	Peter Wong Oxford University	Property Specifications for Workflow Modelling	David Manlove University of Glasgow	Keeping Partners Together: Algorithmic Results for the Hospitals/Residents Problem with Couples
15:30–16:00	Coffee break
Session 12	Plenary Session. Chair: Ranko Lazic Room MS.01
16:00–17:00	Jane Hillston University of Edinburgh	Stochastic Process Algebra: Bringing Performance to Life (Tutorial)
Session 13	A Chair: Ranko Lazic Room MS.01		B Chair: Harald Räcke Room MS.02
17:00–17:25	Liam O'Reilly Swansea University	Structured Theorem Proving For CSP-CASL	Paul Bell University of Liverpool	Multiprocessor Speed Scaling for Jobs with Arbitrary Sizes and Deadlines
17:25–17:50	David Hopkins Oxford University	A Higher-Order Observational Equivalence Model Checker	Paul Sant Univ. of Bedfordshire	An Algorithmic and Graph Theoretic Viewpoint of Security
17:50–18:30	Annual General MeetingRoom MS.01
19:30–21:30	Conference Dinner at Scarman

Thursday, April 9, 2009
Session 14	Plenary Session. Chair: Steve Matthews Room MS.01
9:00–10:00	Bill Wadge University of Victoria	Infinitesimal Logic
Session 15	A Chair: Leslie Goldberg Room MS.01		B Chair: Tugkan Batu Room MS.02
10:00–10:25	Luke Mathieson Durham University	New Parameterized Complexity Results for Problems on Degenerate Graphs	Amin Coja-Oghlan University of Edinburgh	Algorithms for Random k-SAT
10:25–10:50	David Richerby Unversity of Leeds	An Introduction to the Complexity of Constraint Satisfaction	Oliver Kullmann Swansea University	On Computational Experiments with Arithmetic Progressions
10:50–11:20	Coffee break
Session 16	A Chair: Iain Stewart Room MS.01		B Chair: Russell Martin Room MS.02
11:20–11:45	Thomas Nickson University of Liverpool	A New Approach for Automata Coordination on Z²	Benjamin Sach University of Bristol	Online Approximate Matching with Non-local Distances
11:45–12:10	Rick Thomas University of Leicester	FA-Presentable Structures	Supaporn Chairungsee King's College London	Longest Previous Reverse Factor
12:10–12:35	Christopher Broadbent Oxford University	Safety Does Not Constrain Expressivity for Word-Languages	Alexandru Popa University of Bristol	On Generalised Matching
12:35–14:00	Lunch at The Street

Department of Computer Science

25th British Colloquium for Theoretical Computer Science

Programme