Personal tools
You are here: Home Events Lab Lunch by Chiranjit Chakraborty

Lab Lunch by Chiranjit Chakraborty

Instance compression and Counting hierarchy

What
When Mar 26, 2013
from 01:00 PM to 02:00 PM
Where MF2
Add event to calendar vCal
iCal

I will talk about the notion of instance compression and discuss some of my recent results to provide a structural theory of compressibility, analogous to the complexity theory in the classical setting. I will discuss about VC hierarchy and its counting counterpart developed in this context and point out their relations with some other existing hierarchies. I will focus mainly on the counting hierarchies and discuss some of the interesting counting problems whose decision versions are showing significantly different characteristics with respect to compression.

Document Actions