Logic List Mailing Archive

Workshop "New Directions in Proof Complexity", Newton Institute, Cambridge (April 2006)

Isaac Newton Institute for Mathematical Sciences, Cambridge, UK

New Directions in Proof Complexity

(10 April to 13 April 2006)

in association with the Newton Institute programme entitled Logic and
Algorithms (16 January to 7 July 2006)

Organisers:  Professor SR Buss (California), Professor J Krajicek (Prague)

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.

Speakers:  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).

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 385GBP, includes accommodation, breakfast and dinner from dinner
on Sunday 9 April 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 35GBP.  Self-supporting participants are very welcome
to apply.

Further Information and Application Forms are available from the WWW at:

http://www.newton.cam.ac.uk/programmes/LAA/laaw04.html

Completed application forms should be sent to Tracey Andrew at the address
below, or via email to: t.andrew@newton.cam.ac.uk

Closing Date for the receipt of applications is 31 December 2005