Publications

[Extracted from DiVA, the publication database at KTH.]

Austrin, P.; Brown-Cohen, J.; Håstad, J. (2021):
Optimal inapproximability with universal factor graphs.
[Conference paper] 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, 10 January 2021 through 13 January 2021, Alexandria, Virtual; Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms 434-453 [Details]
Austrin, P.; Bhangale, A.; Potukuchi, A. (2020):
Improved Inapproximability of Rainbow Coloring.
[Conference paper] 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020.; Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 1479-1495 [Details]
Austrin, P.; Stanković, A. (2019):
Global cardinality constraints make approximating some MAx-2-CSPS harder.
[Conference paper] Leibniz International Proceedings in Informatics, LIPIcs [Details]
Austrin, P.; Kaski, P.; Kubjas, K. (2019):
Tensor network complexity of multilinear maps.
[Conference paper] 10th Innovations in Theoretical Computer Science, ITCS 2019, 10-12 January 2019, San Diego, United States; Leibniz International Proceedings in Informatics, LIPIcs [Details]
Austrin, P.; Kaski, P.; Koivisto, M.; Nederlof, J. (2018):
Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs.
IEEE Transactions on Information Theory 64: 1368-1373 [Details]
Austrin, P.; Guruswami, V.; Håstad, J. (2017):
(2 + ϵ)-SAT is NP-hard.
SIAM journal on computing (Print) 46: 1554-1573 [Details]
Austrin, P.; Chung, K.; Mahmoody, M.; Pass, R.; Seth, K. (2017):
On the Impossibility of Cryptography with Tamperable Randomness.
Algorithmica 79: 1052-1101 [Details]
Austrin, P.; Kaski, P.; Koivisto, M.; Nederlöf, J. (2016):
Dense Subset Sum may be the hardest.
[Conference paper] 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, 17 February 2016 through 20 February 2016; Leibniz International Proceedings in Informatics, LIPIcs [Details]
Austrin, P.; Benabbas, S.; Georgiou, K. (2016):
Better Balance by Being Biased - A 0.8776-Approximation for Max Bisection.
ACM Transactions on Algorithms 13: [Details]
Austrin, P.; Kaski, P.; Koivisto, M.; Nederlof, J. (2016):
Sharper upper bounds for unbalanced Uniquely Decodable Code Pairs.
[Conference paper] 2016 IEEE International Symposium on Information Theory, ISIT 2016, Universitat Pompeu FabraBarcelona, Spain, 10 July 2016 through 15 July 2016; 2016 IEEE International Symposium on Information Theory 335-339 [Details]
Austrin, P.; Kaski, P.; Koivisto, M.; Nederlof, J. (2015):
Subset sum in the absence of concentration.
[Conference paper] 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, 4 March 2015 through 7 March 2015; Leibniz International Proceedings in Informatics, LIPIcs 48-61 [Details]
Wu, Y.; Austrin, P.; Pitassi, T.; Liu, D. (2015):
Inapproximability of treewidth and related problems.
[Conference paper] 24th International Joint Conference on Artificial Intelligence, IJCAI 2015, 25-31 July 2015, Buenos Aires, Argentina; IJCAI International Joint Conference on Artificial Intelligence 4222-4228 [Details]
Austrin, P.; Manokaran, R.; Wenner, C. (2015):
On the NP-hardness of approximating ordering-constraint satisfaction problems.
Theory of Computing 11: 257-283 [Details]
Austrin, P.; Chung, K.; Mahmoody, M.; Pass, R.; Seth, K. (2014):
On the impossibility of cryptography with tamperable randomness.
[Conference paper] 17 August 2014 through 21 August 2014, Santa Barbara, CA; 34rd Annual International Cryptology Conference, CRYPTO 2014 462-479 [Details]
Austrin, P.; Håstad, J.; Guruswami, V. (2014):
(2 + epsilon)-Sat Is NP-hard.
[Conference paper] 55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014, 18 October 2014 through 21 October 2014; Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS 1-10 [Details]
Austrin, P.; Khot, S. (2014):
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem.
IEEE Transactions on Information Theory 60: 6636-6645 [Details]
Austrin, P.; Khot, S. (2013):
A characterization of approximation resistance for even k-partite CSPs.
[Conference paper] 2013 4th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2013; Berkeley, CA; United States; 9 January 2013 through 12 January 2013; ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science 187-196 [Details]
Austrin, P.; Håstad, J.; Pass, R. (2013):
On the power of many one-bit provers.
[Conference paper] 2013 4th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2013; Berkeley, CA; United States; 9 January 2013 through 12 January 2013; ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science 215-220 [Details]
Austrin, P.; Kaski, P.; Koivisto, M.; Määttä, J. (2013):
Space-time tradeoffs for subset sum - An improved worst case algorithm.
[Conference paper] 40th International Colloquium on Automata, Languages, and Programming, ICALP 2013; Riga; Latvia; 8 July 2013 through 12 July 2013; Automata, Languages, and Programming 45-56 [Details]
Austrin, P.; Manokaran, R.; Wenner, C. (2013):
On the NP-hardness of approximating ordering constraint satisfaction problems.
[Conference paper] 16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2013 and the 17th International Workshop on Randomization and Computation, RANDOM 2013; Berkeley, CA; United States; 21 August 2013 through 23 August 2013; Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques 26-41 [Details]
Austrin, P.; Benabbas, S.; Georgiou, K. (2013):
Better balance by being biased - A 0.8776-approximation for max bisection.
[Conference paper] 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, 6 January 2013 through 8 January 2013, New Orleans, LA; Proc Annu ACM SIAM Symp Discrete Algorithms 277-294 [Details]
Austrin, P.; Pitassi, T.; Wu, Y. (2012):
Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems.
[Conference paper] 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012 and the 16th International Workshop on Randomization and Computation, RANDOM 2012; Cambridge, MA; United States; International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 13-24 [Details]
Austrin, P.; O’Donnell, R.; Wright, J. (2012):
A New Point of NP-Hardness for 2-to-1 Label Cover.
[Conference paper] 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012 and the 16th International Workshop on Randomization and Computation, RANDOM 2012; Cambridge, MA; United States; Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 1-12 [Details]
Austrin, P.; Håstad, J. (2012):
On the Usefulness of Predicates.
ACM Transactions on Computation Theory 5: [Details]
Austrin, P.; Khot, S.; Safra, M. (2011):
Inapproximability of vertex cover and independent set in bounded degree graphs.
Theory of Computing 7: 27-43 [Details]
Austrin, P.; Håstad, J. (2011):
Randomly supported independence and resistance.
SIAM journal on computing (Print) 40: 1-27 [Details]
Austrin, P. (2010):
TOWARDS SHARP INAPPROXIMABILITY FOR ANY 2-CSP.
SIAM journal on computing (Print) 39: 2430-2463 [Details]
Austrin, P.; Håstad, J. (2009):
Randomly Supported Independence and Resistance.
[Conference paper] 41st Annual ACM Symposium on Theory of Computing Bethesda, MD, MAY 31-JUN 02, 2009; STOC'09 483-492 [Details]
Austrin, P.; Khot, S.; Safra, M. (2009):
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs.
[Conference paper] 24th Annual IEEE Conference on Computational Complexity, Paris, FRANCE, JUL 15-18, 2009; PROCEEDINGS OF THE 24TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY 74-80 [Details]
Austrin, P.; Mossel, E. (2009):
Approximation resistant predicates from pairwise independence.
Computational Complexity 18: 249-271 [Details]
Austrin, P.; Mossel, E. (2008):
Approximation resistant predicates from pairwise independence.
[Conference paper] 23rd Annual IEEE Conference on Computational Complexity Location: Univ Maryland, College Pk, MD Date: JUN 23-26, 2008; 23rd Annual IEEE Conference on Computational Complexity, proceedings 249-258 [Details]
Austrin, P.; Kreitz, G. (2008):
Lower bounds for Subset Cover based Broadcast Encryption.
[Conference paper] 1st International Conference on Cryptology in Africa; PROGRESS IN CRYPTOLOGY - AFRICACRYPT 2008   343-356 [Details]
Austrin, P. (2008):
Conditional Inapproximability and Limited Independence.
Doctoral thesis, monograph [Details]
Austrin, P. (2007):
Towards sharp inapproximability for any 2-CSP.
[Conference paper] 48th Annual IEEE Symposium on Foundations of Computer Science Location: Providence, RI Date: OCT 20-23, 2007; 48th Annual IEEE Symposium On Foundations Of Computer Science, Proceedings 307-317 [Details]
Austrin, P. (2007):
Balanced Max 2-Sat Might Not be the Hardest - PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING.
[Conference paper] 39th Annual ACM Symposium on Theory of Computing San Diego, CA, JUN 11-13, 2007; STOC 07: PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING 189-197 [Details]