Follow
Per Austrin
Per Austrin
Associate Professor in Computer Science, KTH Royal Institute of Technology
Verified email at kth.se - Homepage
Title
Cited by
Cited by
Year
Inapproximability of vertex cover and independent set in bounded degree graphs
P Austrin, S Khot, M Safra
Theory of Computing 7 (1), 27-43, 2011
1282011
Approximation resistant predicates from pairwise independence
P Austrin, E Mossel
Computational Complexity 18 (2), 249-271, 2009
1202009
Towards sharp inapproximability for any 2-CSP
P Austrin
SIAM Journal on Computing 39 (6), 2430-2463, 2010
832010
-Sat Is NP-hard
P Austrin, V Guruswami, J Håstad
SIAM Journal on Computing 46 (5), 1554-1573, 2017
822017
Better balance by being biased: A 0.8776-approximation for max bisection
P Austrin, S Benabbas, K Georgiou
ACM Transactions on Algorithms (TALG) 13 (1), 1-27, 2016
762016
Balanced max 2-sat might not be the hardest
P Austrin
Proceedings of the thirty-ninth annual ACM symposium on Theory of computing …, 2007
752007
Inapproximability of Treewidth and Related Problems
Y Wu, P Austrin, T Pitassi, D Liu
Journal of Artificial Intelligence Research, 569-600, 2014
63*2014
On the impossibility of cryptography with tamperable randomness
P Austrin, KM Chung, M Mahmoody, R Pass, K Seth
Algorithmica 79 (4), 1052-1101, 2017
532017
Randomly supported independence and resistance
P Austrin, J HÅstad
SIAM Journal on Computing 40 (1), 1-27, 2011
502011
Inapproximability of NP-complete variants of Nash equilibrium
P Austrin, M Braverman, E Chlamtáč
Theory of Computing 9 (1), 117-142, 2013
472013
On the usefulness of predicates
P Austrin, J Håstad
ACM Transactions on Computation Theory (TOCT) 5 (1), 1-24, 2013
422013
Dense Subset Sum may be the hardest
P Austrin, M Koivisto, P Kaski, J Nederlof
arXiv preprint arXiv:1508.06019, 2015
342015
Subset Sum in the Absence of Concentration
P Austrin, P Kaski, M Koivisto, J Nederlof
32nd International Symposium on Theoretical Aspects of Computer Science …, 2015
282015
Space–time tradeoffs for subset sum: An improved worst case algorithm
P Austrin, P Kaski, M Koivisto, J Määttä
Automata, Languages, and Programming: 40th International Colloquium, ICALP …, 2013
282013
Improved inapproximability of rainbow coloring
P Austrin, A Bhangale, A Potukuchi
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete …, 2020
232020
A simple deterministic reduction for the gap minimum distance of code problem
P Austrin, S Khot
IEEE Transactions on Information Theory 60 (10), 6636-6645, 2014
212014
Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
P Austrin, A Stankovic
arXiv preprint arXiv:1907.04165, 2019
182019
On the impossibility of key agreements from quantum random oracles
P Austrin, H Chung, KM Chung, S Fu, YT Lin, M Mahmoody
Advances in Cryptology–CRYPTO 2022: 42nd Annual International Cryptology …, 2022
162022
Tensor network complexity of multilinear maps
P Austrin, P Kaski, K Kubjas
arXiv preprint arXiv:1712.09630, 2017
152017
On the NP-hardness of approximating ordering-constraint satisfaction problems
P Austrin, R Manokaran, C Wenner
Theory of Computing 11 (1), 257-283, 2015
152015
The system can't perform the operation now. Try again later.
Articles 1–20