Balanced Max 2-Sat might not be the hardest. - Per Austrin (Electron. Colloquium Comput. Complex., 2006)

Lower Bounds for Subset Cover Based Broadcast Encryption. - Per Austrin; Gunnar Kreitz (AFRICACRYPT, 2008)

Conditional Inapproximability and Limited Independence. - Per Austrin (2008)

Approximation Resistant Predicates from Pairwise Independence. - Per Austrin; Elchanan Mossel (Comput. Complex., 2009)

Improved Inapproximability for Submodular Maximization. - Per Austrin (APPROX-RANDOM, 2010)

Towards Sharp Inapproximability for Any 2-CSP. - Per Austrin (SIAM J. Comput., 2010)

Randomly Supported Independence and Resistance. - Per Austrin; Johan Håstad (SIAM J. Comput., 2011)

Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs. - Per Austrin; Subhash Khot; Muli Safra (Theory Comput., 2011)

A New Point of NP-Hardness for 2-to-1 Label Cover. - Per Austrin; Ryan O'Donnell; John Wright 004 (APPROX-RANDOM, 2012)

Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems. - Per Austrin; Toniann Pitassi; Yu Wu (APPROX-RANDOM, 2012)

On Quadratic Threshold CSPs. - Per Austrin; Siavosh Benabbas; Avner Magen (Discret. Math. Theor. Comput. Sci., 2012)

Space-Time Tradeoffs for Subset Sum: An Improved Worst Case Algorithm. - Per Austrin; Petteri Kaski; Mikko Koivisto; Jussi Määttä (ICALP (1), 2013)

On the power of many one-bit provers. - Per Austrin; Johan Håstad; Rafael Pass (ITCS, 2013)

A characterization of approximation resistance for even k-partite CSPs. - Per Austrin; Subhash Khot (ITCS, 2013)

On the (Im)Possibility of Tamper-Resilient Cryptography: Using Fourier Analysis in Computer Viruses. - Per Austrin; Kai-Min Chung; Mohammad Mahmoody; Rafael Pass; Karn Seth (IACR Cryptol. ePrint Arch., 2013)

Inapproximability of NP-Complete Variants of Nash Equilibrium. - Per Austrin; Mark Braverman; Eden Chlamtac (Theory Comput., 2013)

On the usefulness of predicates. - Per Austrin; Johan Håstad (ACM Trans. Comput. Theory, 2013)

(2 + epsilon)-Sat Is NP-Hard. - Per Austrin; Johan Håstad; Venkatesan Guruswami (FOCS, 2014)

Inapproximability of Treewidth and Related Problems. - Yu (Ledell) Wu; Per Austrin; Toniann Pitassi; David Liu 003 (J. Artif. Intell. Res., 2014)

A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem. - Per Austrin; Subhash Khot (IEEE Trans. Inf. Theory, 2014)

New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover. - Per Austrin; Ryan O'Donnell; Li-Yang Tan; John Wright 004 (ACM Trans. Comput. Theory, 2014)

Inapproximability of Treewidth and Related Problems (Extended Abstract). - Yu (Ledell) Wu; Per Austrin; Toniann Pitassi; David Liu 003 (IJCAI, 2015)

Subset Sum in the Absence of Concentration. - Per Austrin; Petteri Kaski; Mikko Koivisto; Jesper Nederlof (STACS, 2015)

On the NP-Hardness of Approximating Ordering-Constraint Satisfaction Problems. - Per Austrin; Rajsekar Manokaran; Cenny Wenner (Theory Comput., 2015)

Dense Subset Sum May Be the Hardest. - Per Austrin; Petteri Kaski; Mikko Koivisto; Jesper Nederlof (STACS, 2016)

Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection. - Per Austrin; Siavosh Benabbas; Konstantinos Georgiou (ACM Trans. Algorithms, 2016)

On the Impossibility of Cryptography with Tamperable Randomness. - Per Austrin; Kai-Min Chung; Mohammad Mahmoody; Rafael Pass; Karn Seth (Algorithmica, 2017)

(2+ε)-Sat Is NP-hard. - Per Austrin; Venkatesan Guruswami; Johan Håstad (SIAM J. Comput., 2017)

Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs. - Per Austrin; Petteri Kaski; Mikko Koivisto; Jesper Nederlof (IEEE Trans. Inf. Theory, 2018)

Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder. - Per Austrin; Aleksa Stankovic (APPROX-RANDOM, 2019)

Optimal Inapproximability with Universal Factor Graphs. - Per Austrin; Jonah Brown-Cohen; Johan Håstad (Electron. Colloquium Comput. Complex., 2019)

Simplified inpproximability of hypergraph coloring via t-agreeing families. - Per Austrin; Amey Bhangale; Aditya Potukuchi (Electron. Colloquium Comput. Complex., 2019)

Improved Inapproximability of Rainbow Coloring. - Per Austrin; Amey Bhangale; Aditya Potukuchi (SODA, 2020)

Average-Case Perfect Matching Lower Bounds from Hardness of Tseitin Formulas. - Per Austrin; Kilian Risse (Electron. Colloquium Comput. Complex., 2021)

On the Impossibility of Key Agreements from Quantum Random Oracles. - Per Austrin; Hao Chung; Kai-Min Chung; Shiuan Fu; Yao-Ting Lin; Mohammad Mahmoody (IACR Cryptol. ePrint Arch., 2022)

Perfect Matching in Random Graphs is as Hard as Tseitin. - Per Austrin; Kilian Risse (TheoretiCS, 2022)

Tensor Network Complexity of Multilinear Maps. - Per Austrin; Petteri Kaski; Kaie Kubjas (Adv. Math. Commun., 2022)

Sum-of-Squares Lower Bounds for the Minimum Circuit Size Problem. - Per Austrin; Kilian Risse (Electron. Colloquium Comput. Complex., 2023)

On the geometry of k-SAT solutions: what more can PPZ and Schöning's algorithms do? - Per Austrin; Ioana O. Bercea; Mayank Goswami 001; Nutan Limaye; Adarsh Srinivasan (CoRR, 2024)

Algorithms for the Diverse-k-SAT Problem: The Geometry of Satisfying Assignments. - Per Austrin; Ioana O. Bercea; Mayank Goswami 001; Nutan Limaye; Adarsh Srinivasan (ICALP, 2025)

On the usefulness of Promises. - Per Austrin; Johan Håstad; Björn Martinsson (Electron. Colloquium Comput. Complex., 2025)