An Isaac Newton Institute Workshop

New Directions in Proof Complexity

10 - 13 April 2006

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

Scientific Enquires: Professor J Krajicek (Prague)

Programme | Participants | Presentations on the web | Photograph

Theme of Conference:

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.


Misha Alekhnovich (IAS, Princeton); Steve Cook (U. of Toronto); Stefan Dantchev (U. of Durham); Russell Impagliazzo (U. of California, San Diego); Toni Pitassi (U. of Toronto); Pavel Pudlak (Academy of Sciences, Prague); Nathan Segerlind (U. of Washington); Neil Thapen (U. of Oxford & Academy of Sciences, Prague); Iddo Tzameret (Tel Aviv University).

Location and Cost:

The conference will take place at the Newton Institute and accommodation for participants will be provided in single study bedrooms with shared bathroom at Wolfson Court. The conference package, costing £385, includes accommodation, breakfast and dinner from dinner on Sunday 9 April 2006 to breakfast on Friday 14 April 2006, and lunch and refreshments during the days that lectures take place. Participants who wish to attend but do not require the Conference Package will be charged a registration fee of £35. Self-supporting participants are very welcome to apply.

Application Forms:

Are available here. Invited participants to the semester long programme whose dates coincide with those of the workshop need not apply or pay any registration fee.

Closing Date:

The closing date for the receipt of applications is 31 December 2005

Local Information

Local Information

Logic and Algorithms | Workshops | Newton Institute Home Page