default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDPer Austrin
Person information
- affiliation: Royal Institute of Technology, Stockholm, Sweden
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
Books and Theses
- 2008
[b1]Per Austrin:
Conditional Inapproximability and Limited Independence. KTH Royal Institute of Technology, Sweden, 2008
Journal Articles
- 2022
- [j17]Per Austrin, Kilian Risse:
Perfect Matching in Random Graphs is as Hard as Tseitin. TheoretiCS 1 (2022) - [j16]Per Austrin, Petteri Kaski, Kaie Kubjas:
Tensor Network Complexity of Multilinear Maps. Theory Comput. 18: 1-54 (2022) - 2018
- [j15]Per Austrin, Petteri Kaski, Mikko Koivisto
, Jesper Nederlof:
Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs. IEEE Trans. Inf. Theory 64(2): 1368-1373 (2018) - 2017
- [j14]Per Austrin, Kai-Min Chung, Mohammad Mahmoody, Rafael Pass, Karn Seth:
On the Impossibility of Cryptography with Tamperable Randomness. Algorithmica 79(4): 1052-1101 (2017) - [j13]Per Austrin, Venkatesan Guruswami, Johan Håstad:
(2+ε)-Sat Is NP-hard. SIAM J. Comput. 46(5): 1554-1573 (2017) - 2016
- [j12]Per Austrin, Siavosh Benabbas, Konstantinos Georgiou:
Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection. ACM Trans. Algorithms 13(1): 2:1-2:27 (2016) - 2015
- [j11]Per Austrin, Rajsekar Manokaran, Cenny Wenner:
On the NP-Hardness of Approximating Ordering-Constraint Satisfaction Problems. Theory Comput. 11: 257-283 (2015) - 2014
- [j10]Yu (Ledell) Wu, Per Austrin, Toniann Pitassi, David Liu:
Inapproximability of Treewidth and Related Problems. J. Artif. Intell. Res. 49: 569-600 (2014) - [j9]Per Austrin, Subhash Khot:
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem. IEEE Trans. Inf. Theory 60(10): 6636-6645 (2014) - [j8]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): 2:1-2:20 (2014) - 2013
- [j7]Per Austrin, Mark Braverman, Eden Chlamtac:
Inapproximability of NP-Complete Variants of Nash Equilibrium. Theory Comput. 9: 117-142 (2013) - [j6]Per Austrin, Johan Håstad:
On the usefulness of predicates. ACM Trans. Comput. Theory 5(1): 1:1-1:24 (2013) - 2012
- [j5]Per Austrin, Siavosh Benabbas, Avner Magen:
On Quadratic Threshold CSPs. Discret. Math. Theor. Comput. Sci. 14(2): 205-228 (2012) - 2011
- [j4]Per Austrin, Johan Håstad:
Randomly Supported Independence and Resistance. SIAM J. Comput. 40(1): 1-27 (2011) - [j3]Per Austrin, Subhash Khot, Muli Safra:
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs. Theory Comput. 7(1): 27-43 (2011) - 2010
- [j2]Per Austrin:
Towards Sharp Inapproximability for Any 2-CSP. SIAM J. Comput. 39(6): 2430-2463 (2010) - 2009
- [j1]Per Austrin, Elchanan Mossel:
Approximation Resistant Predicates from Pairwise Independence. Comput. Complex. 18(2): 249-271 (2009)
Conference and Workshop Papers
- 2023
- [c31]Per Austrin, Kilian Risse:
Sum-Of-Squares Lower Bounds for the Minimum Circuit Size Problem. CCC 2023: 31:1-31:21 - 2022
- [c30]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: 165-194 - [c29]Per Austrin, Kilian Risse:
Perfect Matching in Random Graphs is as Hard as Tseitin. SODA 2022: 979-1012 - 2021
- [c28]Per Austrin, Jonah Brown-Cohen, Johan Håstad:
Optimal Inapproximability with Universal Factor Graphs. SODA 2021: 434-453 - 2020
- [c27]Per Austrin, Amey Bhangale, Aditya Potukuchi:
Improved Inapproximability of Rainbow Coloring. SODA 2020: 1479-1495 - 2019
- [c26]Per Austrin, Aleksa Stankovic:
Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder. APPROX-RANDOM 2019: 24:1-24:17 - [c25]Per Austrin, Petteri Kaski, Kaie Kubjas:
Tensor Network Complexity of Multilinear Maps. ITCS 2019: 7:1-7:21 - 2016
- [c24]Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper Nederlof:
Sharper upper bounds for unbalanced Uniquely Decodable Code Pairs. ISIT 2016: 335-339 - [c23]Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper Nederlof:
Dense Subset Sum May Be the Hardest. STACS 2016: 13:1-13:14 - 2015
- [c22]Yu (Ledell) Wu, Per Austrin, Toniann Pitassi, David Liu:
Inapproximability of Treewidth and Related Problems (Extended Abstract). IJCAI 2015: 4222-4228 - [c21]Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper Nederlof:
Subset Sum in the Absence of Concentration. STACS 2015: 48-61 - 2014
- [c20]Per Austrin, Kai-Min Chung, Mohammad Mahmoody, Rafael Pass, Karn Seth:
On the Impossibility of Cryptography with Tamperable Randomness. CRYPTO (1) 2014: 462-479 - [c19]Per Austrin, Johan Håstad, Venkatesan Guruswami:
(2 + epsilon)-Sat Is NP-Hard. FOCS 2014: 1-10 - 2013
- [c18]Per Austrin, Rajsekar Manokaran, Cenny Wenner:
On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems. APPROX-RANDOM 2013: 26-41 - [c17]Per Austrin, Petteri Kaski, Mikko Koivisto, Jussi Määttä:
Space-Time Tradeoffs for Subset Sum: An Improved Worst Case Algorithm. ICALP (1) 2013: 45-56 - [c16]Per Austrin, Subhash Khot:
A characterization of approximation resistance for even k-partite CSPs. ITCS 2013: 187-196 - [c15]Per Austrin, Johan Håstad, Rafael Pass:
On the power of many one-bit provers. ITCS 2013: 215-220 - [c14]Per Austrin, Siavosh Benabbas, Konstantinos Georgiou:
Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection. SODA 2013: 277-294 - 2012
- [c13]Per Austrin, Ryan O'Donnell, John Wright:
A New Point of NP-Hardness for 2-to-1 Label Cover. APPROX-RANDOM 2012: 1-12 - [c12]Per Austrin, Toniann Pitassi, Yu Wu:
Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems. APPROX-RANDOM 2012: 13-24 - [c11]Per Austrin, Johan Håstad:
On the Usefulness of Predicates. CCC 2012: 53-63 - 2011
- [c10]Per Austrin, Mark Braverman, Eden Chlamtac:
Inapproximability of NP-Complete Variants of Nash Equilibrium. APPROX-RANDOM 2011: 13-25 - [c9]Per Austrin, Subhash Khot:
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem. ICALP (1) 2011: 474-485 - 2010
- [c8]Per Austrin:
Improved Inapproximability for Submodular Maximization. APPROX-RANDOM 2010: 12-24 - [c7]Per Austrin, Siavosh Benabbas, Avner Magen:
On Quadratic Threshold CSPs. LATIN 2010: 332-343 - 2009
- [c6]Per Austrin, Subhash Khot, Muli Safra:
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs. CCC 2009: 74-80 - [c5]Per Austrin, Johan Håstad:
Randomly supported independence and resistance. STOC 2009: 483-492 - 2008
- [c4]Per Austrin, Gunnar Kreitz:
Lower Bounds for Subset Cover Based Broadcast Encryption. AFRICACRYPT 2008: 343-356 - [c3]Per Austrin, Elchanan Mossel:
Approximation Resistant Predicates from Pairwise Independence. CCC 2008: 249-258 - 2007
- [c2]Per Austrin:
Towards Sharp Inapproximability For Any 2-CSP. FOCS 2007: 307-317 - [c1]Per Austrin:
Balanced max 2-sat might not be the hardest. STOC 2007: 189-197
Informal and Other Publications
- 2024
- [i31]Per Austrin, Ioana O. Bercea, Mayank Goswami, Nutan Limaye, Adarsh Srinivasan:
On the geometry of k-SAT solutions: what more can PPZ and Schöning's algorithms do? CoRR abs/2408.03465 (2024) - 2023
- [i30]Per Austrin, Kilian Risse:
Sum-of-Squares Lower Bounds for the Minimum Circuit Size Problem. CoRR abs/2311.12994 (2023) - [i29]Per Austrin, Kilian Risse:
Sum-of-Squares Lower Bounds for the Minimum Circuit Size Problem. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [i28]Per Austrin, Kilian Risse:
Perfect Matching in Random Graphs is as Hard as Tseitin. CoRR abs/2201.10835 (2022) - [i27]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: 218 (2022) - 2021
- [i26]Per Austrin, Kilian Risse:
Average-Case Perfect Matching Lower Bounds from Hardness of Tseitin Formulas. Electron. Colloquium Comput. Complex. TR21 (2021) - 2019
- [i25]Per Austrin, Amey Bhangale, Aditya Potukuchi:
Simplified inpproximability of hypergraph coloring via t-agreeing families. CoRR abs/1904.01163 (2019) - [i24]Per Austrin, Aleksa Stankovic:
Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder. CoRR abs/1907.04165 (2019) - [i23]Per Austrin, Jonah Brown-Cohen, Johan Håstad:
Optimal Inapproximability with Universal Factor Graphs. Electron. Colloquium Comput. Complex. TR19 (2019) - [i22]Per Austrin, Amey Bhangale, Aditya Potukuchi:
Simplified inpproximability of hypergraph coloring via t-agreeing families. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [i21]Per Austrin, Amey Bhangale, Aditya Potukuchi:
Improved Inapproximability of Rainbow Coloring. CoRR abs/1810.02784 (2018) - 2017
- [i20]Per Austrin, Petteri Kaski, Kaie Kubjas:
Tensor network complexity of multilinear maps. CoRR abs/1712.09630 (2017) - 2016
- [i19]Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper Nederlof:
Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs. CoRR abs/1605.00462 (2016) - 2015
- [i18]Per Austrin, Mikko Koivisto, Petteri Kaski, Jesper Nederlof:
Dense Subset Sum may be the hardest. CoRR abs/1508.06019 (2015) - 2013
- [i17]Per Austrin, Johan Håstad, Rafael Pass:
On the Power of Many One-Bit Provers. CoRR abs/1301.2729 (2013) - [i16]Per Austrin, Subhash Khot:
A Characterization of Approximation Resistance for Even $k$-Partite CSPs. CoRR abs/1301.2731 (2013) - [i15]Per Austrin, Petteri Kaski, Mikko Koivisto, Jussi Määttä:
Space--Time Tradeoffs for Subset Sum: An Improved Worst Case Algorithm. CoRR abs/1303.0609 (2013) - [i14]Per Austrin, Rajsekar Manokaran, Cenny Wenner:
On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems. CoRR abs/1307.5090 (2013) - [i13]Per Austrin, Venkatesan Guruswami, Johan Håstad:
(2+ε)-SAT is NP-hard. Electron. Colloquium Comput. Complex. TR13 (2013) - [i12]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: 194 (2013) - 2012
- [i11]Per Austrin, Johan Håstad:
On the Usefulness of Predicates. CoRR abs/1204.5662 (2012) - [i10]Per Austrin, Ryan O'Donnell, John Wright:
A new point of NP-hardness for 2-to-1 Label Cover. CoRR abs/1204.5666 (2012) - [i9]Per Austrin, Siavosh Benabbas, Konstantinos Georgiou:
Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection. CoRR abs/1205.0458 (2012) - [i8]Per Austrin, Ryan O'Donnell, Li-Yang Tan, John Wright:
New NP-hardness results for 3-Coloring and 2-to-1 Label Cover. CoRR abs/1210.5648 (2012) - 2011
- [i7]Per Austrin, Mark Braverman, Eden Chlamtac:
Inapproximability of NP-Complete Variants of Nash Equilibrium. CoRR abs/1104.3760 (2011) - [i6]Per Austrin, Toniann Pitassi, Yu Wu:
Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems. CoRR abs/1109.4910 (2011) - 2010
- [i5]Per Austrin:
Improved Inapproximability For Submodular Maximization. CoRR abs/1004.3777 (2010) - [i4]Per Austrin, Subhash Khot:
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem. CoRR abs/1010.1481 (2010) - 2008
- [i3]Per Austrin, Elchanan Mossel:
Approximation Resistant Predicates From Pairwise Independence. CoRR abs/0802.2300 (2008) - [i2]Per Austrin, Elchanan Mossel:
Approximation Resistant Predicates From Pairwise Independence. Electron. Colloquium Comput. Complex. TR08 (2008) - 2006
- [i1]Per Austrin:
Balanced Max 2-Sat might not be the hardest. Electron. Colloquium Comput. Complex. TR06 (2006)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-09-18 01:10 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
