Profiles2020-2026
Aaron Potechin
University of Chicago
9Papers
1Last author
12Unique co-authors
1First author
0Solo
First and last author come from byline position, which some venues assign alphabetically.
Recent papers9
- Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding SchemesAuthor 3 of 4STOC 2026
- MAX BISECTION might be harder to approximate than MAX CUTAuthor 3 of 4SODA 2026
- Sum-of-Squares Lower Bounds for Independent Set on Ultra-Sparse Random GraphsAuthor 2 of 3STOC 2024 · 2 citations
- Sum-of-Squares Lower Bounds for Non-Gaussian Component AnalysisAuthor 4 of 4FOCS 2024 · 1 citation
- Sum-of-Squares Lower Bounds for Densest k-SubgraphAuthor 2 of 4STOC 2023 · 8 citations
- Separating MAX 2-AND, MAX DI-CUT and MAX CUTAuthor 3 of 4FOCS 2023 · 3 citations
- Sub-exponential time Sum-of-Squares lower bounds for Principal Components AnalysisAuthor 1 of 2NeurIPS 2022 · 10 citations
- Sum-of-Squares Lower Bounds for Sparse Independent SetAuthor 2 of 5FOCS 2021 · 14 citations
- Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine PlanesAuthor 4 of 5FOCS 2020 · 29 citations
