Per Austrin

SODA Conference 2022 Conference Paper

Perfect Matching in Random Graphs is as Hard as Tseitin

• Per Austrin
• Kilian Risse

SODA Conference 2021 Conference Paper

Optimal Inapproximability with Universal Factor Graphs

• 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 Max-CSPs remain as hard to approximate as in the general case even when the factor graph is fixed (depending only on the size of the instance) and known in advance. Examples of results obtained for this restricted setting are: Optimal inapproximability for Max-3-Lin and Max-3-Sat (Håstad, J. ACM 2001). Approximation resistance for predicates supporting pairwise independent subgroups (Chan, J. ACM 2016). Hardness of the “(2 + ∊ )-Sat” problem and other Promise CSPs (Austrin et al. , SIAM J. Comput. 2017). The main technical tool used to establish these results is a new way of folding the long code which we call “functional folding”.

SODA Conference 2020 Conference Paper

Improved Inapproximability of Rainbow Coloring

• Per Austrin
• Amey Bhangale
• Aditya Potukuchi

A rainbow q -coloring of a k -uniform hypergraph is a q -coloring of the vertex set such that every hyperedge contains all q colors. We prove that given a rainbow -colorable k -uniform hypergraph, it is NP -hard to find a normal 2-coloring. Previously, this was only known for rainbow -colorable hypergraphs (Guruswami and Lee, SODA 2015). We also study a generalization which we call rainbow ( q, p )-coloring, defined as a coloring using q colors such that every hyperedge contains at least p colors. We prove that given a rainbow -colorable k uniform hypergraph, it is NP -hard to find a normal c -coloring for any c = o ( k ). The proof of our second result relies on two combinatorial theorems. One of the theorems was proved by Sarkaria (J. Comb. Theory, Ser. B 1990) using topological methods and the other theorem we prove using a generalized Borsuk-Ulam theorem.

IJCAI Conference 2015 Conference Paper

Inapproximability of Treewidth and Related Problems (Extended Abstract)

• Yu Wu
• Per Austrin
• Toniann Pitassi
• David Liu

Graphical models, such as Bayesian Networks and Markov networks play an important role in artificial intelligence and machine learning. Inference is a central problem to be solved on these networks. This, and other problems on these graph models are often known to be hard to solve in general, but tractable on graphs with bounded Treewidth. Therefore, finding or approximating the Treewidth of a graph is a fundamental problem related to inference in graphical models. In this paper, we study the approximability of a number of graph problems: Treewidth and Pathwidth of graphs, Minimum Fill- In, and a variety of different graph layout problems such as Minimum Cut Linear Arrangement. We show that, assuming Small Set Expansion Conjecture, all of these problems are NP-hard to approximate to within any constant factor in polynomial time. This paper is an extended abstract of the Journal of Artificial Intelligence Research [Wu et al. , 2014]

FOCS Conference 2014 Conference Paper

(2 + epsilon)-Sat Is NP-Hard

• Per Austrin
• Johan Håstad
• Venkatesan Guruswami

We prove the following hardness result for anatural promise variant of the classical CNF-satisfiabilityproblem: Given a CNF-formula where each clause has widthw and the guarantee that there exists an assignment satisfyingat least g = [w/2] - 1 literals in each clause, it is NP-hard tofind a satisfying assignment to the formula (that sets at leastone literal to true in each clause). On the other hand, when g = [w/2], it is easy to find a satisfying assignment via simplegeneralizations of the algorithms for 2-SAT. Viewing 2-SAT ∈ P as easiness of SAT when 1-in-2 literals are true in every clause, and NP-hardness of 3-SAT as intractability of SAT when 1-in-3 literals are true, our resultshows, for any fixed ε > 0, the hardness of finding a satisfyingassignment to instances of "(2 + ε)-SAT" where the density ofsatisfied literals in each clause is promised to exceed 1/(2+ε). We also strengthen the results to prove that given a (2k + 1)-uniform hypergraph that can be 2-colored such that each edgehas perfect balance (at most k + 1 vertices of either color), itis NP-hard to find a 2-coloring that avoids a monochromaticedge. In other words, a set system with discrepancy 1 is hard todistinguish from a set system with worst possible discrepancy.

SODA Conference 2013 Conference Paper

Better Balance by Being Biased: A 0. 8776-Approximation for Max Bisection

• Per Austrin
• Siavosh Benabbas
• Konstantinos Georgiou

Recently Raghavendra and Tan (SODA 2012) gave a 0. 85-approximation algorithm for the M ax B isection problem. We improve their algorithm to a 0. 8776-approximation. As M ax B isection is hard to approximate within α GW + ∊ ≈ 0. 8786 under the Unique Games Conjecture (UGC), our algorithm is nearly optimal. We conjecture that M ax B isection is approximable within α GW − ∊, i. e. , the bisection constraint (essentially) does not make M ax C ut harder. We also obtain an optimal algorithm (assuming the UGC) for the analogous variant of M ax 2-S at. Our approximation ratio for this problem exactly matches the optimal approximation ratio for M ax 2-S at, i. e. , α LLZ + ∊ ≈ 0. 9401, showing that the bisection constraint does not make M ax 2-S at harder. This improves on a 0. 93-approximation for this problem due to Raghavendra and Tan.

STOC Conference 2009 Conference Paper

Randomly supported independence and resistance

• Per Austrin
• Johan Håstad

STOC Conference 2007 Conference Paper

Balanced max 2-sat might not be the hardest

• Per Austrin

FOCS Conference 2007 Conference Paper

Towards Sharp Inapproximability For Any 2-CSP

• Per Austrin

We continue the recent line of work on the connection between semidefinite programming-based approximation algorithms and the Unique Games Conjecture. Given any-boolean 2-CSP (or more generally, any nonnegative objective function on two boolean variables), we show how to reduce the search for a good inapproximability result to a certain numeric minimization problem. The key objects in our analysis are the vector triples arising when doing clause-by-clause analysis of algorithms based on semidefinite programming. Given a weighted set of such triples of a certain restricted type, which are "hard" to round in a certain sense, we obtain a Unique Games-based inapproximability matching this "hardness" of rounding the set of vector triples. Conversely, any instance together with an SDP solution can be viewed as a set of vector triples, and we show that we can always find an assignment to the instance which is at least as good as the "hardness" of rounding the corresponding set of vector triples. We conjecture that the restricted type required for the hardness result is in fact no restriction, which would imply that these upper and lower bounds match exactly. This conjecture is supported by all existing results for specific 2-CSPs. As an application, we show that Max 2-AND is hard to approximate within 0. 87435. This improves upon the best previous hardness of alpha GW + epsi ap 0. 87856, and comes very close to matching the approximation ratio of the best algorithm known, 0. 87401. It also establishes that balanced instances of Max 2-AND, i. e. , instances in which each variable occurs positively and negatively equally often, are not the hardest to approximate, as these can be approximated within a factor alpha GW.