Title: New Insights on the (Non)-Hardness of Circuit Minimization and Related Problems
Speaker: Eric Allender, Rutgers University
Date: Wednesday, November 16, 2016 11:00am-12:00pm
Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
The Minimum Circuit Size Problem (MCSP) and a related problem (MKTP) that deals with time-bounded Kolmogorov complexity are prominent candidates for NP-intermediate status. We prove new unconditional lower bounds for MKTP, by showing that MKTP is hard for the complexity class DET (a class that captures the complexity of computing the determinant; DET contains NL) under non-uniform NC0 reductions.
Under a suitable derandomization hypothesis, we obtain uniform reductions, and we are even able to show that circuit size lower bounds are equivalent to hardness results for certain problems related to MKTP, and provide the first results showing that hardness of MCSP problems implies hardness for MKTP problems. We also present new results relating the complexity of various promise problems related to MCSP and MKTP. We show that, under modest cryptographic assumptions, some of these promise problems must have intermediate complexity: they have no solution in P/poly and are not NP-hard under P/poly reductions.
Joint work with Shuichi Hirahara.
See: http://www.math.rutgers.edu/~sk1233/theory-seminar/F16/