Personal tools
You are here: Home Events Lab Lunch by Andrew Drucker

Lab Lunch by Andrew Drucker

— filed under:

Limits to Efficient Preprocessing

  • Lab Lunch
When Feb 03, 2015
from 01:00 PM to 02:00 PM
Add event to calendar vCal

Kernelization is an influential paradigm for attacking hard computational problems.  Kernelization algorithms efficiently preprocess their input to “shrink” it to a smaller, equivalent one.  This can be a valuable first step before applying exhaustive-search techniques.


After giving the basic framework of kernelization, I’ll describe my contribution to a line of works showing *limits* to the achievable performance of kernelization algorithms for many NP problems (under complexity-theoretic assumptions).


Based on: 


[A. Drucker,  New Limits to Classical and Quantum Instance Compression. FOCS’12]

Document Actions