University of Cambridge > > Isaac Newton Institute Seminar Series > Language compression for sets in P/poly

Language compression for sets in P/poly

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Mustapha Amrani.

Semantics and Syntax: A Legacy of Alan Turing

If we consider a finite set $A$, it is desirable to represent every $x$ in $A$ by another shorter string compressed($x$) such that compressed($x$) describes unambiguously the initial $x$. Regarding the compression rate, ideally, one would like to achieve the information-theoretical bound |compressed($x$)| $pprox log (|A|)$, for all $x$ in $A$. This optimal rate is achievable for c.e. (and also co-c.e.) sets $A$, because for such a set C($x$) $leq log (|A|) + O(log n)$ (C($x$) is the Kolmogorov complexity of string $x$ and $n$ is the length of $x$). In the time-bounded setting, we would like to have a polynomial-time type of unambiguous description. The relevant concept is the time-bounded distinguishing complexity, CD(), introduced by Sipser. The $t$-time bounded distinguishing complexity of $x$, denoted CD$t(x)$ is the length of the shortest program $p$ that accepts $x$ and only $x$ within time $t(|x|)$. Recently we have shown that for sets in P, NP, PSPACE , optimal compression can be achieved, using some reasonable hardness assumptions. We show that this also holds for sets in P/poly, i.e., for sets computable by polynomial-size circuits. Furthermore, we sketch here a different proof method (even though some key elements are common) suggested by Vinodchandran, which needs a weaker hardness assumption.

This talk is part of the Isaac Newton Institute Seminar Series series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2020, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity