Per Austrin

According to our database, Per Austrin authored at least 38 papers between 2006 and 2023.

Collaborative distances:

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

2023

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

Per Austrin, Kilian Risse

Electron. Colloquium Comput. Complex., 2023

2022

Tensor Network Complexity of Multilinear Maps.

Per Austrin, Petteri Kaski, Kaie Kubjas

Theory Comput., 2022

Perfect Matching in Random Graphs is as Hard as Tseitin.

Per Austrin, Kilian Risse

TheoretiCS, 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

IACR Cryptol. ePrint Arch., 2022

2021

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

Per Austrin, Kilian Risse

Electron. Colloquium Comput. Complex., 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

Optimal Inapproximability with Universal Factor Graphs.

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

Electron. Colloquium Comput. Complex., 2019

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

Per Austrin, Aleksa Stankovic

Proceedings of the Approximation, 2019

2018

Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs.

Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper Nederlof

IEEE Trans. Inf. Theory, 2018

2017

On the Impossibility of Cryptography with Tamperable Randomness.

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

Algorithmica, 2017

2016

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

Per Austrin, Siavosh Benabbas, Konstantinos Georgiou

ACM Trans. Algorithms, 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

2015

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

Per Austrin, Rajsekar Manokaran, Cenny Wenner

Theory Comput., 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

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

Per Austrin, Subhash Khot

IEEE Trans. Inf. 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

2013

On the usefulness of predicates.

Per Austrin, Johan Håstad

ACM Trans. Comput. Theory, 2013

Inapproximability of NP-Complete Variants of Nash Equilibrium.

Per Austrin, Mark Braverman, Eden Chlamtac

Theory Comput., 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

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

2012

On Quadratic Threshold CSPs.

Per Austrin, Siavosh Benabbas, Avner Magen

Discret. Math. Theor. Comput. Sci., 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

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

Per Austrin, Subhash Khot, Muli Safra

Theory Comput., 2011

Randomly Supported Independence and Resistance.

Per Austrin, Johan Håstad

SIAM J. Comput., 2011

2010

Towards Sharp Inapproximability for Any 2-CSP.

Per Austrin

SIAM J. Comput., 2010

Improved Inapproximability for Submodular Maximization.

Per Austrin

Proceedings of the Approximation, 2010

2009

Approximation Resistant Predicates from Pairwise Independence.

Per Austrin, Elchanan Mossel

Comput. Complex., 2009

2008

Conditional Inapproximability and Limited Independence.

Per Austrin

PhD thesis, 2008

Lower Bounds for Subset Cover Based Broadcast Encryption.

Per Austrin, Gunnar Kreitz

Proceedings of the Progress in Cryptology, 2008

2006

Balanced Max 2-Sat might not be the hardest.

Per Austrin

Electron. Colloquium Comput. Complex., 2006