11 citations · 27 across the 17 of their papers we have counts for
24 papers
On the Usefulness of Promises
Per Austrin, Johan Håstad, Björn Martinsson
A Boolean predicate is defined to be promise-useful if is tractable for some non-trivial and otherwise it is promise-useless. We initiate investi…
Algorithms for the Diverse-k-SAT problem: the geometry of satisfying assignments
Per Austrin, Ioana O. Bercea, Mayank Goswami +2
Given a -CNF formula and an integer , we study algorithms that obtain solutions to the formula that are maximally dispersed. For , the problem of computing the diame…
Sum-of-Squares Lower Bounds for the Minimum Circuit Size Problem
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…
Perfect Matching in Random Graphs is as Hard as Tseitin
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 bein…
Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
Per Austrin, Aleksa Stankovic
Assuming the Unique Games Conjecture, we show that existing approximation algorithms for some Boolean Max-2-CSPs with cardinality constraints are optimal. In particular, we prove t…
Simplified inpproximability of hypergraph coloring via t-agreeing families
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 -agreeing families of . Sp…