You are in : Home » Results & submissions » Select UOA » 11 - Computer Science and Informatics » View submission: University of Edinburgh » Outputs » Detail

Output details

11 - Computer Science and Informatics

University of Edinburgh

Return to search Previous output Next output

Output 187 of 401 in the submission

Article title

Infeasibility of instance compression and succinct PCPs for NP

Type

D - Journal article

DOI

10.1016/j.jcss.2010.06.007

Title of journal

Journal of Computer and System Sciences

Article number

Volume number

Issue number

First page of article

ISSN of journal

0022-0000

Year of publication

2011

URL

http://www.sciencedirect.com/science/article/pii/S0022000010000917

Number of additional authors

Additional information

<12> Originality: First paper giving evidence against polynomial kernelizability of parameterized problems under a standard complexity assumption.

Significance: Many parameterized algorithms work by reducing the instance to a small "kernel". Until recently, there has been little theoretical understanding of which problems admit a small kernel. By relating this question to a standard complexity assumption, this paper helped to trigger a spate of positive and negative results on kernelizability. The paper appeared in the top theoretical computer science conference STOC 2008 (acceptance rate < 25%), with the journal version in JCSS.

Rigour: The paper consists of mathematical theorems with full proofs.

Interdisciplinary

Cross-referral requested

Research group

F - Laboratory for Foundations of Computer Science

Citation count

Proposed double-weighted

Double-weighted statement

Reserve for a double-weighted output

Non-English

English abstract