Skip to content

Workshop Programme

for period 26-30 March

Logical Approaches to Barriers in Complexity II

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
Seminars in the University
National and International Scientific Research Meetings

Back to top ∧