Logical approaches to barriers in complexity II

Workshop theme

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.

Timetable

Monday 26th March 2012
09:00 to 09:25	Registration	No Room Required
09:25 to 09:30	Welcome from John Toland (INI Director) & Annoucements	Room 1
09:30 to 10:30	Complexity of computations and proofs and pseudo-finite structures	Room 1
10:30 to 11:00	Morning Coffee	No Room Required
11:00 to 11:30	Nicola Galesi University of Rome La Sapienza Proof Complexity of Paris-Harrington Tautologies	Room 1
11:30 to 12:30	Stephan Kreutzer Technische Universität Berlin Logical Methods in the Complexity Analysis of Graph Algorithms	Room 1
12:30 to 13:30	Lunch at Wolfson Court	No Room Required
14:00 to 15:00	Stefan Dantchev Durham University; Aarhus Universitet Parameterised Proof Complexity	Room 1
15:00 to 15:30	Parameterized Complexity of DPLL Search Procedures	Room 1
15:30 to 16:00	Afternoon Tea	No Room Required
16:00 to 16:30	Fan Yang University of Helsinki Model Checking for Modal Intuitionistic Dependence Logic	Room 1
16:30 to 17:30	Juha Kontinen University of Helsinki Complexity results for dependence logic	Room 1
17:30 to 18:00	Drinks Reception	No Room Required

Tuesday 27th March 2012
09:00 to 10:00	Albert Atserias Universitat Politècnica de Catalunya Indistinguishability in Counting Logics and the Complexity of Semi-Algebraic Proofs	Room 1
10:00 to 10:30	Joel David Hamkins City University of New York The hierarchy of equivalence relations on the natural numbers under computable reducibility	Room 1
10:30 to 11:00	Morning Coffee	No Room Required
11:00 to 11:30	Robin Adams Birkbeck, University of London Ordinal Strength of Logic-Enriched Type Theories	Room 1
11:30 to 12:30	Stephan Kreutzer Technische Universität Berlin Logical Methods in the Complexity Analysis of Graph Algorithms II	Room 1
12:30 to 13:30	Lunch at Wolfson Court	No Room Required
14:00 to 15:00	Arnaud Durand Université Denis Diderot The complexity of enumeration and counting for acyclic conjunctive queries	Room 1
15:00 to 15:30	Eryk Kopczynski Uniwersytet Warszawski Bounded degree and planar spectra	Room 1
15:30 to 16:00	Afternoon Tea	No Room Required
16:00 to 16:30	Oliver Kullmann Swansea University SAT Solving: Present and Future	Room 1
16:30 to 17:00	Moshe Vardi Rice University Phase Transitions and Computational Complexity	Room 1
17:00 to 17:30	Break	No Room Required
17:30 to 18:30	Andrew Hodges University of Oxford Alan Turing: the creative power of mathematics	Room 1
18:30 to 19:00	Drinks Reception	No Room Required

Wednesday 28th March 2012
09:00 to 10:00	Rahul Santhanam University of Oxford Strong Lower Bounds for Constant-Depth Frege Imply Lower Bounds for Frege	Room 1
10:00 to 10:30	Jan Johannsen Ludwig-Maximilians-Universität München Separations between propositional proof systems related to clause learning	Room 1
10:30 to 11:00	Morning Coffee	No Room Required
11:00 to 11:30	Naohi Eguchi Tohoku University Towards a New Theory of Bounded Arithmetic for PSPACE computations	Room 1
11:30 to 12:30	Sam Buss University of California, San Diego NP search problems: Complexity and reducibilities	Room 1
12:30 to 13:30	Lunch at Wolfson Court	No Room Required
14:00 to 19:30	Free Afternoon	No Room Required
19:30 to 22:00	Conference Dinner at Christ's College	No Room Required

Thursday 29th March 2012
09:00 to 10:00	Liqun Chen Hewlett-Packard Laboratories From almost optimal algorithms to logics for complexity classes via listings and a halting problem	Room 1
10:00 to 10:30	Massimo Lauria Universitat Politècnica de Catalunya Space Complexity of Polynomial Calculus (joint work with Yuval Filmus, Jakob Nordstrom, Neil Thapen, Noga Zewi)	Room 1
10:30 to 11:00	Mornign Coffee	No Room Required
11:00 to 11:30	Leszek Kolodziejczyk Uniwersytet Warszawski Toda's theorem in bounded arithmetic with parity quantifiers and bounded depth proof systems with parity gates	Room 1
11:30 to 12:30	Sam Buss University of California, San Diego NP search problems: Provability and reducibilities	Room 1
12:30 to 13:30	Lunch at Wolfson Court	No Room Required
14:00 to 15:00	Bjarki Holm University of Cambridge Descriptive complexity of linear algebra	Room 1
15:00 to 15:30	Wied Pakusa RWTH Aachen University Definability of linear equation systems over groups and rings	Room 1
15:30 to 16:00	Afternoon Tea	No Room Required
16:00 to 16:30	Ján Pich Charles University, Prague Proof complexity of circuit lower bounds	Room 1
16:30 to 17:30	Phuong Nguyen Université de Montréal Developing logical theories for several NP search classes	Room 1

Friday 30th March 2012
09:00 to 10:00	Neil Thapen Charles University, Prague Fragments of approximate counting	Room 1
10:00 to 10:30	Emil Jeřábek Academy of Sciences of the Czech Republic Root finding in TC^0 and open induction	Room 1
10:30 to 11:00	Morning Coffee	No Room Required
11:00 to 11:30	Steven Lindell Haverford College Infinitary methods in finite model theory	Room 1
11:30 to 12:30	Nicole Schweikardt Goethe-Universität Frankfurt Locality from circuit lower bounds	Room 1
12:30 to 13:30	Lunch at Wolfson Court	No Room Required

Logical approaches to barriers in complexity II

Speakers

Robin Adams Birkbeck, University of London
Albert Atserias Universitat Politècnica de Catalunya
Sam Buss University of California, San Diego
Liqun Chen Hewlett-Packard Laboratories
Stefan Dantchev Durham University; Aarhus Universitet
Arnaud Durand Université Denis Diderot
Naohi Eguchi Tohoku University
Nicola Galesi University of Rome La Sapienza
Joel David Hamkins City University of New York
Andrew Hodges University of Oxford
Bjarki Holm University of Cambridge
Emil Jeřábek Academy of Sciences of the Czech Republic
Jan Johannsen
Leszek Kolodziejczyk Uniwersytet Warszawski
Juha Kontinen University of Helsinki
Eryk Kopczynski Uniwersytet Warszawski
Stephan Kreutzer Technische Universität Berlin
Oliver Kullmann Swansea University
Massimo Lauria Universitat Politècnica de Catalunya
Steven Lindell Haverford College
Phuong Nguyen Université de Montréal
Wied Pakusa RWTH Aachen University
Ján Pich Charles University, Prague
Rahul Santhanam University of Oxford
Nicole Schweikardt Goethe-Universität Frankfurt
Neil Thapen Charles University, Prague
Moshe Vardi Rice University
Fan Yang University of Helsinki

Show All

Logical approaches to barriers in complexity II

Workshop theme

Timetable

Speakers

Supported By

Register for updates