Sotabase

Career

· Senior Research Scientist, UC Berkeley2019–
· Associate Professor of Electrical Engineering and Computer Science, UC Berkeley

Publications (92)

Optimal algorithms and inapproximability results for every CSP?
Symposium on the Theory of Computing · 2008
476
cited
Graph expansion and the unique games conjecture
Symposium on the Theory of Computing · 2010
282
cited
Rounding Semidefinite Programming Hierarchies via Global Correlation
IEEE Annual Symposium on Foundations of Computer Science · 2011
196
cited
Hardness of Learning Halfspaces with Noise
IEEE Annual Symposium on Foundations of Computer Science · 2006
192
cited
Lower Bounds on the Size of Semidefinite Programming Relaxations
Symposium on the Theory of Computing · 2014
179
cited
Agnostic Learning of Monomials by Halfspaces Is Hard
2009 50th Annual IEEE Symposium on Foundations of Computer Science · 2009
160
cited
The Power of Sum-of-Squares for Detecting Hidden Structures
IEEE Annual Symposium on Foundations of Computer Science · 2017
149
cited
Reductions between Expansion Problems
2012 IEEE 27th Conference on Computational Complexity · 2010
133
cited
Approximating CSPs with global cardinality constraints using SDP hierarchies
ACM-SIAM Symposium on Discrete Algorithms · 2011
129
cited
Approximate Constraint Satisfaction Requires Large LP Relaxations
IEEE Annual Symposium on Foundations of Computer Science · 2013
127
cited
Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph
2008 49th Annual IEEE Symposium on Foundations of Computer Science · 2008
117
cited
A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs
International Colloquium on Automata, Languages and Programming · 2016
109
cited
Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
2009 50th Annual IEEE Symposium on Foundations of Computer Science · 2009
106
cited
Many sparse cuts via higher eigenvalues
Symposium on the Theory of Computing · 2011
95
cited
Strongly refuting random CSPs below the spectral threshold
Symposium on the Theory of Computing · 2016
87
cited
Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
Symposium on the Theory of Computing · 2016
78
cited
How to Round Any CSP
2009 50th Annual IEEE Symposium on Foundations of Computer Science · 2009
78
cited
Making the Long Code Shorter
IEEE Annual Symposium on Foundations of Computer Science · 2012
78
cited
SDP Gaps and UGC Hardness for Multiway Cut , 0-Extension and Metric Labelling
2008
71
cited
List Decodable Learning via Sum of Squares
ACM-SIAM Symposium on Discrete Algorithms · 2019
70
cited
Sotabase