Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with probabilistic arguments:
TR04-054 | 5th June 2004
Andrej Muchnik, Alexander Shen, Nikolay Vereshchagin, Mikhail V. Vyugin

Non-reducible descriptions for conditional Kolmogorov complexity

Let a program p on input a output b. We are looking for a
shorter program p' having the same property (p'(a)=b). In
addition, we want p' to be simple conditional to p (this
means that the conditional Kolmogorov complexity K(p'|p) is
negligible). In the present paper, we prove that ... more >>>

TR19-180 | 6th December 2019
Andreas Lenz, Cyrus Rashtchian, Paul Siegel, Eitan Yaakobi

Covering Codes for Insertions and Deletions

Revisions: 1

A covering code is a set of codewords with the property that the union of balls, suitably defined, around these codewords covers an entire space. Generally, the goal is to find the covering code with the minimum size codebook. While most prior work on covering codes has focused on the ... more >>>

ISSN 1433-8092 | Imprint