papers
Publications (19)
cs.CC2013
On the Power of Many One-Bit Provers
Per Austrin, Johan HÃ¥stad, Rafael Pass
cs.CC2011
Inapproximability of NP-Complete Variants of Nash Equilibrium
Per Austrin, Mark Braverman, Eden Chlamtac
cs.CC2012
On the Usefulness of Predicates
Per Austrin, Johan HÃ¥stad
cs.DS2013
Space--Time Tradeoffs for Subset Sum: An Improved Worst Case Algorithm
Per Austrin, Petteri Kaski, Mikko Koivisto +1
cs.CC2010
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem
Per Austrin, Subhash Khot
cs.CC2012
A new point of NP-hardness for 2-to-1 Label Cover
Per Austrin, Ryan O'Donnell, John Wright
cs.CC2019
Simplified inpproximability of hypergraph coloring via t-agreeing families
Per Austrin, Amey Bhangale, Aditya Potukuchi
cs.CC2018
Tensor network complexity of multilinear maps
Per Austrin, Petteri Kaski, Kaie Kubjas
cs.IT2016
Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs
Per Austrin, Petteri Kaski, Mikko Koivisto +1
cs.CC2012
New NP-hardness results for 3-Coloring and 2-to-1 Label Cover
Per Austrin, Ryan O'Donnell, Li-Yang Tan +1
cs.CC2010
Improved Inapproximability For Submodular Maximization
Per Austrin
cs.DS2015
Dense Subset Sum may be the hardest
Per Austrin, Mikko Koivisto, Petteri Kaski +1
cs.CC2013
A Characterization of Approximation Resistance for Even $k$-Partite CSPs
Per Austrin, Subhash Khot
math.PR2010
Noise Correlation Bounds for Uniform Low Degree Functions
Per Austrin, Elchanan Mossel
cs.DS2012
Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection
Per Austrin, Siavosh Benabbas, Konstantinos Georgiou
cs.CC2008
Approximation Resistant Predicates From Pairwise Independence
Per Austrin, Elchanan Mossel
cs.CC2013
On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems
Per Austrin, Rajsekar Manokaran, Cenny Wenner
cs.CC2011
Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems
Per Austrin, Toniann Pitassi, Yu Wu
cs.CC2018
Improved Inapproximability of Rainbow Coloring
Per Austrin, Amey Bhangale, Aditya Potukuchi