|COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring.|
Language compression for sets in P/poly
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.
This talk is included in these lists:
Note that ex-directory lists are not shown.
Other listsMRC Centenary - Series of Public Lectures HEP/GR Informal Seminar Series for Graduate Students Nineteenth-Century Epic
Other talksSurface Plasmon Resonance (Biacore) Fancy some PIMMS? Or want to stay SLIMM? Memory theories worthy of their acronyms? Annual Conversazione tba Shock compression of geological materials Tissue Engineering Today