Per

Per Austrin

I am an Associate Professor in the Theory Group at the School of Computer Science and Communication at KTH.

I am very fond of combinatorics and theoretical computer science. My research interests include computational complexity and approximation algorithms.

E-mail lastname at kth dot se

Phone +46 (8) 790 62 86

Address KTH CSC
Lindstedtsvägen 3
S-10044 Stockholm
Sweden

Visiting address Room 4533

Swedish Summer School in Computer Science

The Swedish Summer School in Computer Science takes place June 29 - July 5 in Stockholm, with Boaz Barak and Ryan O'Donnell as speakers.

Committees

I was on the program committee of RANDOM 2011, STOC 2013 and SODA 2014. I am on the program committee of SWAT 2014.

Publications

Journal Papers

[AH13] Per Austrin and Johan Håstad, On the usefulness of predicates, ACM Transactions on Computation Theory, vol. 5, no. 1, pp. 1-24, 2013. [ DOI | arXiv ]
[ABC13] Per Austrin, Mark Braverman, and Eden Chlamtáč, Inapproximability of NP-Complete Variants of Nash Equilibrium, Theory of Computing, vol. 9, no. 3, pp. 117-142, 2013. [ DOI ]
[ABM12] Per Austrin, Siavosh Benabbas, and Avner Magen, On Quadratic Threshold CSPs, Discrete Mathematics & Theoretical Computer Science, vol. 14, no. 2, pp. 205-228, 2012. [ http ]
[AM11] Per Austrin and Elchanan Mossel, Noise Correlation Bounds for Uniform Low Degree Functions, To appear in Arkiv för Matematik. [ DOI | arXiv ]
[AKS11] Per Austrin, Subhash Khot, and Muli Safra, Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs, Theory of Computing, vol. 7, no. 1, pp. 27-43, 2011. [ DOI | pdf ]
[AH11] Per Austrin and Johan Håstad, Randomly Supported Independence and Resistance, SIAM Journal on Computing, vol. 40, no. 1, pp. 1-27, 2011. [ DOI | pdf ]
[Aus10] Per Austrin, Towards Sharp Inapproximability for Any 2-CSP, SIAM Journal on Computing, vol. 39, no. 6, pp. 2430-2463, 2010. [ DOI | pdf ]
[AM09] Per Austrin and Elchanan Mossel, Approximation Resistant Predicates from Pairwise Independence, Computational Complexity, vol. 18, no. 2, pp. 249-271, 2009. [ DOI | pdf ]

Refereed Conference Papers

[AMW13] Per Austrin, Rajsekar Manokaran, and Cenny Wenner, On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems, in International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2013, pp. 26-41. [ arXiv ]
[AKKM13] Per Austrin, Petteri Kaski, Mikko Koivisto, and Jussi Määttä, Space-Time Tradeoffs for Subset Sum: An Improved Worst Case Algorithm, in International Colloquium on Automata, Languages and Programming (ICALP), 2013, pp. 45-56. [ arXiv ]
[AHP13] Per Austrin, Johan Håstad, and Rafael Pass, On the power of many one-bit provers, in Innovations in Theoretical Computer Science (ITCS), 2013, pp. 215-220. [ DOI | arXiv ]
[AK13] Per Austrin and Subhash Khot, A Characterization of Approximation Resistance for Even k-Partite CSPs, in Innovations in Theoretical Computer Science (ITCS), 2013, pp. 187-196. [ DOI | arXiv ]
[ABG13] Per Austrin, Siavosh Benabbas, and Konstantinos Georgiou, Better Balance by Being Biased: a 0.8776-Approximation for Max Bisection, in ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013. [ arXiv ]
[AOW12] Per Austrin, Ryan O'Donnell, and John Wright, A New Point of NP-Hardness for 2-to-1 Label Cover, in International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2012, pp. 1-12, Superseded by AOTW12 which contains additional results. [ DOI | arXiv ]
[APW12] Per Austrin, Toniann Pitassi, and Yu Wu, Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems, in International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2012, pp. 13-24. [ DOI | arXiv ]
[AH12] Per Austrin and Johan Håstad, On the Usefulness of Predicates, in IEEE Conference on Computational Complexity (CCC), 2012, pp. 53-63, Note: Superseded by journal version: [AH13].
[ABC11] Per Austrin, Mark Braverman, and Eden Chlamtáč, Inapproximability of NP-Complete Variants of Nash Equilibrium, in International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2011, pp. 13-25, Note: Superseded by journal version: [ABC13].
[AK11] Per Austrin and Subhash Khot, A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem, in International Colloquium on Automata, Languages and Programming (ICALP), 2011, pp. 474-485. [ DOI | arXiv ]
[Aus10b] Per Austrin, Improved Inapproximability for Submodular Maximization, in International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2010, pp. 12-24. [ DOI | arXiv ]
[ABM10] Per Austrin, Siavosh Benabbas, and Avner Magen, On Quadratic Threshold CSPs, in Latin American Theoretical Informatics Symposium (LATIN), 2010, pp. 332-343, Note: Superseded by journal version: [ABM12].
[AKS09] Per Austrin, Subhash Khot, and Muli Safra, Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs, in IEEE Conference on Computational Complexity (CCC), 2009, pp. 74-80, Note: Superseded by journal version: [AKS11].
[AH09] Per Austrin and Johan Håstad, Randomly Supported Independence and Resistance, in ACM Symposium on Theory of Computing (STOC), 2009, pp. 483-492, Note: Superseded by journal version: [AH11]. This version may be easier to read than the journal version as it deals only with the case of uniform distributions over the Boolean domain. The proofs for the general case are the same but the notation is more cumbersome. [ DOI | pdf ]
[AM08] Per Austrin and Elchanan Mossel, Approximation Resistant Predicates From Pairwise Independence, in IEEE Conference on Computational Complexity (CCC), 2008, pp. 249-258, Note: Superseded by journal version: [AM09].
[AK08] Per Austrin and Gunnar Kreitz, Lower bounds for subset cover based broadcast encryption, in Progress in Cryptology - AFRICACRYPT, 2008, pp. 343-356. [ DOI | pdf ]
[Aus07b] Per Austrin, Towards Sharp Inapproximability For Any 2-CSP, in IEEE Symposium on Foundations of Computer Science (FOCS), 2007, pp. 307-317, Note: Superseded by journal version: [Aus10].
[Aus07a] Per Austrin, Balanced Max 2-Sat Might Not be the Hardest, in ACM Symposium on Theory of Computing (STOC), 2007, pp. 189-197. [ DOI | pdf | ECCC ]

Manuscripts

[AGH13] Per Austrin, Venkatesan Guruswami, and Johan Håstad, (2+ε)-SAT is NP-hard, Electronic Colloquium on Computational Complexity (ECCC), 2013. [ ECCC ]
[ACMPS12] Per Austrin, Kai-Min Chung, Mohammad Mahmoody, Rafael Pass, and Karn Seth, On the (Im)Possibility of Tamper-Resilient Cryptography: Using Fourier Analysis in Computer Viruses, Manuscript. [ pdf ]
[AOTW12] Per Austrin, Ryan O'Donnell, Li-Yang Tan, and John Wright, New NP-hardness results for 3-Coloring and 2-to-1 Label Cover, Manuscript, 2012. [ arXiv ]

Thesis

[Aus08] Per Austrin, Conditional Inapproximability and Limited Independence, PhD thesis, KTH - Royal Institute of Technology, 2008. [ pdf | errata ]
I have a large number of physical copies of the thesis. Let me know if you want one (or more).