Per Austrin

Publication Activity (10 Years)

Years Active: 2006-2023
Publications (10 Years): 27

Top Topics

Constraint Satisfaction

Top Venues

Electron. Colloquium Comput. Complex.

Publications

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