Per Austrin
I am an Associate Professor in the Theory Group at the School of Electrical Engineering and Computer Science at KTH.
I am very fond of combinatorics and theoretical computer science. My research interests include computational complexity and approximation algorithms.
| lastname at kth dot se |
|
| Phone | +46 (8) 790 62 86 |
| Address |
KTH EECS Lindstedtsvägen 3 S-10044 Stockholm Sweden |
| Visiting address | Room 4533 |
Swedish Summer School in Computer Science
The Swedish Summer School in Computer Science runs every summer in the Stockholm archipelago, but is currently on hiatus due to the ongoing pandemic. We hope to return again in 2022.Publications
Journal Papers
| [AKKN18] | Per Austrin, Petteri Kaski, Mikko Koivisto, and Jesper Nederlof, Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs, IEEE Transactions on Information Theory, vol. 64, no. 2, pp. 1368--1373, 2018. [ DOI | http ] |
| [ACMPS17] | Per Austrin, Kai-Min Chung, Mohammad Mahmoody, Rafael Pass, and Karn Seth, On the Impossibility of Cryptography with Tamperable Randomness, Algorithmica, vol. 79, no. 4, pp. 1052--1101, 2017. [ DOI | http ] |
| [AGH17] | Per Austrin, Venkatesan Guruswami, and Johan Håstad, (2+ε)-sat is NP-hard, SIAM Journal on Computing, vol. 46, no. 5, pp. 1554--1573, 2017. [ DOI | http ] |
| [ABG16] | Per Austrin, Siavosh Benabbas, and Konstantinos Georgiou, Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection, ACM Transactions on Algorithms, vol. 13, no. 1, pp. 2:1--2:27, 2016. [ DOI | http ] |
| [AMW15] | Per Austrin, Rajsekar Manokaran, and Cenny Wenner, On the NP-Hardness of Approximating Ordering-Constraint Satisfaction Problems, Theory of Computing, vol. 11, pp. 257--283, 2015. [ DOI | http ] |
| [AK14] | Per Austrin and Subhash Khot, A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem, IEEE Transactions on Information Theory, vol. 60, no. 10, pp. 6636--6645, 2014. [ DOI | arXiv ] |
| [WAPL14] | Yu Wu, Per Austrin, Toniann Pitassi, and David Liu, Inapproximability of Treewidth and Related Problems, J. Artif. Intell. Res. (JAIR), vol. 49, pp. 569--600, 2014. [ DOI | arXiv ] |
| [AOTW14] | Per Austrin, Ryan O'Donnell, Li-Yang Tan, and John Wright, New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover, ACM Transactions on Computation Theory, vol. 6, no. 1, pp. 2:1--2:20, 2014. [ DOI | arXiv ] |
| [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, Arkiv för Matematik, vol. 51, no. 1, pp. 29--52, 2011. [ 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
| [ABH21] | Per Austrin, Jonah Brown-Cohen, and Johan Håstad, Optimal inapproximability with universal factor graphs, in ACM-SIAM Symposium on Discrete Algorithms (SODA), Dániel Marx, Ed. 2021, pp. 434--453, SIAM. [ DOI | http ] |
| [ABP20] | Per Austrin, Amey Bhangale, and Aditya Potukuchi, Improved inapproximability of rainbow coloring, in ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020, pp. 1479--1495. [ DOI | http ] |
| [AS19] | Per Austrin and Aleksa Stanković, Global cardinality constraints make approximating some max-2-csps harder, in International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2019, pp. 24:1--24:17. [ DOI | http ] |
| [AKK19] | Per Austrin, Petteri Kaski, and Kaie Kubjas, Tensor network complexity of multilinear maps, in Innovations in Theoretical Computer Science (ITCS), 2019, pp. 7:1--7:21. [ DOI | http ] |
| [AKKN16b] | Per Austrin, Petteri Kaski, Mikko Koivisto, and Jesper Nederlof, Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs, in IEEE International Symposium on Information Theory (ISIT), 2016, pp. 335--339, Note: Superseded by journal version: [AKKN18] . [ DOI ] |
| [AKKN16a] | Per Austrin, Petteri Kaski, Mikko Koivisto, and Jesper Nederlof, Dense subset sum may be the hardest, in Symposium on Theoretical Aspects of Computer Science (STACS), 2016, pp. 13:1--13:14. [ DOI | http ] |
| [AKKN15] | Per Austrin, Petteri Kaski, Mikko Koivisto, and Jesper Nederlof, Subset Sum in the Absence of Concentration, in Symposium on Theoretical Aspects of Computer Science (STACS), 2015, pp. 48--61. [ DOI | http ] |
| [AGH14] | Per Austrin, Venkatesan Guruswami, and Johan Håstad, (2+ε)-SAT Is NP-Hard, in IEEE Annual Symposium on Foundations of Computer Science, FOCS, 2014, pp. 1--10, Note: Superseded by journal version: [AGH17] . [ DOI | http ] |
| [ACMPS14] | Per Austrin, Kai-Min Chung, Mohammad Mahmoody, Rafael Pass, and Karn Seth, On the impossibility of cryptography with tamperable randomness, in Advances in Cryptology (CRYPTO), 2014, pp. 462--479, Note: Superseded by journal version: [ACMPS17] . [ DOI | pdf ] |
| [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, Note: Superseded by journal version: [AMW15] . [ 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, pp. 277--294, Note: Superseded by journal version: [ABG16] . [ 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, Note: Superseded by journal version: [AOTW14] (Contains additional results). |
| [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, Note: Superseded by journal version: [WAPL14] (Contains additional results). |
| [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, Note: Superseded by journal version: [AK14] . |
| [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
| [AR21] | Per Austrin and Kilian Risse, Average-case perfect matching lower bounds from hardness of tseitin formulas, Electron. Colloquium Comput. Complex., vol. 28, pp. 21, 2021. [ http ] |
| [ABP19] | Per Austrin, Amey Bhangale, and Aditya Potukuchi, Simplified inpproximability of hypergraph coloring via t-agreeing families, Electron. Colloquium Comput. Complex., vol. 26, pp. 48, 2019. [ arXiv | http ] |
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). |
Committees
I was on the program committee of RANDOM 2011, STOC 2013, SODA 2014, SWAT 2014, ESA 2015, FCT 2015, ICALP 2016, WAOA 2016, CCC 2020, SWAT 2020, SODA 2021.