Logic and algorithms

Programme theme

Theoretical Computer Science is broadly divided into disciplines dealing with logic, semantics and formal methods on the one hand, and algorithmics and computational complexity on the other. The programme will focus on active areas of research that cut across this divide, dealing with algorithmic and complexity aspects of logic as well as logical methods in complexity. Among the areas of focus are

Computer-Aided Verification: Specifically dealing with algorithms and structures for verifying properties of computing system and the logical, combinatorial and algebraic methods deployed in their study.

Finite Model Theory: This draws on logic and combinatorial methods to study the expressive power of logical languages in the finite. Along with connections with complexity, the programme will explore applications in database theory, constraint satisfaction, proof complexity and process logics.

Proof Complexity: At the interface of logic and complexity theory, the study of proof complexity, both in terms of lengths of proofs and complexity of inference steps, provides powerful methods for complexity lower bounds.

Constraint Satisfaction: This describes a class of combinatorial search problems that arise in a wide variety of areas of computer science and which have been the focus of sustained research drawing on a rich variety of techniques from algebra, logic and graph theory.

Games: While two-player games are used as a tool in many of the areas mentioned above, an emerging theory combines games with automata and logic into a powerful tool for the analysis of sytems. Fundamental questions concern the algorithmic complexity of determining a winner or constructing a winning strategy, given a game and a winning condition.

Click here to download the programme's final scientific report

Preprints

Title	Year	Programme
On inverting the VMPC one-way function Authors: K Kulesza Download PDF	2005	LAA
Substitutions into propositional tautologies Authors: Jan Krajicek Download PDF	2005	LAA
Logics of imperfect information: why sets of assignments? Authors: Wilfred Hodges Download PDF	2005	LAA
Majority constraints have bounded pathwidth duality Authors: Andrei Krokhin, Victor Dalmau Download PDF	2005	LAA
Fast algorithms for monotonic discounted linear programs with two variables per inequality Authors: Sergei Vorobyov, D Andersson Download PDF	2005	LAA
NP search problems in low fragments of bounded arithmetic Authors: Neil Thapen, Jan Krajicek, Alan Skelley Download PDF	2005	LAA
The complexity of constraint satisfaction games and QCSP Authors: F Boerner, A Bulatov, Hubie Chen, ET Al Download PDF	2005	LAA
Forbidden lifts (NP and CSP for combinatorists) Authors: Jaroslav Nesetril, Gabor Kun Download PDF	2005	LAA
Logics with an existential modality Authors: Natasha Alechina, D Shkatov Download PDF	2005	LAA
Weak bisimulation approximants Authors: W Harwood, Faron Moller, A Setzer Download PDF	2005	LAA
A normal form for first-order logic over doubly-linked data structures Authors: Steven Lindell Download PDF	2005	LAA
Consequences of the Provability of $NP \subseteq P/poly$ Authors: Jan Krajicek, Byron Cook Download PDF	2005	LAA
On the density of Trigraph Homomorphisms Authors: Jaroslav Nesetril, Pavol Hell Download PDF	2005	LAA
Parameterized proof complexity: A complexity gap for parameterized tree-like resolution Authors: Stefan Szeider, S Dantchev, B Martin Download PDF	2005	LAA
Marrying words and trees Authors: R Alur Download PDF	2005	LAA
Locally excluding a minor Authors: Martin Grohe, S Kreutzer, Anuj Dawar Download PDF	2005	LAA
Affine systems of equations and counting infinitary logic Authors: A Bulatov, Anuj Dawar, Albert Atserias Download PDF	2005	LAA
Model theory makes formulas large Authors: Martin Grohe, S Kreutzer, ET Al, Anuj Dawar Download PDF	2005	LAA
Machines, computations and time; when P can be equal NP Authors: K Kulesza Download PDF	2005	LAA
A logical characterization of individual-based models Authors: James Lynch Download PDF	2005	LAA

Workshops

LAAW01

Seminars

Thursday 19th January 2006
11:00 to 12:00	Jerzy Marcinkowski Wroclaw University of Technology On the selectivity of a semantic subsumption index	Room 1

Tuesday 24th January 2006
11:00 to 12:00	Natasha Alechina University of Nottingham Epistemic logics for time and space bounded reasoning	Room 1

Thursday 26th January 2006
11:00 to 12:00	Complexity of constraint problems via polymorphisms	Room 1

Tuesday 31st January 2006
11:00 to 12:00	Matt Valeriote McMaster University Tractable constraint languages arising from some algebras that generate congruence distributive varieties	Room 1

Thursday 2nd February 2006
11:00 to 12:00	Luke Ong University of Oxford Game semantics and its algorithmic applications: Part I	Room 1

Friday 3rd February 2006
11:00 to 12:00	Stephen Cook University of Toronto Automatically proving the termination of C programs	Room 1

Monday 6th February 2006
11:00 to 12:00	Albert Atserias Universitat Politècnica de Catalunya Non-uniform hardness for NP via black-box adversaries	Room 1

Tuesday 7th February 2006
11:00 to 12:00	Luke Ong University of Oxford Game semantics and its algorithmic applications: Part II	Room 1

Thursday 9th February 2006
11:00 to 12:00	Luke Ong University of Oxford Game semantics and its algorithmic applications: Part III	Room 1
16:00 to 17:00	Albert Atserias Universitat Politècnica de Catalunya Part II on hardness for NP Informal Discussion	Discussion Room

Monday 13th February 2006
11:00 to 12:00	Orna Kupferman Hebrew University of Jerusalem Avoiding determinization	Room 1

Tuesday 14th February 2006
11:00 to 12:00	Luke Ong University of Oxford Game semantics and its algorithmic applications: Part IV	Room 1

Wednesday 15th February 2006
11:30 to 12:30	Lauri Hella University of Tampere Complete problems for higher order logics	Room 1

Thursday 16th February 2006
11:00 to 12:00	Luke Ong University of Oxford Game semantics and its algorithmic applications: Part V	Room 1

Friday 17th February 2006
11:00 to 12:00	Klas Markstrom Umeå University A class of SAT-instances which are hard for resolution based SAT-solvers	Room 1

Monday 20th February 2006
11:00 to 12:00	Hubie Chen Universitat Pompeu Fabra The computational complexity of quantified constraint satisfaction	Room 1

Tuesday 21st February 2006
11:00 to 12:00	Luca Cardelli Biological systems as reactive systems	Room 1

Wednesday 22nd February 2006
11:00 to 12:00	Syntactic vs. semantic approximations to logics that capture complexity classes	Room 1

Thursday 23rd February 2006
11:00 to 12:00	Victor Dalmau Universitat Pompeu Fabra Beyond Hypertee Width: Decomposition methods without decompositions	Room 1

Friday 24th February 2006
11:00 to 12:00	Lauri Hella University of Tampere Complete problems for higher order logics	Room 1

Monday 6th March 2006
11:00 to 12:00	Andrei Krokhin University of Durham Constraint satisfaction problems and dualities	Room 1

Tuesday 7th March 2006
11:00 to 12:00	Jan Krajicek Charles University, Prague Basic proof complexity I	Room 1

Wednesday 8th March 2006
11:00 to 12:00	Charles Steinhorn Vassar College On asymptotic classes of finite structures	Room 1

Thursday 9th March 2006
11:00 to 12:00	Jan Krajicek Charles University, Prague Basic proof complexity II	Room 1

Friday 10th March 2006
11:00 to 12:00	Timothy Griffin University of Cambridge Metarouting: An algebraic approach to defining routing protocols	Room 1

Monday 13th March 2006
11:00 to 12:00	Gabor Kun CSP and MMSNP are computationally equivalent	Room 1

Tuesday 14th March 2006
11:00 to 12:00	Jan Krajicek Charles University, Prague Basic proof complexity III	Room 1

Wednesday 15th March 2006
11:00 to 12:00	Pavol Hell Simon Fraser University Graph partitions	Room 1

Thursday 16th March 2006
11:00 to 12:00	Jan Krajicek Charles University, Prague Basic proof complexity IIII	Room 1

Friday 17th March 2006
11:00 to 12:00	Valentin Goranko University of the Witwatersrand Infinite state model checking in modal logic	Room 1
14:15 to 15:15	Moshe Vardi Rice University Logic and Algorithms	Room 1

Monday 27th March 2006
11:00 to 12:00	Stefan Szeider University of Durham Fixed-parameter algorithms for propositional satisfiability and constraint satisfaction	Room 2

Tuesday 28th March 2006
11:00 to 12:00	Jaroslav Nesetril Charles University, Prague Small extensions	Room 2

Thursday 30th March 2006
11:00 to 12:00	Kathi Fisler Worcester Polytechnic Institute Verification and change-impact analysis of access-control policies	Room 2

Monday 3rd April 2006
11:00 to 12:00	Ubiquitous computing: shall we understand it?	Room 2

Tuesday 4th April 2006
11:00 to 12:00	Approximation schemes for first-order definable optimisation problems	Room 2

Thursday 6th April 2006
11:00 to 12:00	Sergei Vorobyov Games as controlled optimization problems	Room 2

Friday 7th April 2006
11:00 to 12:00	Wilfred Hodges Queen Mary University of London The semantics of modularity	Room 2

Tuesday 18th April 2006
11:00 to 12:00	Thomas Brihaye Université de Mons O-minimal hybrid systems, bisimulation and control	Room 1

Thursday 20th April 2006
11:00 to 12:00	Jan Krajicek Charles University, Prague Forcing with random variables and complexity of computations and proofs	Room 1

Friday 21st April 2006
11:00 to 12:00	Jouko Vaananen University of Helsinki Team logic	Room 1

Monday 24th April 2006
11:00 to 12:00	Pavel Pudlak On lower bounds in non-classical logics	Room 1

Tuesday 25th April 2006
11:00 to 12:00	Graph searching games and graph decompositions I	Room 1

Wednesday 26th April 2006
11:00 to 12:00	Complexity gaps for resolution-based proof systems	Room 1

Thursday 27th April 2006
11:00 to 12:00	Graph searching games and graph decompositions II	Room 1

Tuesday 2nd May 2006
11:00 to 12:00	Graph searching games and graph decompositions III	Room 1

Wednesday 3rd May 2006
11:00 to 12:00	Observations on inverting the VMPC one-way function	Room 1

Thursday 4th May 2006
11:00 to 12:00	Graph searching games and graph decompositions IV	Room 1

Friday 5th May 2006
11:00 to 12:00	Confluent Markov chains	Room 1

Monday 15th May 2006
11:00 to 12:00	Eyal Amir University of Illinois Connecting logic and learning	Room 1

Tuesday 16th May 2006
11:00 to 12:00	Felix Klaedtke Don't care words with an application to the automata-based approach for real addition	Room 1

Wednesday 17th May 2006
11:00 to 12:00	Marta Zofia Kwiatkowska University of Birmingham Model checking for probabilistic real-time systems	Room 1

Thursday 18th May 2006
11:00 to 12:00	Nir Piterman EPFL - Ecole Polytechnique Fédérale de Lausanne Solving games without determinization	Room 1

Tuesday 23rd May 2006
11:00 to 12:00	Ahmed Bouajjani Automata-based techniques for the analysis of dynamic concurrent programs	Room 1

Thursday 25th May 2006
11:00 to 12:00	Steven Lindell Haverford College A physical analysis of mechanical computability	Room 1

Tuesday 30th May 2006
11:00 to 12:00	Heribert Vollmer Post's lattice with applications to complexity theory (Part I)	Room 1

Thursday 1st June 2006
11:00 to 12:00	Heribert Vollmer Post's lattice with applications to complexity theory (Part II)	Room 1

Monday 5th June 2006
11:00 to 12:00	Heribert Vollmer Post's lattice with applications to complexity theory (Part III)	Room 1

Tuesday 6th June 2006
11:00 to 12:00	Moshe Vardi Rice University And logic begat computer science: When giants roamed the Earth	Room 1

Thursday 8th June 2006
11:00 to 12:00	David Richerby National and Capodistrian University of Athens Choiceless polynomial time	Room 1

Monday 12th June 2006
11:00 to 12:00	Anuj Dawar University of Cambridge Model theory on well-behaved finite structures	Room 1

Tuesday 13th June 2006
11:00 to 12:00	Kousha Etessami University of Edinburgh Analysis of recursive Markov chains, recursive Markov decision processes and recursive stochastic games (Part I)	Room 1

Wednesday 14th June 2006
11:00 to 12:00	Helmut Veith Environment abstraction for parameterised systems	Room 1

Thursday 15th June 2006
11:00 to 12:00	Kousha Etessami University of Edinburgh Analysis of recursive Markov chains, recursive Markov decision processes and recursive stochastic games (Part II)	Room 1

Tuesday 20th June 2006
11:00 to 12:00	Kousha Etessami University of Edinburgh Analysis of recursive Markov chains, recursive Markov decision processes and recursive stochastic games. Part III.	Room 1

Thursday 22nd June 2006
11:00 to 12:00	Damian Niwinski On the complexity of infinite computations	Room 1

Friday 23rd June 2006
11:00 to 12:00	Marcin Jurdzinski University of Warwick A deterministic subexponential algorithm for solving parity games	Room 1

Monday 26th June 2006
11:00 to 12:00	David Mitchell Simon Fraser University Modelling in logic; solving with SAT	Room 2

Tuesday 27th June 2006
11:00 to 12:00	Richard Trefler University of Waterloo Patterns of compositional reasoning	Room 2

Wednesday 28th June 2006
11:00 to 12:00	Paul Gastin A fresh look at testing for asynchronous communication	Room 2

Thursday 29th June 2006
11:00 to 12:00	James Lynch Models of biological regulatory networks	Room 2

Organisers

Anuj Dawar University of Cambridge
Moshe Vardi Rice University

Speakers

Natasha Alechina University of Nottingham
Eyal Amir University of Illinois
Albert Atserias Universitat Politècnica de Catalunya
Ahmed Bouajjani
Thomas Brihaye Université de Mons
Luca Cardelli
Hubie Chen Universitat Pompeu Fabra
Stephen Cook University of Toronto
Victor Dalmau Universitat Pompeu Fabra
Anuj Dawar University of Cambridge
Kousha Etessami University of Edinburgh
Kathi Fisler Worcester Polytechnic Institute
Paul Gastin
Valentin Goranko University of the Witwatersrand
Timothy Griffin University of Cambridge
Pavol Hell Simon Fraser University
Lauri Hella University of Tampere
Wilfred Hodges Queen Mary University of London
Marcin Jurdzinski University of Warwick
Felix Klaedtke
Jan Krajicek Charles University, Prague
Andrei Krokhin University of Durham
Gabor Kun
Orna Kupferman Hebrew University of Jerusalem
Marta Zofia Kwiatkowska University of Birmingham
Steven Lindell Haverford College
James Lynch
Jerzy Marcinkowski Wroclaw University of Technology
Klas Markstrom Umeå University
David Mitchell Simon Fraser University
Jaroslav Nesetril Charles University, Prague
Damian Niwinski
Luke Ong University of Oxford
Nir Piterman EPFL - Ecole Polytechnique Fédérale de Lausanne
Pavel Pudlak
David Richerby National and Capodistrian University of Athens
Charles Steinhorn Vassar College
Stefan Szeider University of Durham
Richard Trefler University of Waterloo
Jouko Vaananen University of Helsinki
Matt Valeriote McMaster University
Moshe Vardi Rice University
Helmut Veith
Heribert Vollmer
Sergei Vorobyov

Show All

Programme theme

Preprints

On inverting the VMPC one-way function

Substitutions into propositional tautologies

Logics of imperfect information: why sets of assignments?

Majority constraints have bounded pathwidth duality

Fast algorithms for monotonic discounted linear programs with two variables per inequality

NP search problems in low fragments of bounded arithmetic

The complexity of constraint satisfaction games and QCSP

Forbidden lifts (NP and CSP for combinatorists)

Logics with an existential modality

Weak bisimulation approximants

A normal form for first-order logic over doubly-linked data structures

Consequences of the Provability of $NP \subseteq P/poly$

On the density of Trigraph Homomorphisms

Parameterized proof complexity: A complexity gap for parameterized tree-like resolution

Marrying words and trees

Locally excluding a minor

Affine systems of equations and counting infinitary logic

Model theory makes formulas large

Machines, computations and time; when P can be equal NP

A logical characterization of individual-based models

Workshops

Finite and algorithmic model theory

Logic and databases

Mathematics of constraint satisfaction: logic, algebra and graph theory

New directions in proof complexity

Constraints and verification

Games and verification

Logic and algorithms

Seminars

Organisers

Speakers

Supported By

Logic and algorithms

Programme theme

Preprints

On inverting the VMPC one-way function

Substitutions into propositional tautologies

Logics of imperfect information: why sets of assignments?

Majority constraints have bounded pathwidth duality

Fast algorithms for monotonic discounted linear programs with two variables per inequality

NP search problems in low fragments of bounded arithmetic

The complexity of constraint satisfaction games and QCSP

Forbidden lifts (NP and CSP for combinatorists)

Logics with an existential modality

Weak bisimulation approximants

A normal form for first-order logic over doubly-linked data structures

Consequences of the Provability of $NP \subseteq P/poly$

On the density of Trigraph Homomorphisms

Parameterized proof complexity: A complexity gap for parameterized tree-like resolution

Marrying words and trees

Locally excluding a minor

Affine systems of equations and counting infinitary logic

Model theory makes formulas large

Machines, computations and time; when P can be equal NP

A logical characterization of individual-based models

Workshops

Finite and algorithmic model theory

Logic and databases

Mathematics of constraint satisfaction: logic, algebra and graph theory

New directions in proof complexity

Constraints and verification

Games and verification

Logic and algorithms

Seminars

Organisers

Speakers

Supported By

Register for updates