Per Austrin
Per Austrin
Associate Professor in Computer Science, KTH Royal Institute of Technology
Geverifieerd e-mailadres voor kth.se - Homepage
Titel
Geciteerd door
Geciteerd door
Jaar
Approximation resistant predicates from pairwise independence
P Austrin, E Mossel
Computational Complexity 18 (2), 249-271, 2009
1062009
Towards sharp inapproximability for any 2-CSP
P Austrin
SIAM Journal on Computing 39 (6), 2430-2463, 2010
682010
Balanced max 2-sat might not be the hardest
P Austrin
Proceedings of the thirty-ninth annual ACM symposium on Theory of computing …, 2007
592007
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
582009
Inapproximability of Treewidth and Related Problems
Y Wu, P Austrin, T Pitassi, D Liu
Journal of Artificial Intelligence Research, 569-600, 2014
46*2014
Randomly supported independence and resistance
P Austrin, J HÅstad
SIAM Journal on Computing 40 (1), 1-27, 2011
462011
On the usefulness of predicates
P Austrin, J Håstad
ACM Transactions on Computation Theory (TOCT) 5 (1), 1, 2013
442013
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
432016
On the impossibility of cryptography with tamperable randomness
P Austrin, KM Chung, M Mahmoody, R Pass, K Seth
Algorithmica 79 (4), 1052-1101, 2017
412017
-Sat Is NP-hard
P Austrin, V Guruswami, J Håstad
SIAM Journal on Computing 46 (5), 1554-1573, 2017
392017
Inapproximability of NP-complete variants of Nash equilibrium
P Austrin, M Braverman, E Chlamtáč
Theory of Computing 9 (1), 117-142, 2013
312013
Dense Subset Sum may be the hardest
P Austrin, M Koivisto, P Kaski, J Nederlof
arXiv preprint arXiv:1508.06019, 2015
192015
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
192013
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
152015
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
142014
Conditional inapproximability and limited independence
P Austrin
KTH, 2008
122008
Lower bounds for subset cover based broadcast encryption
P Austrin, G Kreitz
International Conference on Cryptology in Africa, 343-356, 2008
112008
Noise correlation bounds for uniform low degree functions
P Austrin, E Mossel
Arkiv för Matematik 51 (1), 29-52, 2013
102013
Improved Inapproximability of Rainbow Coloring
P Austrin, A Bhangale, A Potukuchi
arXiv preprint arXiv:1810.02784, 2018
92018
On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems
P Austrin, R Manokaran, C Wenner
Approximation, Randomization, and Combinatorial Optimization. Algorithms and …, 2013
92013
Het systeem kan de bewerking nu niet uitvoeren. Probeer het later opnieuw.
Artikelen 1–20