Skip to content

SAS

Seminar

Language compression for sets in P/poly

Zimand, M (Towson University)
Wednesday 04 July 2012, 10:00-10:30

Seminar Room 1, Newton Institute

Abstract

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$)| $\approx \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^{=n}|) + 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.

Presentation

[pdf ]

Video

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧