Approximation resistant predicates from pairwise independence P Austrin, E Mossel
Computational Complexity 18 (2), 249-271, 2009
109 2009 Inapproximability of vertex cover and independent set in bounded degree graphs P Austrin, S Khot, M Safra
2009 24th Annual IEEE Conference on Computational Complexity, 74-80, 2009
103 2009 Towards sharp inapproximability for any 2-CSP P Austrin
SIAM Journal on Computing 39 (6), 2430-2463, 2010
69 2010 Balanced max 2-sat might not be the hardest P Austrin
Proceedings of the thirty-ninth annual ACM symposium on Theory of computing …, 2007
60 2007 Inapproximability of Treewidth and Related Problems Y Wu, P Austrin, T Pitassi, D Liu
Journal of Artificial Intelligence Research, 569-600, 2014
47 * 2014 Randomly supported independence and resistance P Austrin, J HÅstad
SIAM Journal on Computing 40 (1), 1-27, 2011
46 2011 P Austrin, V Guruswami, J Håstad
SIAM Journal on Computing 46 (5), 1554-1573, 2017
45 2017 On the usefulness of predicates P Austrin, J Håstad
ACM Transactions on Computation Theory (TOCT) 5 (1), 1, 2013
45 2013 On the impossibility of cryptography with tamperable randomness P Austrin, KM Chung, M Mahmoody, R Pass, K Seth
Algorithmica 79 (4), 1052-1101, 2017
43 2017 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), 2, 2016
43 2016 Inapproximability of NP-complete variants of Nash equilibrium P Austrin, M Braverman, E Chlamtáč
Theory of Computing 9 (1), 117-142, 2013
33 2013 Space–time tradeoffs for subset sum: An improved worst case algorithm P Austrin, P Kaski, M Koivisto, J Määttä
International Colloquium on Automata, Languages, and Programming, 45-56, 2013
24 2013 Dense Subset Sum may be the hardest P Austrin, M Koivisto, P Kaski, J Nederlof
arXiv preprint arXiv:1508.06019, 2015
21 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
18 2015 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
15 2014 Conditional inapproximability and limited independence P Austrin
KTH, 2008
12 2008 Lower bounds for subset cover based broadcast encryption P Austrin, G Kreitz
International Conference on Cryptology in Africa, 343-356, 2008
11 2008 Improved Inapproximability of Rainbow Coloring P Austrin, A Bhangale, A Potukuchi
arXiv preprint arXiv:1810.02784, 2018
10 2018 Tensor network complexity of multilinear maps P Austrin, P Kaski, K Kubjas
arXiv preprint arXiv:1712.09630, 2017
10 2017 On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems P Austrin, R Manokaran, C Wenner
Approximation, Randomization, and Combinatorial Optimization. Algorithms and …, 2013
10 2013 
Johan HåstadProfessor i teoretisk datalogi, KTHGeverifieerd e-mailadres voor kth.se
