Per Austrin

85 papers A* 11A 9B 2Journal 51Unranked 11
YearRankTypeTitle / Venue / Authors
2026 A* conf
On the Usefulness of Promises.
SODA
Per Austrin, Johan Håstad, Björn Martinsson
2025 A* conf
Algorithms for the Diverse-k-SAT Problem: The Geometry of Satisfying Assignments.
ICALP
Per Austrin, Ioana O. Bercea, Mayank Goswami, Nutan Limaye, Adarsh Srinivasan
2025 J jnl
On the Usefulness of Promises.
CoRR
Per Austrin, Johan Håstad, Björn Martinsson
2025 J jnl
On the usefulness of Promises.
Electron. Colloquium Comput. Complex.
Per Austrin, Johan Håstad, Björn Martinsson
2025 J jnl
Optimal Inapproximability with Universal Factor Graphs.
ACM Trans. Algorithms
Per Austrin, Jonah Brown-Cohen, Johan Håstad
2024 J jnl
On the geometry of
CoRR
Per Austrin, Ioana O. Bercea, Mayank Goswami, Nutan Limaye, Adarsh Srinivasan
2023 A conf
Sum-Of-Squares Lower Bounds for the Minimum Circuit Size Problem.
CCC
Per Austrin, Kilian Risse
2023 J jnl
Sum-of-Squares Lower Bounds for the Minimum Circuit Size Problem.
CoRR
Per Austrin, Kilian Risse
2023 J jnl
Sum-of-Squares Lower Bounds for the Minimum Circuit Size Problem.
Electron. Colloquium Comput. Complex.
Per Austrin, Kilian Risse
2022 — conf
On the Impossibility of Key Agreements from Quantum Random Oracles.
CRYPTO (2)
Per Austrin, Hao Chung, Kai-Min Chung, Shiuan Fu, Yao-Ting Lin, Mohammad Mahmoody
2022 J jnl
On the Impossibility of Key Agreements from Quantum Random Oracles.
IACR Cryptol. ePrint Arch.
Per Austrin, Hao Chung, Kai-Min Chung, Shiuan Fu, Yao-Ting Lin, Mohammad Mahmoody
2022 A* conf
Perfect Matching in Random Graphs is as Hard as Tseitin.
SODA
Per Austrin, Kilian Risse
2022 J jnl
Perfect Matching in Random Graphs is as Hard as Tseitin.
CoRR
Per Austrin, Kilian Risse
2022 J jnl
Perfect Matching in Random Graphs is as Hard as Tseitin.
TheoretiCS
Per Austrin, Kilian Risse
2022 J jnl
Tensor Network Complexity of Multilinear Maps.
Theory Comput.
Per Austrin, Petteri Kaski, Kaie Kubjas
2021 J jnl
Average-Case Perfect Matching Lower Bounds from Hardness of Tseitin Formulas.
Electron. Colloquium Comput. Complex.
Per Austrin, Kilian Risse
2021 A* conf
Optimal Inapproximability with Universal Factor Graphs.
SODA
Per Austrin, Jonah Brown-Cohen, Johan Håstad
2020 A* conf
Improved Inapproximability of Rainbow Coloring.
SODA
Per Austrin, Amey Bhangale, Aditya Potukuchi
2019 — conf
Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder.
APPROX-RANDOM
Per Austrin, Aleksa Stankovic
2019 J jnl
Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder.
CoRR
Per Austrin, Aleksa Stankovic
2019 J jnl
Optimal Inapproximability with Universal Factor Graphs.
Electron. Colloquium Comput. Complex.
Per Austrin, Jonah Brown-Cohen, Johan Håstad
2019 J jnl
Simplified inpproximability of hypergraph coloring via t-agreeing families.
CoRR
Per Austrin, Amey Bhangale, Aditya Potukuchi
2019 J jnl
Simplified inpproximability of hypergraph coloring via t-agreeing families.
Electron. Colloquium Comput. Complex.
Per Austrin, Amey Bhangale, Aditya Potukuchi
2019 A conf
Tensor Network Complexity of Multilinear Maps.
ITCS
Per Austrin, Petteri Kaski, Kaie Kubjas
2018 J jnl
Improved Inapproximability of Rainbow Coloring.
CoRR
Per Austrin, Amey Bhangale, Aditya Potukuchi
2018 J jnl
Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs.
IEEE Trans. Inf. Theory
Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper Nederlof
2017 J jnl
(2+ε)-Sat Is NP-hard.
SIAM J. Comput.
Per Austrin, Venkatesan Guruswami, Johan Håstad
2017 J jnl
On the Impossibility of Cryptography with Tamperable Randomness.
Algorithmica
Per Austrin, Kai-Min Chung, Mohammad Mahmoody, Rafael Pass, Karn Seth
2017 J jnl
Tensor network complexity of multilinear maps.
CoRR
Per Austrin, Petteri Kaski, Kaie Kubjas
2016 J jnl
Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection.
ACM Trans. Algorithms
Per Austrin, Siavosh Benabbas, Konstantinos Georgiou
2016 A conf
Dense Subset Sum May Be the Hardest.
STACS
Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper Nederlof
2016 J jnl
Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs.
CoRR
Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper Nederlof
2016 B conf
Sharper upper bounds for unbalanced Uniquely Decodable Code Pairs.
ISIT
Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper Nederlof
2015 J jnl
Dense Subset Sum may be the hardest.
CoRR
Per Austrin, Mikko Koivisto, Petteri Kaski, Jesper Nederlof
2015 A* conf
Inapproximability of Treewidth and Related Problems (Extended Abstract).
IJCAI
Yu (Ledell) Wu, Per Austrin, Toniann Pitassi, David Liu
2015 J jnl
On the NP-Hardness of Approximating Ordering-Constraint Satisfaction Problems.
Theory Comput.
Per Austrin, Rajsekar Manokaran, Cenny Wenner
2015 A conf
Subset Sum in the Absence of Concentration.
STACS
Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper Nederlof
2014 A* conf
(2 + epsilon)-Sat Is NP-Hard.
FOCS
Per Austrin, Johan Håstad, Venkatesan Guruswami
2014 J jnl
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem.
IEEE Trans. Inf. Theory
Per Austrin, Subhash Khot
2014 J jnl
Inapproximability of Treewidth and Related Problems.
J. Artif. Intell. Res.
Yu (Ledell) Wu, Per Austrin, Toniann Pitassi, David Liu
2014 J jnl
New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover.
ACM Trans. Comput. Theory
Per Austrin, Ryan O'Donnell, Li-Yang Tan, John Wright
2014 — conf
On the Impossibility of Cryptography with Tamperable Randomness.
CRYPTO (1)
Per Austrin, Kai-Min Chung, Mohammad Mahmoody, Rafael Pass, Karn Seth
2013 J jnl
(2+ε)-SAT is NP-hard.
Electron. Colloquium Comput. Complex.
Per Austrin, Venkatesan Guruswami, Johan Håstad
2013 J jnl
A Characterization of Approximation Resistance for Even $k$-Partite CSPs
CoRR
Per Austrin, Subhash Khot
2013 A conf
A characterization of approximation resistance for even k-partite CSPs.
ITCS
Per Austrin, Subhash Khot
2013 A* conf
Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection.
SODA
Per Austrin, Siavosh Benabbas, Konstantinos Georgiou
2013 J jnl
Inapproximability of NP-Complete Variants of Nash Equilibrium.
Theory Comput.
Per Austrin, Mark Braverman, Eden Chlamtac
2013 J jnl
On the (Im)Possibility of Tamper-Resilient Cryptography: Using Fourier Analysis in Computer Viruses.
IACR Cryptol. ePrint Arch.
Per Austrin, Kai-Min Chung, Mohammad Mahmoody, Rafael Pass, Karn Seth
2013 — conf
On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems.
APPROX-RANDOM
Per Austrin, Rajsekar Manokaran, Cenny Wenner
2013 J jnl
On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems.
CoRR
Per Austrin, Rajsekar Manokaran, Cenny Wenner
2013 J jnl
On the Power of Many One-Bit Provers
CoRR
Per Austrin, Johan Håstad, Rafael Pass
2013 A conf
On the power of many one-bit provers.
ITCS
Per Austrin, Johan Håstad, Rafael Pass
2013 J jnl
On the usefulness of predicates.
ACM Trans. Comput. Theory
Per Austrin, Johan Håstad
2013 J jnl
Space--Time Tradeoffs for Subset Sum: An Improved Worst Case Algorithm
CoRR
Per Austrin, Petteri Kaski, Mikko Koivisto, Jussi Määttä
2013 — conf
Space-Time Tradeoffs for Subset Sum: An Improved Worst Case Algorithm.
ICALP (1)
Per Austrin, Petteri Kaski, Mikko Koivisto, Jussi Määttä
2012 — conf
A New Point of NP-Hardness for 2-to-1 Label Cover.
APPROX-RANDOM
Per Austrin, Ryan O'Donnell, John Wright
2012 J jnl
A new point of NP-hardness for 2-to-1 Label Cover
CoRR
Per Austrin, Ryan O'Donnell, John Wright
2012 J jnl
Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection
CoRR
Per Austrin, Siavosh Benabbas, Konstantinos Georgiou
2012 — conf
Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems.
APPROX-RANDOM
Per Austrin, Toniann Pitassi, Yu Wu
2012 J jnl
New NP-hardness results for 3-Coloring and 2-to-1 Label Cover
CoRR
Per Austrin, Ryan O'Donnell, Li-Yang Tan, John Wright
2012 J jnl
On Quadratic Threshold CSPs.
Discret. Math. Theor. Comput. Sci.
Per Austrin, Siavosh Benabbas, Avner Magen
2012 J jnl
On the Usefulness of Predicates
CoRR
Per Austrin, Johan Håstad
2012 A conf
On the Usefulness of Predicates.
CCC
Per Austrin, Johan Håstad
2011 — conf
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem.
ICALP (1)
Per Austrin, Subhash Khot
2011 J jnl
Inapproximability of NP-Complete Variants of Nash Equilibrium
CoRR
Per Austrin, Mark Braverman, Eden Chlamtac
2011 — conf
Inapproximability of NP-Complete Variants of Nash Equilibrium.
APPROX-RANDOM
Per Austrin, Mark Braverman, Eden Chlamtac
2011 J jnl
Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems
CoRR
Per Austrin, Toniann Pitassi, Yu Wu
2011 J jnl
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs.
Theory Comput.
Per Austrin, Subhash Khot, Muli Safra
2011 J jnl
Randomly Supported Independence and Resistance.
SIAM J. Comput.
Per Austrin, Johan Håstad
2010 J jnl
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem
CoRR
Per Austrin, Subhash Khot
2010 J jnl
Improved Inapproximability For Submodular Maximization
CoRR
Per Austrin
2010 — conf
Improved Inapproximability for Submodular Maximization.
APPROX-RANDOM
Per Austrin
2010 B conf
On Quadratic Threshold CSPs.
LATIN
Per Austrin, Siavosh Benabbas, Avner Magen
2010 J jnl
Towards Sharp Inapproximability for Any 2-CSP.
SIAM J. Comput.
Per Austrin
2009 J jnl
Approximation Resistant Predicates from Pairwise Independence.
Comput. Complex.
Per Austrin, Elchanan Mossel
2009 A conf
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs.
CCC
Per Austrin, Subhash Khot, Muli Safra
2009 A* conf
Randomly supported independence and resistance.
STOC
Per Austrin, Johan Håstad
2008 J jnl
Approximation Resistant Predicates From Pairwise Independence
CoRR
Per Austrin, Elchanan Mossel
2008 J jnl
Approximation Resistant Predicates From Pairwise Independence.
Electron. Colloquium Comput. Complex.
Per Austrin, Elchanan Mossel
2008 A conf
Approximation Resistant Predicates from Pairwise Independence.
CCC
Per Austrin, Elchanan Mossel
2008 — —
Conditional Inapproximability and Limited Independence.
Per Austrin
2008 — conf
Lower Bounds for Subset Cover Based Broadcast Encryption.
AFRICACRYPT
Per Austrin, Gunnar Kreitz
2007 A* conf
Balanced max 2-sat might not be the hardest.
STOC
Per Austrin
2007 A* conf
Towards Sharp Inapproximability For Any 2-CSP.
FOCS
Per Austrin
2006 J jnl
Balanced Max 2-Sat might not be the hardest.
Electron. Colloquium Comput. Complex.
Per Austrin