| 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 | 135 | 2011 |
| Approximation resistant predicates from pairwise independence P Austrin, E Mossel Computational Complexity 18 (2), 249-271, 2009 | 127 | 2009 |
| -Sat Is NP-hard P Austrin, V Guruswami, J Håstad SIAM Journal on Computing 46 (5), 1554-1573, 2017 | 93 | 2017 |
| Towards sharp inapproximability for any 2-CSP P Austrin SIAM Journal on Computing 39 (6), 2430-2463, 2010 | 90 | 2010 |
| 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 | 84 | 2016 |
| Balanced max 2-sat might not be the hardest P Austrin Proceedings of the thirty-ninth annual ACM symposium on Theory of computing …, 2007 | 80 | 2007 |
| Inapproximability of Treewidth and Related Problems Y Wu, P Austrin, T Pitassi, D Liu Journal of Artificial Intelligence Research, 569-600, 2014 | 72* | 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 | 55 | 2017 |
| Randomly supported independence and resistance P Austrin, J HÅstad SIAM Journal on Computing 40 (1), 1-27, 2011 | 50 | 2011 |
| Inapproximability of NP-complete variants of Nash equilibrium P Austrin, M Braverman, E Chlamtáč Theory of Computing 9 (1), 117-142, 2013 | 47 | 2013 |
| On the usefulness of predicates P Austrin, J Håstad ACM Transactions on Computation Theory (TOCT) 5 (1), 1-24, 2013 | 45 | 2013 |
| Dense Subset Sum may be the hardest P Austrin, M Koivisto, P Kaski, J Nederlof arXiv preprint arXiv:1508.06019, 2015 | 39 | 2015 |
| 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 | 35 | 2015 |
| 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 | 32 | 2013 |
| 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 | 25 | 2022 |
| Improved inapproximability of rainbow coloring P Austrin, A Bhangale, A Potukuchi Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete …, 2020 | 25 | 2020 |
| 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 | 25 | 2014 |
| Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder P Austrin, A Stankovic arXiv preprint arXiv:1907.04165, 2019 | 19 | 2019 |
| On the NP-hardness of approximating ordering-constraint satisfaction problems P Austrin, R Manokaran, C Wenner Theory of Computing 11 (1), 257-283, 2015 | 17 | 2015 |
| Tensor network complexity of multilinear maps P Austrin, P Kaski, K Kubjas arXiv preprint arXiv:1712.09630, 2017 | 16 | 2017 |
Johan HåstadProfessor i teoretisk datalogi, KTHVerified email at kth.se
