ACAC Seminar Abstract

ACAC Seminar Abstract

ACAC Seminars

ACAC Seminar Abstract

A Proof Checking View of Parameterized Complexity

Speaker: Luke Mathieson
Date, Time: Fri, 29 Jun 2012 15:00

The PCP Theorem is one of the most stunning results in computational complexity theory, a culmination of a series of results regarding proof checking it exposes some deep structure of computational problems. As a surprising side-effect, it also gives strong non-approximability results. This talk discusses the first steps of extending proof checking complexity results to Parameterized Complexity. In particular we extend the result of Feige et al. to W[1], and discuss some corollaries for other classes.

Back to the top of this page