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.
lastname at csc dot kth dot se 

Phone  +46 (8) 790 62 86 
Address 
KTH CSC Lindstedtsvägen 3 S10044 Stockholm Sweden 
Visiting address  Room 4533 
I am on the program committee of ESA 2015 and FCT 2015. I was on the program committee of RANDOM 2011, STOC 2013, SODA 2014, SWAT 2014.
[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 ] 
[AKKN15]  Per Austrin, Petteri Kaski, Mikko Koivisto, and Jesper Nederlof, The Subset Sum Problem in the Absence of Concentration, To appear in Symposium on Theoretical Aspects of Computer Science (STACS), 2015. 
[AGH14]  Per Austrin, Venkatesan Guruswami, and Johan Håstad, (2+ε)SAT is NPhard, To appear in IEEE Symposium on Foundations of Computer Science (FOCS), 2014. [ ECCC ] 
[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. [ 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. [ 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. [ 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 ] 
[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). 