Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Detlef Ronneburger:

TR09-051 | 2nd July 2009
Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy

The Pervasive Reach of Resource-Bounded Kolmogorov Complexity in Computational Complexity Theory

We continue an investigation into resource-bounded Kolmogorov complexity \cite{abkmr}, which highlights the close connections between circuit complexity and Levin's time-bounded Kolmogorov complexity measure Kt (and other measures with a similar flavor), and also exploits derandomization techniques to provide new insights regarding Kolmogorov complexity.
The Kolmogorov measures that have been ... more >>>

TR02-028 | 15th May 2002
Eric Allender, Harry Buhrman, Michal Koucky, Detlef Ronneburger, Dieter van Melkebeek

Power from Random Strings

Revisions: 1

We consider sets of strings with high Kolmogorov complexity, mainly
in resource-bounded settings but also in the traditional
recursion-theoretic sense. We present efficient reductions, showing
that these sets are hard and complete for various complexity classes.

In particular, in addition to the usual Kolmogorov complexity measure
K, ... more >>>

TR01-041 | 23rd May 2001
Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy, V Vinay

Time-Space Tradeoffs in the Counting Hierarchy

We extend the lower bound techniques of [Fortnow], to the
unbounded-error probabilistic model. A key step in the argument
is a generalization of Nepomnjascii's theorem from the Boolean
setting to the arithmetic setting. This generalization is made
possible, due to the recent discovery of logspace-uniform TC^0
more >>>

ISSN 1433-8092 | Imprint