BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Language compression for sets in P/poly - Zimand\, M (Towson Unive
 rsity)
DTSTART:20120704T090000Z
DTEND:20120704T093000Z
UID:TALK38844@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:If we consider a finite set $A$\, it is desirable to represent
  every\n$x$ in $A$ by another shorter string compressed($x$) such that\nco
 mpressed($x$) describes unambiguously the initial $x$. Regarding\nthe comp
 ression rate\, ideally\, one would like to achieve the\ninformation-theore
 tical bound |compressed($x$)| $pprox log (|A|)$\,\nfor all $x$ in $A$. Th
 is optimal rate is achievable for c.e. (and also\nco-c.e.) sets $A$\, beca
 use for such a set C($x$) $leq log (|A^{=n}|)\n+ O(log n)$ (C($x$) is the 
 Kolmogorov complexity of string $x$ and $n$\nis the length of $x$). In the
  time-bounded setting\, we would like to have\na polynomial-time type of u
 nambiguous description. The relevant concept\nis the time-bounded distingu
 ishing complexity\, CD()\, introduced by\nSipser. The $t$-time bounded dis
 tinguishing complexity of $x$\, denoted\nCD$^t(x)$ is the length of the sh
 ortest program $p$ that accepts $x$\nand only $x$ within time $t(|x|)$. Re
 cently we have shown that for\nsets in P\, NP\, PSPACE\, optimal compressi
 on can be achieved\, using some\nreasonable hardness assumptions. We show 
 that this also holds for sets\nin P/poly\, i.e.\, for sets computable by p
 olynomial-size\ncircuits. Furthermore\, we sketch here a different proof m
 ethod (even\nthough some key elements are common) suggested by Vinodchandr
 an\, which\nneeds a weaker hardness assumption.\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR