Aaron Potechin

Publication Activity (10 Years)

Years Active: 2008-2024
Publications (10 Years): 53

Top Topics

Linear Threshold Functions

Independent Set

Top Venues

Publications

Pravesh K. Kothari, Aaron Potechin, Jeff Xu
Sum-of-Squares Lower Bounds for Independent Set on Ultra-Sparse Random Graphs. STOC (2024)
Pravesh Kothari, Aaron Potechin, Jeff Xu
Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs. CoRR (2024)
Susanna F. de Rezende, Aaron Potechin, Kilian Risse
Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients. CoRR (2024)
Aaron Potechin, Aaron Zhang
Bounds on the Total Coefficient Size of Nullstellensatz Proofs of the Pigeonhole Principle. ICALP (2024)
Aaron Potechin, Paxton M. Turner, Prayaag Venkat, Alexander S. Wein
Near-optimal fitting of ellipsoids to random points. COLT (2023)
Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
Separating MAX 2-AND, MAX DI-CUT and MAX CUT. FOCS (2023)
Jun-Ting Hsieh, Pravesh K. Kothari, Aaron Potechin, Jeff Xu
Ellipsoid Fitting Up to a Constant. CoRR (2023)
Chris Jones, Aaron Potechin, Goutham Rajendran, Jeff Xu
Sum-of-Squares Lower Bounds for Densest k-Subgraph. CoRR (2023)
Susanna F. de Rezende, Aaron Potechin, Kilian Risse
Clique Is Hard on Average for Unary Sherali-Adams. FOCS (2023)
Chris Jones, Aaron Potechin, Goutham Rajendran, Jeff Xu
Sum-of-Squares Lower Bounds for Densest k-Subgraph. STOC (2023)
Jun-Ting Hsieh, Pravesh K. Kothari, Aaron Potechin, Jeff Xu
Ellipsoid Fitting up to a Constant. ICALP (2023)
Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
Separating MAX 2-AND, MAX DI-CUT and MAX CUT. CoRR (2022)
Aaron Potechin, Aaron Zhang
Bounds on the Total Coefficient Size of Nullstellensatz Proofs of the Pigeonhole Principle and the Ordering Principle. CoRR (2022)
Aaron Potechin, Goutham Rajendran
Sub-exponential time Sum-of-Squares lower bounds for Principal Components Analysis. NeurIPS (2022)
Chris Jones, Aaron Potechin, Goutham Rajendran, Madhur Tulsiani, Jeff Xu
Sum-of-Squares Lower Bounds for Sparse Independent Set. FOCS (2022)
Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, Amnon Ta-Shma
Expander Random Walks: The General Case and Limitations. ICALP (2022)
Chris Jones, Aaron Potechin
Almost-Orthogonal Bases for Inner Product Polynomials. ITCS (2022)
Chris Jones, Aaron Potechin
Almost-Orthogonal Bases for Inner Product Polynomials. CoRR (2021)
Adam Kurpisz, Aaron Potechin, Elias Samuel Wirth
SoS certification for symmetric quadratic functions and its connection to constrained Boolean hypercube optimization. CoRR (2021)
Adam Kurpisz, Aaron Potechin, Elias Samuel Wirth
SoS Certification for Symmetric Quadratic Functions and Its Connection to Constrained Boolean Hypercube Optimization. ICALP (2021)
Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
On the Mysteries of MAX NAE-SAT. SODA (2021)
Chris Jones, Aaron Potechin, Goutham Rajendran, Madhur Tulsiani, Jeff Xu
Sum-of-Squares Lower Bounds for Sparse Independent Set. FOCS (2021)
Chris Jones, Aaron Potechin, Goutham Rajendran, Madhur Tulsiani, Jeff Xu
Sum-of-Squares Lower Bounds for Sparse Independent Set. CoRR (2021)
Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, Amnon Ta-Shma
Expander Random Walks: The General Case and Limitations. Electron. Colloquium Comput. Complex. 28 (2021)
Aaron Potechin
Sum of Squares Bounds for the Ordering Principle. Computational Complexity Conference (2020)
Neng Huang, Aaron Potechin
On the Approximability of Presidential Type Predicates. APPROX-RANDOM (2020)
Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
On the Mysteries of MAX NAE-SAT. CoRR (2020)
Aaron Potechin, Jeffrey O. Shallit
Lengths of words accepted by nondeterministic finite automata. Inf. Process. Lett. 162 (2020)
Bohdan Kivva, Aaron Potechin
Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 SOS. CoRR (2020)
Aaron Potechin, Goutham Rajendran
Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems. CoRR (2020)
Wenjun Cai, Aaron Potechin
The Spectrum of the Singular Values of Z-Shaped Graph Matrices. CoRR (2020)
Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones, Aaron Potechin, Goutham Rajendran
Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes. CoRR (2020)
Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones, Aaron Potechin, Goutham Rajendran
Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes. FOCS (2020)
Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh K. Kothari, Ankur Moitra, Aaron Potechin
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. SIAM J. Comput. 48 (2) (2019)
Aaron Potechin
On the approximation resistance of balanced linear threshold functions. STOC (2019)
Aaron Potechin
Sum of Squares Lower Bounds from Symmetry and a Good Story. ITCS (2019)
Neng Huang, Aaron Potechin
On the Approximability of Presidential Type Predicates. CoRR (2019)
Aaron Potechin
On the Approximation Resistance of Balanced Linear Threshold Functions. CoRR (2018)
Aaron Potechin, Jeffrey O. Shallit
Lengths of Words Accepted by Nondeterministic Finite Automata. CoRR (2018)
Aaron Potechin
Sum of squares bounds for the total ordering principle. CoRR (2018)
Aaron Potechin
Sum of squares lower bounds from symmetry and a good story. CoRR (2017)
Aaron Potechin
A Note on Amortized Branching Program Complexity. Computational Complexity Conference (2017)
Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer
The power of sum-of-squares for detecting hidden structures. CoRR (2017)
Aaron Potechin
Bounds on Monotone Switching Networks for Directed Connectivity. J. ACM 64 (4) (2017)
Aaron Potechin, David Steurer
Exact tensor completion with sum-of-squares. CoRR (2017)
Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer
The Power of Sum-of-Squares for Detecting Hidden Structures. FOCS (2017)
Aaron Potechin, Liu Yang
A Note on Property Testing Sum of Squares and Multivariate Polynomial Interpolation. CoRR (2017)
Aaron Potechin, David Steurer
Exact tensor completion with sum-of-squares. COLT (2017)
Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. FOCS (2016)
Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. CoRR (2016)
Dhruv Medarametla, Aaron Potechin
Bounds on the Norms of Uniform Low Degree Graph Matrices. APPROX-RANDOM (2016)
Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. Electron. Colloquium Comput. Complex. 23 (2016)
Aaron Potechin
A Note on Amortized Space Complexity. CoRR (2016)
Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin
SoS and Planted Clique: Tight Analysis of MPW Moments at all Degrees and an Optimal Lower Bound at Degree Four. CoRR (2015)
Raghu Meka, Aaron Potechin, Avi Wigderson
Sum-of-squares Lower Bounds for Planted Clique. STOC (2015)
Raghu Meka, Aaron Potechin, Avi Wigderson
Sum-of-squares lower bounds for planted clique. CoRR (2015)
Siu Man Chan, Aaron Potechin
Tight Bounds for Monotone Switching Networks via Fourier Analysis. Theory Comput. 10 (2014)
Joshua Brakensiek, Aaron Potechin
Bounds on the Size of Sound Monotone Switching Networks Accepting Permutation Sets of Directed Trees CoRR (2013)
Aaron Potechin
Improved upper and lower bound techniques for monotone switching networks for directed connectivity CoRR (2013)
Siu Man Chan, Aaron Potechin
Tight Bounds for Monotone Switching Networks via Fourier Analysis. Electron. Colloquium Comput. Complex. 19 (2012)
Siu Man Chan, Aaron Potechin
Tight bounds for monotone switching networks via fourier analysis. STOC (2012)
Aaron Potechin
Monotone switching networks for directed connectivity are strictly more powerful than certain-knowledge switching networks CoRR (2011)
Aaron Potechin
Bounds on Monotone Switching Networks for Directed Connectivity. FOCS (2010)
Aaron Potechin
Bounds on Monotone Switching Networks for Directed Connectivity. Electron. Colloquium Comput. Complex. 16 (2009)
Aaron Potechin
Bounds on monotone switching networks for directed connectivity CoRR (2009)
Aaron Potechin
Maximal caps in AG (6, 3). Des. Codes Cryptogr. 46 (3) (2008)