# Language compression for sets in P/poly

• Zimand, M (Towson University)
• Wednesday 04 July 2012, 10:00-10:30
• Seminar Room 1, Newton Institute.

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.