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
Title | Year | Programme |
---|---|---|
On inverting the VMPC one-way functionAuthors: K Kulesza |
2005 | LAA |
Substitutions into propositional tautologiesAuthors: Jan Krajicek |
2005 | LAA |
Logics of imperfect information: why sets of assignments?Authors: Wilfred Hodges |
2005 | LAA |
Majority constraints have bounded pathwidth dualityAuthors: Andrei Krokhin, Victor Dalmau |
2005 | LAA |
Fast algorithms for monotonic discounted linear programs with two variables per inequalityAuthors: Sergei Vorobyov, D Andersson |
2005 | LAA |
NP search problems in low fragments of bounded arithmeticAuthors: Neil Thapen, Jan Krajicek, Alan Skelley |
2005 | LAA |
The complexity of constraint satisfaction games and QCSPAuthors: F Boerner, A Bulatov, Hubie Chen, ET Al |
2005 | LAA |
Forbidden lifts (NP and CSP for combinatorists)Authors: Jaroslav Nesetril, Gabor Kun |
2005 | LAA |
Logics with an existential modalityAuthors: Natasha Alechina, D Shkatov |
2005 | LAA |
Weak bisimulation approximantsAuthors: W Harwood, Faron Moller, A Setzer |
2005 | LAA |
A normal form for first-order logic over doubly-linked data structuresAuthors: Steven Lindell |
2005 | LAA |
Consequences of the Provability of $NP \subseteq P/poly$Authors: Jan Krajicek, Byron Cook |
2005 | LAA |
On the density of Trigraph HomomorphismsAuthors: Jaroslav Nesetril, Pavol Hell |
2005 | LAA |
Parameterized proof complexity: A complexity gap for parameterized tree-like resolutionAuthors: Stefan Szeider, S Dantchev, B Martin |
2005 | LAA |
Marrying words and treesAuthors: R Alur |
2005 | LAA |
Locally excluding a minorAuthors: Martin Grohe, S Kreutzer, Anuj Dawar |
2005 | LAA |
Affine systems of equations and counting infinitary logicAuthors: A Bulatov, Anuj Dawar, Albert Atserias |
2005 | LAA |
Model theory makes formulas largeAuthors: Martin Grohe, S Kreutzer, ET Al, Anuj Dawar |
2005 | LAA |
Machines, computations and time; when P can be equal NPAuthors: K Kulesza |
2005 | LAA |
A logical characterization of individual-based modelsAuthors: James Lynch |
2005 | LAA |
9 January 2006 to 13 January 2006
27 February 2006 to 3 March 2006
20 March 2006 to 24 March 2006
10 April 2006 to 13 April 2006
8 May 2006 to 12 May 2006
3 July 2006 to 7 July 2006
21 July 2008 to 25 July 2008
The Organisers would like to thank the following sponsors for their generous support of the event:
Thursday 19th January 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Jerzy Marcinkowski Wroclaw University of Technology |
Room 1 |
Tuesday 24th January 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Natasha Alechina University of Nottingham |
Room 1 |
Thursday 26th January 2006 | |||
---|---|---|---|
11:00 to 12:00 | Room 1 |
Tuesday 31st January 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Matt Valeriote McMaster University |
Room 1 |
Thursday 2nd February 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Luke Ong University of Oxford |
Room 1 |
Friday 3rd February 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Stephen Cook University of Toronto |
Room 1 |
Monday 6th February 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Albert Atserias Universitat Politècnica de Catalunya |
Room 1 |
Tuesday 7th February 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Luke Ong University of Oxford |
Room 1 |
Thursday 9th February 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Luke Ong University of Oxford |
Room 1 | |
16:00 to 17:00 |
Albert Atserias Universitat Politècnica de Catalunya |
Discussion Room |
Monday 13th February 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Orna Kupferman Hebrew University of Jerusalem |
Room 1 |
Tuesday 14th February 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Luke Ong University of Oxford |
Room 1 |
Wednesday 15th February 2006 | |||
---|---|---|---|
11:30 to 12:30 |
Lauri Hella University of Tampere |
Room 1 |
Thursday 16th February 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Luke Ong University of Oxford |
Room 1 |
Friday 17th February 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Klas Markstrom Umeå University |
Room 1 |
Monday 20th February 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Hubie Chen Universitat Pompeu Fabra |
Room 1 |
Tuesday 21st February 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Luca Cardelli |
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 |
Room 1 |
Friday 24th February 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Lauri Hella University of Tampere |
Room 1 |
Monday 6th March 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Andrei Krokhin University of Durham |
Room 1 |
Tuesday 7th March 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Jan Krajicek Charles University, Prague |
Room 1 |
Wednesday 8th March 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Charles Steinhorn Vassar College |
Room 1 |
Thursday 9th March 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Jan Krajicek Charles University, Prague |
Room 1 |
Friday 10th March 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Timothy Griffin University of Cambridge |
Room 1 |
Monday 13th March 2006 | |||
---|---|---|---|
11:00 to 12:00 | Room 1 |
Tuesday 14th March 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Jan Krajicek Charles University, Prague |
Room 1 |
Wednesday 15th March 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Pavol Hell Simon Fraser University |
Room 1 |
Thursday 16th March 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Jan Krajicek Charles University, Prague |
Room 1 |
Friday 17th March 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Valentin Goranko University of the Witwatersrand |
Room 1 | |
14:15 to 15:15 |
Moshe Vardi Rice University |
Room 1 |
Monday 27th March 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Stefan Szeider University of Durham |
Room 2 |
Tuesday 28th March 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Jaroslav Nesetril Charles University, Prague |
Room 2 |
Thursday 30th March 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Kathi Fisler Worcester Polytechnic Institute |
Room 2 |
Monday 3rd April 2006 | |||
---|---|---|---|
11:00 to 12:00 | 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 |
Room 2 |
Friday 7th April 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Wilfred Hodges Queen Mary University of London |
Room 2 |
Tuesday 18th April 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Thomas Brihaye Université de Mons |
Room 1 |
Thursday 20th April 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Jan Krajicek Charles University, Prague |
Room 1 |
Friday 21st April 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Jouko Vaananen University of Helsinki |
Room 1 |
Monday 24th April 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Pavel Pudlak |
Room 1 |
Tuesday 25th April 2006 | |||
---|---|---|---|
11:00 to 12:00 | Room 1 |
Wednesday 26th April 2006 | |||
---|---|---|---|
11:00 to 12:00 | Room 1 |
Thursday 27th April 2006 | |||
---|---|---|---|
11:00 to 12:00 | Room 1 |
Tuesday 2nd May 2006 | |||
---|---|---|---|
11:00 to 12:00 | Room 1 |
Wednesday 3rd May 2006 | |||
---|---|---|---|
11:00 to 12:00 | Room 1 |
Thursday 4th May 2006 | |||
---|---|---|---|
11:00 to 12:00 | Room 1 |
Friday 5th May 2006 | |||
---|---|---|---|
11:00 to 12:00 | Room 1 |
Monday 15th May 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Eyal Amir University of Illinois |
Room 1 |
Tuesday 16th May 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Felix Klaedtke |
Room 1 |
Wednesday 17th May 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Marta Zofia Kwiatkowska University of Birmingham |
Room 1 |
Thursday 18th May 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Nir Piterman EPFL - Ecole Polytechnique Fédérale de Lausanne |
Room 1 |
Tuesday 23rd May 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Ahmed Bouajjani |
Room 1 |
Thursday 25th May 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Steven Lindell Haverford College |
Room 1 |
Tuesday 30th May 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Heribert Vollmer |
Room 1 |
Thursday 1st June 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Heribert Vollmer |
Room 1 |
Monday 5th June 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Heribert Vollmer |
Room 1 |
Tuesday 6th June 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Moshe Vardi Rice University |
Room 1 |
Thursday 8th June 2006 | |||
---|---|---|---|
11:00 to 12:00 |
David Richerby National and Capodistrian University of Athens |
Room 1 |
Monday 12th June 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Anuj Dawar University of Cambridge |
Room 1 |
Tuesday 13th June 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Kousha Etessami University of Edinburgh |
Room 1 |
Wednesday 14th June 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Helmut Veith |
Room 1 |
Thursday 15th June 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Kousha Etessami University of Edinburgh |
Room 1 |
Tuesday 20th June 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Kousha Etessami University of Edinburgh |
Room 1 |
Thursday 22nd June 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Damian Niwinski |
Room 1 |
Friday 23rd June 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Marcin Jurdzinski University of Warwick |
Room 1 |
Monday 26th June 2006 | |||
---|---|---|---|
11:00 to 12:00 |
David Mitchell Simon Fraser University |
Room 2 |
Tuesday 27th June 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Richard Trefler University of Waterloo |
Room 2 |
Wednesday 28th June 2006 | |||
---|---|---|---|
11:00 to 12:00 |
Paul Gastin |
Room 2 |
Thursday 29th June 2006 | |||
---|---|---|---|
11:00 to 12:00 |
James Lynch |
Room 2 |
Subscribe for the latest updates on events and news
Isaac Newton Institute for Mathematical Sciences, 20 Clarkson Road, Cambridge CB3 0EH United Kingdom
Tel: +44 1223 335999 Email: reception@newton.ac.uk
© 2023 Isaac Newton Institute for Mathematical Sciences. All Rights Reserved. Privacy Policy
INI is a creative collaborative space which is occupied by up to fifty-five mathematical scientists at any one time (and many more when there is a workshop). Some of them may not have met before and others may not realise the relevance of other research to their own work.
INI is especially important as a forum where early-career researchers meet senior colleagues and form networks that last a lifetime.
Here you can learn about all activities past, present and future, watch live seminars and submit your own proposals for research programmes.
Within this section of the website you should find all the information required to arrange and plan your visit to the Institute. If you have any further questions, or are unable to find the information you require, please get in touch with the relevant staff member or our Reception team via our contact pages.
INI and its programme participants produce a range of publications to communicate information about activities and events, publish research outcomes, and document case studies which are written for a non-technical audience. You will find access to them all in this section.
The Isaac Newton Institute aims to maximise the benefit of its scientific programmes to the UK mathematical science community in a variety of ways.
Whether spreading research opportunities through its network of correspondents, offering summer schools to early career researchers, or hosting public-facing lectures through events such as the Cambridge Festival, there is always a great deal of activity to catch up on.
Find out about all of these endeavours in this section of the site.
There are various ways to keep up-to-date with current events and happenings at the Isaac Newton Institute. As detailed via the menu links within this section, our output covers social media streams, news articles, a regular podcast series, an online newsletter, and more detailed documents produced throughout the year.
“A world famous place for research in the mathematical sciences with a reputation for efficient management and a warm welcome for visitors”
The Isaac Newton Institute is a national and international visitor research institute. It runs research programmes on selected themes in mathematics and the mathematical sciences with applications over a wide range of science and technology. It attracts leading mathematical scientists from the UK and overseas to interact in research over an extended period.
INI has a vital national role, building on many strengths that already exist in UK universities, aiming to generate a new vitality through stimulating and nurturing research throughout the country.During each scientific programme new collaborations are made and ideas and expertise are exchanged and catalysed through lectures, seminars and informal interaction, which the INI building has been designed specifically to encourage.
For INI’s knowledge exchange arm, please see the Newton Gateway to Mathematics.
The Institute depends upon donations, as well as research grants, to support the world class research undertaken by participants in its programmes.
Fundraising activities are supported by a Development Board comprising leading figures in academia, industry and commerce.
Visit this section to learn more about how you could play a part in supporting INI’s groundbreaking research.
In this section you can find contact information, staff lists, maps and details of how to find INI’s main building in Cambridge.
Our administrative staff can help you with any queries regarding a prospective or planned visit. If you would like to discuss a proposed a research programme or other event, our senior management team will be happy to help.