Skip to main content

25th British Colloquium for Theoretical Computer Science

Programme

BCTCS 2009
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 Z2 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