### Parameterised Proof Complexity

**Dantchev, S ***(Durham University)*

Monday 26 March 2012, 14:00-15:00

Seminar Room 1, Newton Institute

#### Abstract

I will start by introducing the basic notion of a parameterised proof as defined by B. Martin, S. Szeider and myself back in 2007, and will discuss a complexity gap theorem theorem for generic parameterisation of tree-like resolution. I will then move onto results that have been obtained since them by various researchers, including parameterised lower bounds for the pigeon-hole principle in resolution and for the maximum clique in random graphs in tree-like resolution. I will conclude with some new results due to B. Martin and myself on
parameterised proofs for W[1] as well as with some open problems.

#### Presentation

#### Video

**The video for this talk should appear here if JavaScript is enabled.**

If it doesn't, something may have gone wrong with our embedded player.

We'll get it fixed as soon as possible.

## Comments

Start the discussion!