Per Austrin

According to our database, Per Austrin authored at least 41 papers between 2007 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

On the usefulness of Promises.

Per Austrin, Johan Håstad, Björn Martinsson

Electron. Colloquium Comput. Complex., 2025

Algorithms for the Diverse-k-SAT Problem: The Geometry of Satisfying Assignments.

Per Austrin, Ioana O. Bercea, Mayank Goswami, Nutan Limaye, Adarsh Srinivasan

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

2024

On the geometry of <i>k</i>-SAT solutions: what more can PPZ and Schöning's algorithms do?

Per Austrin, Ioana O. Bercea, Mayank Goswami, Nutan Limaye, Adarsh Srinivasan

CoRR, 2024

2023

Sum-Of-Squares Lower Bounds for the Minimum Circuit Size Problem.

Per Austrin, Kilian Risse

Proceedings of the 38th Computational Complexity Conference, 2023

2022

Perfect Matching in Random Graphs is as Hard as Tseitin.

Per Austrin, Kilian Risse

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

On the Impossibility of Key Agreements from Quantum Random Oracles.

Per Austrin, Hao Chung, Kai-Min Chung, Shiuan Fu, Yao-Ting Lin, Mohammad Mahmoody

Proceedings of the Advances in Cryptology - CRYPTO 2022, 2022

2021

Average-Case Perfect Matching Lower Bounds from Hardness of Tseitin Formulas.

Per Austrin, Kilian Risse

Electron. Colloquium Comput. Complex., 2021

Optimal Inapproximability with Universal Factor Graphs.

Per Austrin, Jonah Brown-Cohen, Johan Håstad

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

2020

Improved Inapproximability of Rainbow Coloring.

Per Austrin, Amey Bhangale, Aditya Potukuchi

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019

Simplified inpproximability of hypergraph coloring via t-agreeing families.

Per Austrin, Amey Bhangale, Aditya Potukuchi

Electron. Colloquium Comput. Complex., 2019

Tensor Network Complexity of Multilinear Maps.

Per Austrin, Petteri Kaski, Kaie Kubjas

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder.

Per Austrin, Aleksa Stankovic

Proceedings of the Approximation, 2019

2016

Dense Subset Sum May Be the Hardest.

Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper Nederlof

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

Sharper upper bounds for unbalanced Uniquely Decodable Code Pairs.

Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper Nederlof

Proceedings of the IEEE International Symposium on Information Theory, 2016

2015

Subset Sum in the Absence of Concentration.

Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper Nederlof

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

Inapproximability of Treewidth and Related Problems (Extended Abstract).

Yu (Ledell) Wu, Per Austrin, Toniann Pitassi, David Liu

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015

2014

New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover.

Per Austrin, Ryan O'Donnell, Li-Yang Tan, John Wright

ACM Trans. Comput. Theory, 2014

Inapproximability of Treewidth and Related Problems.

Yu (Ledell) Wu, Per Austrin, Toniann Pitassi, David Liu

J. Artif. Intell. Res., 2014

(2 + epsilon)-Sat Is NP-Hard.

Per Austrin, Johan Håstad, Venkatesan Guruswami

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

On the Impossibility of Cryptography with Tamperable Randomness.

Per Austrin, Kai-Min Chung, Mohammad Mahmoody, Rafael Pass, Karn Seth

Proceedings of the Advances in Cryptology - CRYPTO 2014, 2014

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

(2+ε)-SAT is NP-hard.

Per Austrin, Venkatesan Guruswami, Johan Håstad

Electron. Colloquium Comput. Complex., 2013

Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection.

Per Austrin, Siavosh Benabbas, Konstantinos Georgiou

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

A characterization of approximation resistance for even k-partite CSPs.

Per Austrin, Subhash Khot

Proceedings of the Innovations in Theoretical Computer Science, 2013

On the power of many one-bit provers.

Per Austrin, Johan Håstad, Rafael Pass

Proceedings of the Innovations in Theoretical Computer Science, 2013

Space-Time Tradeoffs for Subset Sum: An Improved Worst Case Algorithm.

Per Austrin, Petteri Kaski, Mikko Koivisto, Jussi Määttä

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems.

Per Austrin, Rajsekar Manokaran, Cenny Wenner

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

On the Usefulness of Predicates.

Per Austrin, Johan Håstad

Proceedings of the 27th Conference on Computational Complexity, 2012

Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems.

Per Austrin, Toniann Pitassi, Yu Wu

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

A New Point of NP-Hardness for 2-to-1 Label Cover.

Per Austrin, Ryan O'Donnell, John Wright

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem.

Per Austrin, Subhash Khot

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Inapproximability of NP-Complete Variants of Nash Equilibrium.

Per Austrin, Mark Braverman, Eden Chlamtac

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

On Quadratic Threshold CSPs.

Per Austrin, Siavosh Benabbas, Avner Magen

Proceedings of the LATIN 2010: Theoretical Informatics, 2010

Improved Inapproximability for Submodular Maximization.

Per Austrin

Proceedings of the Approximation, 2010

2009

Randomly supported independence and resistance.

Per Austrin, Johan Håstad

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs.

Per Austrin, Subhash Khot, Muli Safra

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008

Conditional Inapproximability and Limited Independence.

Per Austrin

PhD thesis, 2008

Approximation Resistant Predicates from Pairwise Independence.

Per Austrin, Elchanan Mossel

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

Lower Bounds for Subset Cover Based Broadcast Encryption.

Per Austrin, Gunnar Kreitz

Proceedings of the Progress in Cryptology, 2008

2007

Balanced max 2-sat might not be the hardest.

Per Austrin

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Towards Sharp Inapproximability For Any 2-CSP.

Per Austrin

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007