Aaron Potechin

According to our database, Aaron Potechin authored at least 38 papers between 2008 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2023

Sum-of-Squares Lower Bounds for Densest k-Subgraph.

Chris Jones, Aaron Potechin, Goutham Rajendran, Jeff Xu

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Ellipsoid Fitting up to a Constant.

Jun-Ting Hsieh, Pravesh K. Kothari, Aaron Potechin, Jeff Xu

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Clique Is Hard on Average for Unary Sherali-Adams.

Susanna F. de Rezende, Aaron Potechin, Kilian Risse

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Separating MAX 2-AND, MAX DI-CUT and MAX CUT.

Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Near-optimal fitting of ellipsoids to random points.

Aaron Potechin, Paxton M. Turner, Prayaag Venkat, Alexander S. Wein

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

Bounds on the Total Coefficient Size of Nullstellensatz Proofs of the Pigeonhole Principle and the Ordering Principle.

Aaron Potechin, Aaron Zhang

CoRR, 2022

Sub-exponential time Sum-of-Squares lower bounds for Principal Components Analysis.

Aaron Potechin, Goutham Rajendran

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Almost-Orthogonal Bases for Inner Product Polynomials.

Chris Jones, Aaron Potechin

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

2021

Expander Random Walks: The General Case and Limitations.

Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2021

On the Mysteries of MAX NAE-SAT.

Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

SoS Certification for Symmetric Quadratic Functions and Its Connection to Constrained Boolean Hypercube Optimization.

Adam Kurpisz, Aaron Potechin, Elias Samuel Wirth

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Sum-of-Squares Lower Bounds for Sparse Independent Set.

Chris Jones, Aaron Potechin, Goutham Rajendran, Madhur Tulsiani, Jeff Xu

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Lengths of words accepted by nondeterministic finite automata.

Aaron Potechin, Jeffrey O. Shallit

Inf. Process. Lett., 2020

Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 SOS.

Bohdan Kivva, Aaron Potechin

CoRR, 2020

Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems.

Aaron Potechin, Goutham Rajendran

CoRR, 2020

The Spectrum of the Singular Values of Z-Shaped Graph Matrices.

Wenjun Cai, Aaron Potechin

CoRR, 2020

Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes.

Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones, Aaron Potechin, Goutham Rajendran

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Sum of Squares Bounds for the Ordering Principle.

Aaron Potechin

Proceedings of the 35th Computational Complexity Conference, 2020

On the Approximability of Presidential Type Predicates.

Neng Huang, Aaron Potechin

Proceedings of the Approximation, 2020

2019

On the approximation resistance of balanced linear threshold functions.

Aaron Potechin

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Sum of Squares Lower Bounds from Symmetry and a Good Story.

Aaron Potechin

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

2018

On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique.

Samuel B. Hopkins, Pravesh Kothari, Aaron Henry Potechin, Prasad Raghavendra, Tselil Schramm

ACM Trans. Algorithms, 2018

Sum of squares bounds for the total ordering principle.

Aaron Potechin

CoRR, 2018

2017

Bounds on Monotone Switching Networks for Directed Connectivity.

Aaron Potechin

J. ACM, 2017

A Note on Property Testing Sum of Squares and Multivariate Polynomial Interpolation.

Aaron Potechin, Liu Yang

CoRR, 2017

The Power of Sum-of-Squares for Detecting Hidden Structures.

Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Exact tensor completion with sum-of-squares.

Aaron Potechin, David Steurer

Proceedings of the 30th Conference on Learning Theory, 2017

A Note on Amortized Branching Program Complexity.

Aaron Potechin

Proceedings of the 32nd Computational Complexity Conference, 2017

2016

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

Electron. Colloquium Comput. Complex., 2016

A Note on Amortized Space Complexity.

Aaron Potechin

CoRR, 2016

Bounds on the Norms of Uniform Low Degree Graph Matrices.

Dhruv Medarametla, Aaron Potechin

Proceedings of the Approximation, 2016

2015

SoS and Planted Clique: Tight Analysis of MPW Moments at all Degrees and an Optimal Lower Bound at Degree Four.

Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin

CoRR, 2015

Sum-of-squares Lower Bounds for Planted Clique.

Raghu Meka, Aaron Potechin, Avi Wigderson

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

2014

Tight Bounds for Monotone Switching Networks via Fourier Analysis.

Siu Man Chan, Aaron Potechin

Theory Comput., 2014

2013

Improved upper and lower bound techniques for monotone switching networks for directed connectivity

Aaron Potechin

CoRR, 2013

Bounds on the Size of Sound Monotone Switching Networks Accepting Permutation Sets of Directed Trees

Joshua Brakensiek, Aaron Potechin

CoRR, 2013

2011

Monotone switching networks for directed connectivity are strictly more powerful than certain-knowledge switching networks

Aaron Potechin

CoRR, 2011

2008

Maximal caps in AG (6, 3).

Aaron Potechin

Des. Codes Cryptogr., 2008