Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author John Gouwar:

TR21-010 | 11th February 2021
Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle

Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity

A version of time-bounded Kolmogorov complexity, denoted KT, has received attention in the past several years, due to its close connection to circuit complexity and to the Minimum Circuit Size Problem MCSP. Essentially all results about the complexity of MCSP hold also for MKTP (the problem of computing the KT ... more >>>

ISSN 1433-8092 | Imprint