![[Search]](/static/images/search.gif){kind=small}
![[A-Z Index]](/static/images/az.gif){kind=small}
![[Contact]](/static/images/contact.gif){kind=small}
![[University of Cambridge]](/static/images/identifier2.gif){kind=small}
![[Talks.cam]](/static/images/talkslogosmall.gif)
Monday 26 March 2012, 14:00-15:00
Parameterised Proof Complexity
â ī¸ Important: Semantics and Syntax: A Legacy of Alan Turing
- đ¤ Speaker: Dantchev, S (Durham University)
- đ Date & Time: Monday 26 March 2012, 14:00 - 15:00
- đ Venue: Seminar Room 1, Newton Institute
Questions? Contact
Mustapha Amrani
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 W1 as well as with some open problems.
Series This talk is part of the Isaac Newton Institute Seminar Series series.
Included in Lists
- All CMS events
- bld31
- dh539
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 1, Newton Institute
Note: Ex-directory lists are not shown.