| 2026 | SODA | MAX BISECTION might be harder to approximate than MAX CUT. | Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick |
| 2026 | SODA | New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs. | Joshua Brakensiek, Lorenzo Ciardo, Venkatesan Guruswami, Aaron Potechin, Stanislav Zivn |
| 2026 | STOC | Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes. | Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick |
| 2025 | STOC | Sum-of-Squares Lower Bounds for Coloring Random Graphs. | Aaron Potechin, Jeff Xu |
| 2024 | FOCS | Sum-of-Squares Lower Bounds for Non-Gaussian Component Analysis. | Ilias Diakonikolas, Sushrut Karmalkar, Shuo Pang, Aaron Potechin |
| 2024 | ICALP | Bounds on the Total Coefficient Size of Nullstellensatz Proofs of the Pigeonhole Principle. | Aaron Potechin, Aaron Zhang |
| 2024 | STOC | Sum-of-Squares Lower Bounds for Independent Set on Ultra-Sparse Random Graphs. | Pravesh K. Kothari, Aaron Potechin, Jeff Xu |
| 2023 | COLT | Near-optimal fitting of ellipsoids to random points. | Aaron Potechin, Paxton M. Turner, Prayaag Venkat, Alexander S. Wein |
| 2023 | FOCS | Separating MAX 2-AND, MAX DI-CUT and MAX CUT. | Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick |
| 2023 | FOCS | Clique Is Hard on Average for Unary Sherali-Adams. | Susanna F. de Rezende, Aaron Potechin, Kilian Risse |
| 2023 | ICALP | Ellipsoid Fitting up to a Constant. | Jun-Ting Hsieh, Pravesh K. Kothari, Aaron Potechin, Jeff Xu |
| 2023 | STOC | Sum-of-Squares Lower Bounds for Densest k-Subgraph. | Chris Jones, Aaron Potechin, Goutham Rajendran, Jeff Xu |
| 2022 | ICALP | Expander Random Walks: The General Case and Limitations. | Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, Amnon Ta-Shma |
| 2021 | FOCS | Sum-of-Squares Lower Bounds for Sparse Independent Set. | Chris Jones, Aaron Potechin, Goutham Rajendran, Madhur Tulsiani, Jeff Xu |
| 2021 | ICALP | SoS Certification for Symmetric Quadratic Functions and Its Connection to Constrained Boolean Hypercube Optimization. | Adam Kurpisz, Aaron Potechin, Elias Samuel Wirth |
| 2021 | SODA | On the Mysteries of MAX NAE-SAT. | Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick |
| 2020 | FOCS | Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes. | Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones, Aaron Potechin, Goutham Rajendran |
| 2019 | STOC | On the approximation resistance of balanced linear threshold functions. | Aaron Potechin |
| 2017 | COLT | Exact tensor completion with sum-of-squares. | Aaron Potechin, David Steurer |
| 2017 | FOCS | The Power of Sum-of-Squares for Detecting Hidden Structures. | Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer |
| 2016 | FOCS | A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. | Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin |
| 2015 | STOC | Sum-of-squares Lower Bounds for Planted Clique. | Raghu Meka, Aaron Potechin, Avi Wigderson |
| 2012 | STOC | Tight bounds for monotone switching networks via fourier analysis. | Siu Man Chan, Aaron Potechin |
| 2010 | FOCS | Bounds on Monotone Switching Networks for Directed Connectivity. | Aaron Potechin |