Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with coding:
TR11-042 | 25th March 2011
Ankur Moitra

Efficiently Coding for Interactive Communication

Revisions: 1

In 1992, Schulman proved a coding theorem for interactive communication and demonstrated that interactive communication protocols can be made robust to noise with only a constant slow-down (for a sufficiently small error rate) through a black-box reduction. However, this scheme is not computationally {\em efficient}: the running time to construct ... more >>>

TR21-041 | 15th March 2021
Zhenjian Lu, Igor Carboni Oliveira

An Efficient Coding Theorem via Probabilistic Representations and its Applications

A probabilistic representation of a string $x \in \{0,1\}^n$ is given by the code of a randomized algorithm that outputs $x$ with high probability [Oliveira, ICALP 2019]. We employ probabilistic representations to establish the first unconditional Coding Theorem in time-bounded Kolmogorov complexity. More precisely, we show that if a distribution ... more >>>

ISSN 1433-8092 | Imprint