Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DISTINGUISHING COMPLEIXTY:
Reports tagged with distinguishing compleixty:
TR04-031 | 22nd March 2004
Troy Lee, Andrei Romashchenko

On Polynomially Time Bounded Symmetry of Information

The information contained in a string x about a string y
is defined as the difference between the Kolmogorov complexity
of y and the conditional Kolmogorov complexity of y given x,
i.e., I(x:y)=\C(y)-\C(y|x). From the well-known Kolmogorov--Levin Theorem it follows that I(x:y) is symmetric up to a small ... more >>>


TR17-043 | 3rd March 2017
Alexey Milovanov, Nikolay Vereshchagin

Stochasticity in Algorithmic Statistics for Polynomial Time

A fundamental notion in Algorithmic Statistics is that of a stochastic object, i.e., an object having a simple plausible explanation. Informally, a probability distribution is a plausible explanation for x if it looks likely that x was drawn at random with respect to that distribution. In this paper, we ... more >>>




ISSN 1433-8092 | Imprint