Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Resource-bounded Kolmogorov complexity:
TR04-029 | 7th April 2004
John Hitchcock, Maria Lopez-Valdes, Elvira Mayordomo

Scaled dimension and the Kolmogorov complexity of Turing hard sets

Scaled dimension has been introduced by Hitchcock et al (2003) in order to quantitatively distinguish among classes such as SIZE(2^{a n}) and SIZE(2^{n^{a}}) that have trivial dimension and measure in ESPACE.

more >>>

TR15-198 | 30th November 2015
Shuichi Hirahara, Osamu Watanabe

Limits of Minimum Circuit Size Problem as Oracle

Revisions: 1

The Minimum Circuit Size Problem (MCSP) is known to be hard for statistical zero knowledge via a BPP-reduction (Allender and Das, 2014), whereas establishing NP-hardness of MCSP via a polynomial-time many-one reduction is difficult (Murray and Williams, 2015) in the sense that it implies ZPP $\neq$ EXP, which is a ... more >>>

ISSN 1433-8092 | Imprint