11 citations · 27 across the 17 of their papers we have counts for
1 paper · 2 filters
Per Austrin, Kilian Risse
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 \righta…