All reports by Author Per Austrin:

__
TR23-010
| 13th February 2023
__

Per Austrin, Kilian Risse#### Sum-of-Squares Lower Bounds for the Minimum Circuit Size Problem

__
TR21-021
| 18th February 2021
__

Per Austrin, Kilian Risse#### Average-Case Perfect Matching Lower Bounds from Hardness of Tseitin Formulas

Revisions: 2

__
TR19-151
| 5th November 2019
__

Per Austrin, Jonah Brown-Cohen, Johan Håstad#### Optimal Inapproximability with Universal Factor Graphs

__
TR19-048
| 2nd April 2019
__

Per Austrin, Amey Bhangale, Aditya Potukuchi#### Simplified inpproximability of hypergraph coloring via t-agreeing families

__
TR13-159
| 20th November 2013
__

Per Austrin, Venkatesan Guruswami, Johan Håstad#### $(2+\epsilon)$-SAT is NP-hard

Revisions: 2

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

Per Austrin, Kilian Risse

We study the complexity of proving that a sparse random regular graph on an odd number of vertices does not have a perfect matching, and related problems involving each vertex being matched some pre-specified number of times. We show that this requires proofs of degree $\Omega(n/\log n)$ in the Polynomial ... more >>>

Per Austrin, Jonah Brown-Cohen, Johan Håstad

The factor graph of an instance of a constraint satisfaction problem (CSP) is the bipartite graph indicating which variables appear in each constraint. An instance of the CSP is given by the factor graph together with a list of which predicate is applied for each constraint. We establish that many ... more >>>

Per Austrin, Amey Bhangale, Aditya Potukuchi

We reprove the results on the hardness of approximating hypergraph coloring using a different technique based on bounds on the size of extremal $t$-agreeing families of $[q]^n$. Specifically, using theorems of Frankl-Tokushige [FT99], Ahlswede-Khachatrian [AK98] and Frankl [F76] on the size of such families, we give simple and unified proofs ... more >>>

Per Austrin, Venkatesan Guruswami, Johan Håstad

We prove the following hardness result for a natural promise variant of the classical CNF-satisfiability problem: Given a CNF-formula where each clause has width $w$ and the guarantee that there exists an assignment satisfying at least $g = \lceil \frac{w}{2}\rceil -1$ literals in each clause, it is NP-hard to find ... more >>>