Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with MCSP:
TR21-009 | 1st February 2021
Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich

One-way Functions and Partial MCSP

Revisions: 3 , Comments: 1

One-way functions (OWFs) are central objects of study in cryptography and computational complexity theory. In a seminal work, Liu and Pass (FOCS 2020) proved that the average-case hardness of computing time-bounded Kolmogorov complexity is equivalent to the existence of OWFs. It remained an open problem to establish such an equivalence ... more >>>

TR21-170 | 25th November 2021
Reyad Abed Elrazik, Robert Robere, Assaf Schuster, Gal Yehuda

Pseudorandom Self-Reductions for NP-Complete Problems

A language $L$ is random-self-reducible if deciding membership in $L$ can be reduced (in polynomial time) to deciding membership in $L$ for uniformly random instances. It is known that several "number theoretic" languages (such as computing the permanent of a matrix) admit random self-reductions. Feigenbaum and Fortnow showed that NP-complete ... more >>>

TR23-010 | 13th February 2023
Per Austrin, Kilian Risse

Sum-of-Squares Lower Bounds for the Minimum Circuit Size Problem

We prove lower bounds for the Minimum Circuit Size Problem (MCSP) in the Sum-of-Squares (SoS) proof system. Our main result is that for every Boolean function $f: \{0,1\}^n \rightarrow \{0,1\}$, SoS requires degree $\Omega(s^{1-\epsilon})$ to prove that $f$ does not have circuits of size $s$ (for any $s > \text{poly}(n)$). ... more >>>

ISSN 1433-8092 | Imprint