SASW01
26 March 2012 to 30 March 2012
Computational complexity theory has its origin in logic. The fundamental goal of this area is to understand the limits of efficient computation (that is understanding the class of problems which can be solved quickly and with restricted resources) and the sources of intractability (that is what takes some problems inherently beyond the reach of such efficient solutions). The most famous open problem in the area is the P = NP-problem, listed among the seven Clay Millenium Prize problems. Logic provides a multifarious toolbox of techniques to analyse questions like this, some of which promise to provide deep insights in the nature and limits of efficient computation.
In our workshop, we shall focus on logical descriptions of complexity, i.e. descriptive complexity, propositional proof complexity and bounded arithmetic. Despite considerable progress by research communities in each of these areas, the main open problems remain. In finite model theory the major open problem is whether there is a logic capturing on all structures the complexity class P of polynomial time decidable languages. In bounded arithmetic the major open problem is to prove strong independence results that would separate its levels. In propositional proof complexity the major open problem is to prove strong lower bounds for expressive propositional proof systems.
The workshop will bring together leading researchers covering all research areas within the scope of the workshop. We will especially focus on work that draws on methods from the different areas which appeal to the whole community.
Monday 26th March 2012 | |||
---|---|---|---|
09:00 to 09:25 | No Room Required | ||
09:25 to 09:30 | Room 1 | ||
09:30 to 10:30 |
Complexity of computations and proofs and pseudo-finite structures |
Room 1 | |
10:30 to 11:00 | No Room Required | ||
11:00 to 11:30 |
Nicola Galesi University of Rome La Sapienza |
Room 1 | |
11:30 to 12:30 |
Stephan Kreutzer Technische Universität Berlin |
Room 1 | |
12:30 to 13:30 | No Room Required | ||
14:00 to 15:00 |
Stefan Dantchev Durham University; Aarhus Universitet |
Room 1 | |
15:00 to 15:30 | Room 1 | |
|
15:30 to 16:00 | No Room Required | ||
16:00 to 16:30 |
Fan Yang University of Helsinki |
Room 1 | |
16:30 to 17:30 |
Juha Kontinen University of Helsinki |
Room 1 | |
17:30 to 18:00 | No Room Required |
Tuesday 27th March 2012 | |||
---|---|---|---|
09:00 to 10:00 |
Albert Atserias Universitat Politècnica de Catalunya |
Room 1 | |
10:00 to 10:30 |
Joel David Hamkins City University of New York |
Room 1 | |
10:30 to 11:00 | No Room Required | ||
11:00 to 11:30 |
Robin Adams Birkbeck, University of London |
Room 1 | |
11:30 to 12:30 |
Stephan Kreutzer Technische Universität Berlin |
Room 1 | |
12:30 to 13:30 | No Room Required | ||
14:00 to 15:00 |
Arnaud Durand Université Denis Diderot |
Room 1 | |
15:00 to 15:30 |
Eryk Kopczynski Uniwersytet Warszawski |
Room 1 | |
15:30 to 16:00 | No Room Required | ||
16:00 to 16:30 |
Oliver Kullmann Swansea University |
Room 1 | |
16:30 to 17:00 |
Moshe Vardi Rice University |
Room 1 | |
17:00 to 17:30 | No Room Required | ||
17:30 to 18:30 |
Andrew Hodges University of Oxford |
Room 1 | |
18:30 to 19:00 | No Room Required |
Wednesday 28th March 2012 | |||
---|---|---|---|
09:00 to 10:00 |
Rahul Santhanam University of Oxford |
Room 1 | |
10:00 to 10:30 |
Jan Johannsen Ludwig-Maximilians-Universität München |
Room 1 | |
10:30 to 11:00 | No Room Required | ||
11:00 to 11:30 |
Naohi Eguchi Tohoku University |
Room 1 | |
11:30 to 12:30 |
Sam Buss University of California, San Diego |
Room 1 | |
12:30 to 13:30 | No Room Required | ||
14:00 to 19:30 | No Room Required | ||
19:30 to 22:00 | No Room Required |
Thursday 29th March 2012 | |||
---|---|---|---|
09:00 to 10:00 |
Liqun Chen Hewlett-Packard Laboratories |
Room 1 | |
10:00 to 10:30 |
Massimo Lauria Universitat Politècnica de Catalunya |
Room 1 | |
10:30 to 11:00 | No Room Required | ||
11:00 to 11:30 |
Leszek Kolodziejczyk Uniwersytet Warszawski |
Room 1 | |
11:30 to 12:30 |
Sam Buss University of California, San Diego |
Room 1 | |
12:30 to 13:30 | No Room Required | ||
14:00 to 15:00 |
Bjarki Holm University of Cambridge |
Room 1 | |
15:00 to 15:30 |
Wied Pakusa RWTH Aachen University |
Room 1 | |
15:30 to 16:00 | No Room Required | ||
16:00 to 16:30 |
Ján Pich Charles University, Prague |
Room 1 | |
16:30 to 17:30 |
Phuong Nguyen Université de Montréal |
Room 1 | |
Friday 30th March 2012 | |||
---|---|---|---|
09:00 to 10:00 |
Neil Thapen Charles University, Prague |
Room 1 | |
10:00 to 10:30 |
Emil Jeřábek Academy of Sciences of the Czech Republic |
Room 1 | |
10:30 to 11:00 | No Room Required | ||
11:00 to 11:30 |
Steven Lindell Haverford College |
Room 1 | |
11:30 to 12:30 |
Nicole Schweikardt Goethe-Universität Frankfurt |
Room 1 | |
12:30 to 13:30 | No Room Required |
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.