ECCC-Report TR20-158https://eccc.weizmann.ac.il/report/2020/158Comments and Revisions published for TR20-158en-usMon, 26 Oct 2020 23:00:01 +0200
Paper TR20-158
| A Note on Hardness under Projections for Graph Isomorphism and Time-Bounded Kolmogorov Complexity |
Eric Allender,
Azucena Garvia Bosshard,
Amulya Musipatla
https://eccc.weizmann.ac.il/report/2020/158This 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 under m-reductions computable in NC0, by presenting an AC0 reduction from the rigid graph isomorphism problem to MKTP, and combining that with a theorem of Toran, showing that DET AC0-reduces to the rigid graph isomorphism problem, and then appealing to the "Gap Theorem" of [Agrawal, Allender, Rudich]. Here, we show that these reductions can be accomplished by means of projections. Thus MKTP is hard for DET under projections, and the rigid graph isomorphism problem is hard for DET under uniform projections.Mon, 26 Oct 2020 23:00:01 +0200https://eccc.weizmann.ac.il/report/2020/158