### 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

#### 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.

## Comments

Start the discussion!