Per Austrin

I am a post-doc at the Department of Computer Science of the University of Toronto. I am very fond of combinatorics and theoretical computer science. My research interests include computational complexity and approximation algorithms.

E-mail	lastname at cs dot toronto dot edu
Address	Department of Computer Science University of Toronto 10 King's College Road Toronto, ON M5S 3G4 Canada
Visiting address	Office 2302B

Committees

I was on the program committee of RANDOM 2011.

Publications

Journal Papers

[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 ]

Conference Papers

[AH12]	Per Austrin and Johan Håstad, On the Usefulness of Predicates, To appear in IEEE Conference on Computational Complexity (CCC), 2012. [ arXiv ]
[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, Accepted for publication in Theory of Computing. [ DOI \| arXiv ]
[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. [ DOI \| pdf ]
[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

[APW11]	Per Austrin, Toniann Pitassi, and Yu Wu, Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems, Manuscript, 2011. [ arXiv ]
[AHP12]	Per Austrin, Johan Håstad, and Rafael Pass, On the power of many one-bit provers, Manuscript, 2012.
[AOW12]	Per Austrin, Ryan O'Donnell, and John Wright, A new point of NP-hardness for 2-to-1 Label Cover, Manuscript, 2012. [ arXiv ]
[ABG12]	Per Austrin, Siavosh Benabbas, and Konstantinos Georgiou, Better Balance by Being Biased: a 0.8776-Approximation for Max Bisection, Manuscript, 2012. [ arXiv ]
[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, In preparation, 2012.

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).