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 Problem (MCSP):
TR19-018 | 18th February 2019
Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal

AC0[p] Lower Bounds against MCSP via the Coin Problem

Minimum Circuit Size Problem (MCSP) asks to decide if a given truth table of an $n$-variate boolean function has circuit complexity less than a given parameter $s$. We prove that MCSP is hard for constant-depth circuits with mod $p$ gates, for any prime $p\geq 2$ (the circuit class $AC^0[p])$. Namely, ... more >>>

TR19-021 | 19th February 2019
Rahul Ilango

$AC^0[p]$ Lower Bounds and NP-Hardness for Variants of MCSP

The Minimum Circuit Size Problem (MCSP) asks whether a (given) Boolean function has a circuit of at most a (given) size. Despite over a half-century of study, we know relatively little about the computational complexity of MCSP. We do know that questions about the complexity of MCSP have significant ramifications ... more >>>

TR19-022 | 23rd February 2019
Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis

Circuit Lower Bounds for MCSP from Local Pseudorandom Generators

Revisions: 1

The Minimum Circuit Size Problem (MCSP) asks if a given truth table of a Boolean function $f$ can be computed by a Boolean circuit of size at most $\theta$, for a given parameter $\theta$. We improve several circuit lower bounds for MCSP, using pseudorandom generators (PRGs) that are local; a ... more >>>

TR19-025 | 28th February 2019
Shuichi Hirahara, Osamu Watanabe

On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets

Revisions: 1

We investigate the computational power of an arbitrary distinguisher for (not necessarily computable) hitting set generators as well as the set of Kolmogorov-random strings. This work contributes to (at least) two lines of research. One line of research is the study of the limits of black-box reductions to some distributional ... more >>>

TR19-118 | 5th September 2019
Lijie Chen, Ce Jin, Ryan Williams

Hardness Magnification for all Sparse NP Languages

In the Minimum Circuit Size Problem (MCSP[s(m)]), we ask if there is a circuit of size s(m) computing a given truth-table of length n = 2^m. Recently, a surprising phenomenon termed as hardness magnification by [Oliveira and Santhanam, FOCS 2018] was discovered for MCSP[s(m)] and the related problem MKtP of ... more >>>

TR20-065 | 2nd May 2020
Lijie Chen, Ce Jin, Ryan Williams

Sharp Threshold Results for Computational Complexity

We establish several ``sharp threshold'' results for computational complexity. For certain tasks, we can prove a resource lower bound of $n^c$ for $c \geq 1$ (or obtain an efficient circuit-analysis algorithm for $n^c$ size), there is strong intuition that a similar result can be proved for larger functions of $n$, ... more >>>

TR20-078 | 21st May 2020
Eric Allender

The New Complexity Landscape around Circuit Minimization

We survey recent developments related to the Minimum Circuit Size Problem

more >>>

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 >>>

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