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 S10044 Stockholm Sweden 
Visiting address  Room 4533 
[AR22]  Per Austrin and Kilian Risse, Perfect Matching in Random Graphs is as Hard as Tseitin, TheoretiCS, vol. 1, 2022. [ DOI  http ] 
[AKK22]  Per Austrin, Petteri Kaski, and Kaie Kubjas, Tensor Network Complexity of Multilinear Maps, Theory of Computing, vol. 18, no. 16, pp. 154, 2022. [ DOI  http ] 
[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. 13681373, 2018. [ DOI  http ] 
[ACMPS17]  Per Austrin, KaiMin Chung, Mohammad Mahmoody, Rafael Pass, and Karn Seth, On the Impossibility of Cryptography with Tamperable Randomness, Algorithmica, vol. 79, no. 4, pp. 10521101, 2017. [ DOI  http ] 
[AGH17]  Per Austrin, Venkatesan Guruswami, and Johan Håstad, (2+ε)sat is NPhard, SIAM Journal on Computing, vol. 46, no. 5, pp. 15541573, 2017. [ DOI  http ] 
[ABG16]  Per Austrin, Siavosh Benabbas, and Konstantinos Georgiou, Better Balance by Being Biased: A 0.8776Approximation for Max Bisection, ACM Transactions on Algorithms, vol. 13, no. 1, pp. 2:12:27, 2016. [ DOI  http ] 
[AMW15]  Per Austrin, Rajsekar Manokaran, and Cenny Wenner, On the NPHardness of Approximating OrderingConstraint Satisfaction Problems, Theory of Computing, vol. 11, pp. 257283, 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. 66366645, 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. 569600, 2014. [ DOI  arXiv ] 
[AOTW14]  Per Austrin, Ryan O'Donnell, LiYang Tan, and John Wright, New NPHardness Results for 3Coloring and 2to1 Label Cover, ACM Transactions on Computation Theory, vol. 6, no. 1, pp. 2:12: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. 124, 2013. [ DOI  arXiv ] 
[ABC13]  Per Austrin, Mark Braverman, and Eden Chlamtáč, Inapproximability of NPComplete Variants of Nash Equilibrium, Theory of Computing, vol. 9, no. 3, pp. 117142, 2013. [ DOI ] 
[ABM12]  Per Austrin, Siavosh Benabbas, and Avner Magen, On Quadratic Threshold CSPs, Discrete Mathematics & Theoretical Computer Science, vol. 14, no. 2, pp. 205228, 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. 2952, 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. 2743, 2011. [ DOI  pdf ] 
[AH11]  Per Austrin and Johan Håstad, Randomly Supported Independence and Resistance, SIAM Journal on Computing, vol. 40, no. 1, pp. 127, 2011. [ DOI  pdf ] 
[Aus10]  Per Austrin, Towards Sharp Inapproximability for Any 2CSP, SIAM Journal on Computing, vol. 39, no. 6, pp. 24302463, 2010. [ DOI  pdf ] 
[AM09]  Per Austrin and Elchanan Mossel, Approximation Resistant Predicates from Pairwise Independence, Computational Complexity, vol. 18, no. 2, pp. 249271, 2009. [ DOI  pdf ] 
[AR23]  Per Austrin and Kilian Risse, SumOfSquares Lower Bounds for the Minimum Circuit Size Problem, in 38th Computational Complexity Conference (CCC), Amnon TaShma, Ed. 2023, vol. 264 of LIPIcs, pp. 31:131:21, Schloss Dagstuhl  LeibnizZentrum für Informatik. [ DOI  http ] 
[ACCFLM22]  Per Austrin, Hao Chung, KaiMin Chung, Shiuan Fu, YaoTing Lin, and Mohammad Mahmoody, On the Impossibility of Key Agreements from Quantum Random Oracles, in CRYPTO, 2022. 
[AR22]  Per Austrin and Kilian Risse, Perfect Matching in Random Graphs is as Hard as Tseitin, in ACMSIAM Symposium on Discrete Algorithms (SODA), Joseph (Seffi) Naor and Niv Buchbinder, Eds. 2022, pp. 9791012, SIAM. [ DOI  http ] 
[ABH21]  Per Austrin, Jonah BrownCohen, and Johan Håstad, Optimal inapproximability with universal factor graphs, in ACMSIAM Symposium on Discrete Algorithms (SODA), Dániel Marx, Ed. 2021, pp. 434453, SIAM. [ DOI  http ] 
[ABP20]  Per Austrin, Amey Bhangale, and Aditya Potukuchi, Improved inapproximability of rainbow coloring, in ACMSIAM Symposium on Discrete Algorithms (SODA), 2020, pp. 14791495. [ DOI  http ] 
[AS19]  Per Austrin and Aleksa Stanković, Global cardinality constraints make approximating some max2csps harder, in International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2019, pp. 24:124: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:17: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. 335339, 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:113: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. 4861. [ DOI  http ] 
[AGH14]  Per Austrin, Venkatesan Guruswami, and Johan Håstad, (2+ε)SAT Is NPHard, in IEEE Annual Symposium on Foundations of Computer Science, FOCS, 2014, pp. 110, Note: Superseded by journal version: [AGH17] . [ DOI  http ] 
[ACMPS14]  Per Austrin, KaiMin Chung, Mohammad Mahmoody, Rafael Pass, and Karn Seth, On the impossibility of cryptography with tamperable randomness, in Advances in Cryptology (CRYPTO), 2014, pp. 462479, Note: Superseded by journal version: [ACMPS17] . [ DOI  pdf ] 
[AMW13]  Per Austrin, Rajsekar Manokaran, and Cenny Wenner, On the NPHardness of Approximating Ordering Constraint Satisfaction Problems, in International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2013, pp. 2641, Note: Superseded by journal version: [AMW15] . [ arXiv ] 
[AKKM13]  Per Austrin, Petteri Kaski, Mikko Koivisto, and Jussi Määttä, SpaceTime Tradeoffs for Subset Sum: An Improved Worst Case Algorithm, in International Colloquium on Automata, Languages and Programming (ICALP), 2013, pp. 4556. [ arXiv ] 
[AHP13]  Per Austrin, Johan Håstad, and Rafael Pass, On the power of many onebit provers, in Innovations in Theoretical Computer Science (ITCS), 2013, pp. 215220. [ DOI  arXiv ] 
[AK13]  Per Austrin and Subhash Khot, A Characterization of Approximation Resistance for Even kPartite CSPs, in Innovations in Theoretical Computer Science (ITCS), 2013, pp. 187196. [ DOI  arXiv ] 
[ABG13]  Per Austrin, Siavosh Benabbas, and Konstantinos Georgiou, Better Balance by Being Biased: a 0.8776Approximation for Max Bisection, in ACMSIAM Symposium on Discrete Algorithms (SODA), 2013, pp. 277294, Note: Superseded by journal version: [ABG16] . [ arXiv ] 
[AOW12]  Per Austrin, Ryan O'Donnell, and John Wright, A New Point of NPHardness for 2to1 Label Cover, in International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2012, pp. 112, Note: Superseded by journal version: [AOTW14] (Contains additional results). 
[APW12]  Per Austrin, Toniann Pitassi, and Yu Wu, Inapproximability of Treewidth, OneShot Pebbling, and Related Layout Problems, in International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2012, pp. 1324, 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. 5363, Note: Superseded by journal version: [AH13] . 
[ABC11]  Per Austrin, Mark Braverman, and Eden Chlamtáč, Inapproximability of NPComplete Variants of Nash Equilibrium, in International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2011, pp. 1325, 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. 474485, 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. 1224. [ DOI  arXiv ] 
[ABM10]  Per Austrin, Siavosh Benabbas, and Avner Magen, On Quadratic Threshold CSPs, in Latin American Theoretical Informatics Symposium (LATIN), 2010, pp. 332343, 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. 7480, 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. 483492, 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. 249258, 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. 343356. [ DOI  pdf ] 
[Aus07b]  Per Austrin, Towards Sharp Inapproximability For Any 2CSP, in IEEE Symposium on Foundations of Computer Science (FOCS), 2007, pp. 307317, Note: Superseded by journal version: [Aus10] . 
[Aus07a]  Per Austrin, Balanced Max 2Sat Might Not be the Hardest, in ACM Symposium on Theory of Computing (STOC), 2007, pp. 189197. [ DOI  pdf  ECCC ] 
[ABP19]  Per Austrin, Amey Bhangale, and Aditya Potukuchi, Simplified inpproximability of hypergraph coloring via tagreeing families, Electron. Colloquium Comput. Complex., vol. 26, pp. 48, 2019. [ arXiv  http ] 
[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). 
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.