Workshop Programme

for period 26-30 March

26-30 March

Timetable

Monday 26 March
09:00-09:25	Registration	SAS
09:25-09:30	Welcome from John Toland (INI Director) & Annoucements	SAS
09:30-10:30	Krajicek, J (Charles University, Prague)	SAS
	Complexity of computations and proofs and pseudo-finite structures	Sem 1
10:30-11:00	Morning Coffee	SAS
11:00-11:30	Galesi, N (Università degli Studi di Roma La Sapienza)	SAS
	Proof Complexity of Paris-Harrington Tautologies	Sem 1
11:30-12:30	Kreutzer, S (Technische Universität Berlin)	SAS
	Logical Methods in the Complexity Analysis of Graph Algorithms	Sem 1
12:30-13:30	Lunch at Wolfson Court	SAS
14:00-15:00	Dantchev, S (Durham University)	SAS
	Parameterised Proof Complexity	Sem 1
15:00-15:30	Beyerdorff, O (Università degli Studi di Roma La Sapienza)	SAS
	Parameterized Complexity of DPLL Search Procedures	Sem 1
15:30-16:00	Afternoon Tea	SAS
16:00-16:30	Yang, F (University of Helsinki)	SAS
	Model Checking for Modal Intuitionistic Dependence Logic	Sem 1
16:30-17:30	Kontinen, J (University of Helsinki)	SAS
	Complexity results for dependence logic	Sem 1
17:30-18:00	Drinks Reception	SAS

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

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

Thursday 29 March
09:00-10:00	Chen, Y (Shanghai Jiao Tong University)	SAS
	From almost optimal algorithms to logics for complexity classes via listings and a halting problem	Sem 1
10:00-10:30	Lauria, M (Academy of Sciences of the Czech Republic)	SAS
	Space Complexity of Polynomial Calculus (joint work with Yuval Filmus, Jakob Nordstrom, Neil Thapen, Noga Zewi)	Sem 1
10:30-11:00	Mornign Coffee	SAS
11:00-11:30	Kolodziejczyk, L (Uniwersytet Warszawski)	SAS
	Toda's theorem in bounded arithmetic with parity quantifiers and bounded depth proof systems with parity gates	Sem 1
11:30-12:30	Buss, S (University of California, San Diego)	SAS
	NP search problems: Provability and reducibilities	Sem 1
12:30-13:30	Lunch at Wolfson Court	SAS
14:00-15:00	Holm, B (University of Cambridge)	SAS
	Descriptive complexity of linear algebra	Sem 1
15:00-15:30	Pakusa, W (RWTH Aachen University)	SAS
	Definability of linear equation systems over groups and rings	Sem 1
15:30-16:00	Afternoon Tea	SAS
16:00-16:30	Pich, J	SAS
	Proof complexity of circuit lower bounds	Sem 1
16:30-17:30	Nguyen, PT (Université de Montréal)	SAS
	Developing logical theories for several NP search classes	Sem 1

Friday 30 March
09:00-10:00	Thapen, N (Academy of Sciences of the Czech Republic)	SAS
	Fragments of approximate counting	Sem 1
10:00-10:30	Jerábek, E (Academy of Sciences of the Czech Republic)	SAS
	Root finding in TC^0 and open induction	Sem 1
10:30-11:00	Morning Coffee	SAS
11:00-11:30	Lindell, S (Haverford College)	SAS
	Infinitary methods in finite model theory	Sem 1
11:30-12:30	Schweikardt, N (Goethe-Universität Frankfurt)	SAS
	Locality from circuit lower bounds	Sem 1
12:30-13:30	Lunch at Wolfson Court	SAS

Other Seminars