Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Amulya Musipatla:

TR20-158 | 26th October 2020
Eric Allender, Azucena Garvia Bosshard, Amulya Musipatla

A Note on Hardness under Projections for Graph Isomorphism and Time-Bounded Kolmogorov Complexity

This paper focuses on a variant of the circuit minimization problem (MCSP), denoted MKTP, which studies resource-bounded Kolmogorov complexity in place of circuit size. MCSP is not known to be hard for any complexity class under any kind of m-reducibility, but recently MKTP was shown to be hard for DET ... more >>>

ISSN 1433-8092 | Imprint