Per Austrin

(This is a personal homepage.)

I am a researcher 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. I received my PhD in November 2008.

I am also involved in the KTH programming contest activities.

Publications

• Per Austrin, Subhash Khot and Muli Safra: Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs.
  Extended abstract in IEEE Conference on Computational Complexity (CCC) 2009.
  Preliminary full version.
  
• Per Austrin and Johan Håstad: Randomly Supported Independence and Resistance.
  Extended abstract in ACM Symposium on Theory of Computing (STOC) 2009.
  Preliminary full version.
  
• Per Austrin and Elchanan Mossel: Noise Correlation Bounds for Uniform Low Degree Polynomials
  Preprint available as arXiv report 0904.0157.
• Per Austrin: Conditional Inapproximability and Limited Independence.
  PhD Thesis, KTH - Royal Institute of Technology, 2008.
  PDF version. Some errata.
• Per Austrin, Elchanan Mossel: Approximation Resistant Predicates From Pairwise Independence.
  Extended abstract in IEEE Conference on Computational Complexity (CCC) 2008.
  Preliminary full version.
  
• Per Austrin, Gunnar Kreitz: Lower Bounds for Subset Cover Based Broadcast Encryption.
  Published in LNCS 5023 (pp. 343-356), Proceedings of Africacrypt 2008.
  Full version.
• Per Austrin: Towards Sharp Inapproximability For Any 2-CSP.
  Extended abstract in IEEE Symposium on Foundations of Computer Science (FOCS) 2007.
  Preliminary full version.
• Per Austrin: Balanced Max 2-Sat might not be the hardest.
  Extended abstract in ACM Symposium on Theory of Computing (STOC) 2007.
  Preliminary version available as ECCC Report TR06-88.