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