skip to content

New Directions in Proof Complexity


we have been made aware of a very convincing phone scam that is focusing on our workshop participants. Participants may be contacted by phone by a firm called Business Travel Management to arrange accommodation for workshops and/or programmes.  This includes a request to enter credit card information.

Please note, INI will never contact you over the phone requesting card details. We take all payments via the University of Cambridge Online store

If you have been contacted by this company please contact us as soon as possible.

10th April 2006 to 13th April 2006

Organisers: Professor SR Buss (California) and Professor J Krajicek (Prague).

Conference Theme

Proof complexity is an area of mathematics (and mathematical logic and computational complexity theory in particular) centered around the problem whether the complexity class NP is closed under complementation. With a suitable general definition of a propositional proof system (Cook and Reckhow 1979) this becomes a lengths-of-proofs question: Is there a propositional proof system in which every tautology admits a proof whose length is bounded above by a polynomial in the length of the tautology? The ultimate goal of proof complexity is to show that there is no such proof system; that is, to demonstrate superpolynomial lower bounds for all proof systems.

Strong lower bounds are known for some particular, classical proof systems. (In fact, also surprising upper bounds are known!) The methods used for proving these lower bounds borrow from all parts of logic, from finite combinatorics, from parts of complexity theory including circuit complexity, communication complexity, cryptography, derandomization, from classical algebra like field theory or representation theory, or from abstract concepts of geometry like Euler characteristic and Grothendieck ring.

The purpose of the conference is to bring together researchers in various parts of mathematics and computer science interested in proof complexity. Our ambition is to expose, through invited and contributed lectures, current developments in proof complexity as well as new ideas and directions of research pursued most recently.

University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons