Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > PER AUSTRIN:
All reports by Author Per Austrin:

TR19-151 | 5th November 2019
Per Austrin, Jonah Brown-Cohen, Johan Hastad

Optimal Inapproximability with Universal Factor Graphs

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


TR19-048 | 2nd April 2019
Per Austrin, Amey Bhangale, Aditya Potukuchi

Simplified inpproximability of hypergraph coloring via t-agreeing families

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


TR13-159 | 20th November 2013
Per Austrin, Venkatesan Guruswami, Johan Hastad

$(2+\epsilon)$-SAT is NP-hard

Revisions: 2

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




ISSN 1433-8092 | Imprint