Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Minimum Circuit Size:
TR17-073 | 28th April 2017
Eric Allender, Shuichi Hirahara

New Insights on the (Non)-Hardness of Circuit Minimization and Related Problems

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 show that, under very modest cryptographic assumptions (such as the existence of one-way functions), the problem of approximating the minimum circuit size (or time-bounded Kolmogorov complexity) ... more >>>

TR20-153 | 6th October 2020
Robert Kleinberg, Daniel Mitropolsky, Christos Papadimitriou

Total Functions in the Polynomial Hierarchy

We identify several genres of search problems beyond NP for which existence of solutions is guaranteed. One class that seems especially rich in such problems is PEPP (for "polynomial empty pigeonhole principle"), which includes problems related to existence theorems proved through the union bound, such as finding a bit string ... more >>>

ISSN 1433-8092 | Imprint