 | 2012 |
|---|
| 23 |       | Per Austrin,
Johan Håstad:
On the Usefulness of Predicates
CoRR abs/1204.5662: (2012) |
| 22 | | Per Austrin,
Ryan O'Donnell,
John Wright:
A new point of NP-hardness for 2-to-1 Label Cover
CoRR abs/1204.5666: (2012) |
| 2011 |
|---|
| 21 | | Per Austrin,
Mark Braverman,
Eden Chlamtac:
Inapproximability of NP-Complete Variants of Nash Equilibrium.
APPROX-RANDOM 2011: 13-25 |
| 20 | | Per Austrin,
Subhash Khot:
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem.
ICALP (1) 2011: 474-485 |
| 19 | | Per Austrin,
Mark Braverman,
Eden Chlamtac:
Inapproximability of NP-Complete Variants of Nash Equilibrium
CoRR abs/1104.3760: (2011) |
| 18 | | Per Austrin,
Toniann Pitassi,
Yu Wu:
Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems
CoRR abs/1109.4910: (2011) |
| 17 | | Per Austrin,
Johan Håstad:
Randomly Supported Independence and Resistance.
SIAM J. Comput. 40(1): 1-27 (2011) |
| 16 | | Per Austrin,
Subhash Khot,
Muli Safra:
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs.
Theory of Computing 7(1): 27-43 (2011) |
| 2010 |
|---|
| 15 | | Per Austrin:
Improved Inapproximability for Submodular Maximization.
APPROX-RANDOM 2010: 12-24 |
| 14 | | Per Austrin,
Siavosh Benabbas,
Avner Magen:
On Quadratic Threshold CSPs.
LATIN 2010: 332-343 |
| 13 | | Per Austrin:
Improved Inapproximability For Submodular Maximization
CoRR abs/1004.3777: (2010) |
| 12 | | Per Austrin,
Subhash Khot:
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem
CoRR abs/1010.1481: (2010) |
| 11 | | Per Austrin:
Towards Sharp Inapproximability for Any 2-CSP.
SIAM J. Comput. 39(6): 2430-2463 (2010) |
| 2009 |
|---|
| 10 | | Per Austrin,
Subhash Khot,
Muli Safra:
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs.
IEEE Conference on Computational Complexity 2009: 74-80 |
| 9 | | Per Austrin,
Johan Håstad:
Randomly supported independence and resistance.
STOC 2009: 483-492 |
| 8 | | Per Austrin,
Elchanan Mossel:
Approximation Resistant Predicates from Pairwise Independence.
Computational Complexity 18(2): 249-271 (2009) |
| 2008 |
|---|
| 7 | | Per Austrin,
Gunnar Kreitz:
Lower Bounds for Subset Cover Based Broadcast Encryption.
AFRICACRYPT 2008: 343-356 |
| 6 | | Per Austrin,
Elchanan Mossel:
Approximation Resistant Predicates from Pairwise Independence.
IEEE Conference on Computational Complexity 2008: 249-258 |
| 5 | | Per Austrin,
Elchanan Mossel:
Approximation Resistant Predicates From Pairwise Independence
CoRR abs/0802.2300: (2008) |
| 4 | | Per Austrin,
Elchanan Mossel:
Approximation Resistant Predicates From Pairwise Independence.
Electronic Colloquium on Computational Complexity (ECCC) 15(009): (2008) |
| 2007 |
|---|
| 3 | | Per Austrin:
Towards Sharp Inapproximability For Any 2-CSP.
FOCS 2007: 307-317 |
| 2 | | Per Austrin:
Balanced max 2-sat might not be the hardest.
STOC 2007: 189-197 |
| 2006 |
|---|
| 1 | | Per Austrin:
Balanced Max 2-Sat might not be the hardest.
Electronic Colloquium on Computational Complexity (ECCC) 13(088): (2006) |
Data released under the ODC-BY 1.0 license — See also our legal information page