Aaron Potechin

Generating author description...

All published works

Action	Title	Year	Authors
+	SoS Certification for Symmetric Quadratic Functions and Its Connection to Constrained Boolean Hypercube Optimization	2025	Adam Kurpisz Aaron Potechin Elias Wirth
+ PDF Chat	Sum-of-squares lower bounds for Non-Gaussian Component Analysis	2024	Ilias Diakonikolas Sushrut Karmalkar Shuo Pang Aaron Potechin
+ PDF Chat	On the second moment of the determinant of random symmetric, Wigner, and Hermitian matrices	2024	Dominik Beck Zelin Lv Aaron Potechin
+ PDF Chat	Hardness of sampling for the anti-ferromagnetic Ising model on random graphs	2024	Neng Huang Will Perkins Aaron Potechin
+ PDF Chat	Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs	2024	Pravesh K. Kothari Aaron Potechin Jeff Xu
+	Sum-of-Squares Lower Bounds for Independent Set on Ultra-Sparse Random Graphs	2024	Pravesh K. Kothari Aaron Potechin Jeff Xu
+ PDF Chat	On induced subgraphs of $H(n,3)$ with maximum degree $1$	2024	Aaron Potechin Hing Yin Tsang
+ PDF Chat	Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients	2024	Susanna F. de Rezende Aaron Potechin Kilian Risse
+ PDF Chat	Separating MAX 2-AND, MAX DI-CUT and MAX CUT	2023	Joshua Brakensiek Neng Huang Aaron Potechin Uri Zwick
+	Clique Is Hard on Average for Unary Sherali-Adams	2023	Susanna F. de Rezende Aaron Potechin Kilian Risse
+	Sum-of-Squares Lower Bounds for Densest k-Subgraph	2023	C. A. Jones Aaron Potechin Goutham Rajendran Jeff Xu
+	Sum-of-Squares Lower Bounds for Densest $k$-Subgraph	2023	Chris Jones Aaron Potechin Goutham Rajendran Jeff L. Xu
+	Ellipsoid Fitting Up to a Constant	2023	Jun-Ting Hsieh Pravesh K. Kothari Aaron Potechin Jeff Xu
+ PDF Chat	Sum-of-Squares Lower Bounds for Sparse Independent Set	2022	Chris Jones Aaron Potechin Goutham Rajendran Madhur Tulsiani Jeff Xu
+	Bounds on the Total Coefficient Size of Nullstellensatz Proofs of the Pigeonhole Principle and the Ordering Principle	2022	Aaron Potechin Aaron Zhang
+	On Mixing Distributions Via Random Orthogonal Matrices and the Spectrum of the Singular Values of Multi-Z Shaped Graph Matrices	2022	Wenjun Cai Aaron Potechin
+	Separating MAX 2-AND, MAX DI-CUT and MAX CUT	2022	Joshua Brakensiek Neng Huang Aaron Potechin Uri Zwick
+	The Sixth Moment of Random Determinants	2022	Zelin Lv Aaron Potechin
+	SoS certification for symmetric quadratic functions and its connection to constrained boolean hypercube optimization	2021	Adam Kurpisz Aaron Potechin Elias Samuel Wirth
+	Almost-Orthogonal Bases for Inner Product Polynomials.	2021	Chris Jones Aaron Potechin
+	Sum-of-Squares Lower Bounds for Sparse Independent Set	2021	Chris Jones Aaron Potechin Goutham Rajendran Madhur Tulsiani Jeff Xu
+	SoS certification for symmetric quadratic functions and its connection to constrained Boolean hypercube optimization	2021	Adam Kurpisz Aaron Potechin Elias Samuel Wirth
+	Almost-Orthogonal Bases for Inner Product Polynomials	2021	Chris Jones Aaron Potechin
+	Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 SOS	2020	Bohdan Kivva Aaron Potechin
+	Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems.	2020	Aaron Potechin Goutham Rajendran
+ PDF Chat	Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes	2020	Mrinalkanti Ghosh Fernando Granha Jeronimo Chris Jones Aaron Potechin Goutham Rajendran
+	On the Mysteries of MAX NAE-SAT.	2020	Joshua Brakensiek Neng Huang Aaron Potechin Uri Zwick
+	Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes	2020	Mrinalkanti Ghosh Fernando Granha Jeronimo Chris Jones Aaron Potechin Goutham Rajendran
+ PDF Chat	Lengths of words accepted by nondeterministic finite automata	2020	Aaron Potechin Jeffrey Shallit
+ PDF Chat	The Spectrum of the Singular Values of Z-Shaped Graph Matrices	2020	Wenjun Cai Aaron Potechin
+	A Conjecture on Induced Subgraphs of Cayley Graphs	2020	Aaron Potechin Hing Yin Tsang
+	The Spectrum of the Singular Values of Z-Shaped Graph Matrices	2020	Wenjun Cai Aaron Potechin
+	On the Approximability of Presidential Type Predicates	2020	Neng Huang Aaron Potechin
+	Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 SOS	2020	Bohdan Kivva Aaron Potechin
+	Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes	2020	Mrinalkanti Ghosh Fernando Granha Jeronimo Chris Jones Aaron Potechin Goutham Rajendran
+	Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems	2020	Aaron Potechin Goutham Rajendran
+	On the Mysteries of MAX NAE-SAT	2020	Joshua Brakensiek Neng Huang Aaron Potechin Uri Zwick
+ PDF Chat	On the approximation resistance of balanced linear threshold functions	2019	Aaron Potechin
+ PDF Chat	A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem	2019	Boaz Barak Samuel B. Hopkins Jonathan A. Kelner Pravesh K. Kothari Ankur Moitra Aaron Potechin
+	On the Approximability of Presidential Type Predicates	2019	Neng Huang Aaron Potechin
+	Sum of squares bounds for the total ordering principle.	2018	Aaron Potechin
+	On the Approximation Resistance of Balanced Linear Threshold Functions	2018	Aaron Potechin
+	Lengths of Words Accepted by Nondeterministic Finite Automata	2018	Aaron Potechin Jeffrey Shallit
+	Sum of squares bounds for the ordering principle	2018	Aaron Potechin
+	On the Approximation Resistance of Balanced Linear Threshold Functions	2018	Aaron Potechin
+	Lengths of Words Accepted by Nondeterministic Finite Automata	2018	Aaron Potechin Jeffrey Shallit
+	Sum of squares lower bounds from symmetry and a good story	2017	Aaron Potechin
+	The power of sum-of-squares for detecting hidden structures	2017	Samuel B. Hopkins Pravesh K. Kothari Aaron Potechin Prasad Raghavendra Tselil Schramm David Steurer
+ PDF Chat	The Power of Sum-of-Squares for Detecting Hidden Structures	2017	Samuel B. Hopkins Pravesh K. Kothari Aaron Potechin Prasad Raghavendra Tselil Schramm David Steurer
+ PDF Chat	Bounds on Monotone Switching Networks for Directed Connectivity	2017	Aaron Potechin
+	Exact tensor completion with sum-of-squares	2017	Aaron Potechin David Steurer
+	Exact tensor completion with sum-of-squares	2017	Aaron Potechin David Steurer
+	A Note on Property Testing Sum of Squares and Multivariate Polynomial Interpolation	2017	Aaron Potechin Liu Yang
+	Sum of squares lower bounds from symmetry and a good story	2017	Aaron Potechin
+	Exact tensor completion with sum-of-squares	2017	Aaron Potechin David Steurer
+	The power of sum-of-squares for detecting hidden structures	2017	Samuel B. Hopkins Pravesh K. Kothari Aaron Potechin Prasad Raghavendra Tselil Schramm David Steurer
+	A Note on Amortized Space Complexity.	2016	Aaron Potechin
+	A Note on Amortized Branching Program Complexity	2016	Aaron Potechin
+ PDF Chat	A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem	2016	Boaz Barak Samuel B. Hopkins Jonathan A. Kelner Pravesh K. Kothari Ankur Moitra Aaron Potechin
+	Bounds on the Norms of Uniform Low Degree Graph Matrices	2016	Dhruv Medarametla Aaron Potechin
+	A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem	2016	Boaz Barak Samuel B. Hopkins Jonathan A. Kelner Pravesh K. Kothari Ankur Moitra Aaron Potechin
+	On the integrality gap of degree-4 sum of squares for planted clique	2016	Samuel B. Hopkins Pravesh K. Kothari Aaron Potechin Prasad Raghavendra Tselil Schramm
+	A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem.	2016	Boaz Barak Samuel B. Hopkins Jonathan A. Kelner Pravesh K. Kothari Ankur Moitra Aaron Potechin
+	Bounds on the Norms of Uniform Low Degree Graph Matrices	2016	Dhruv Medarametla Aaron Potechin
+	Graph Matrices: Norm Bounds and Applications	2016	Kwangjun Ahn Dhruv Medarametla Aaron Potechin
+	A Note on Amortized Branching Program Complexity	2016	Aaron Potechin
+	A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem	2016	Boaz Barak Samuel B. Hopkins Jonathan A. Kelner Pravesh K. Kothari Ankur Moitra Aaron Potechin
+	On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique	2015	Samuel B. Hopkins Pravesh K. Kothari Aaron Potechin Prasad Raghavendra Tselil Schramm
+ PDF Chat	Sum-of-squares Lower Bounds for Planted Clique	2015	Raghu Meka Aaron Potechin Avi Wigderson
+	Sum-of-squares lower bounds for planted clique	2015	Raghu Meka Aaron Potechin Avi Wigderson
+	SoS and Planted Clique: Tight Analysis of MPW Moments at all Degrees and an Optimal Lower Bound at Degree Four	2015	Samuel B. Hopkins Pravesh K. Kothari Aaron Potechin
+	Sum-of-squares lower bounds for planted clique	2015	Raghu Meka Aaron Potechin Avi Wigderson
+	A note on a problem of Erdos and Rothschild	2014	Aaron Potechin
+	A note on a problem of Erdos and Rothschild	2014	Aaron Potechin
+	Bounds on the Size of Sound Monotone Switching Networks Accepting Permutation Sets of Directed Trees	2013	Joshua Brakensiek Aaron Potechin
+	Improved upper and lower bound techniques for monotone switching networks for directed connectivity	2013	Aaron Potechin
+ PDF Chat	The Critical Group of a Line Graph	2012	Andrew Berget Andrew Manion Molly Maxwell Aaron Potechin Victor Reiner
+	Monotone switching networks for directed connectivity are strictly more powerful than certain-knowledge switching networks	2011	Aaron Potechin
+ PDF Chat	Bounds on Monotone Switching Networks for Directed Connectivity	2010	Aaron Potechin
+	Bounds on monotone switching networks for directed connectivity	2009	Aaron Potechin
+	The critical group of a line graph	2009	Andrew Berget Andrew Manion Molly Maxwell Aaron Potechin Victor Reiner
+	The critical group of a line graph	2009	Andrew Berget A. Manion Molly Maxwell Aaron Potechin Victor Reiner
+	Bounds on monotone switching networks for directed connectivity	2009	Aaron Potechin
+	Maximal caps in AG (6, 3)	2008	Aaron Potechin
+	Proof of Han's Hook Expansion Conjecture	2008	Kevin Carde Joe Loubert Aaron Potechin Adrian L. Sanborn

Common Coauthors

Coauthor	Papers Together
Pravesh K. Kothari	14
Samuel B. Hopkins	11
Goutham Rajendran	9
Neng Huang	7
David Steurer	6
Jeff Xu	6
Jonathan A. Kelner	5
Joshua Brakensiek	5
Prasad Raghavendra	5
Tselil Schramm	5
Ankur Moitra	5
Chris Jones	5
Boaz Barak	5
Uri Zwick	4
Avi Wigderson	3
Andrew Berget	3
Adam Kurpisz	3
Wenjun Cai	3
Raghu Meka	3
Chris Jones	3
Fernando Granha Jeronimo	3
Dhruv Medarametla	3
Victor Reiner	3
Elias Samuel Wirth	3
Molly Maxwell	3
Jeffrey Shallit	3
Madhur Tulsiani	2
Bohdan Kivva	2
Zelin Lv	2
Susanna F. de Rezende	2
Hing Yin Tsang	2
Andrew Manion	2
Kilian Risse	2
Mrinalkanti Ghosh	2
Ilias Diakonikolas	1
Kevin Carde	1
Adrian L. Sanborn	1
A. Manion	1
Jun-Ting Hsieh	1
C. A. Jones	1
Aaron Zhang	1
Liu Yang	1
Dominik Beck	1
Jeff L. Xu	1
Sushrut Karmalkar	1
Shuo Pang	1
Will Perkins	1
Mrinalkanti Ghosh	1
Joe Loubert	1
Elias Wirth	1

Commonly Cited References

Action	Title	Year	Authors	# of times referenced
+ PDF Chat	Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming	1995	Michel X. Goemans David P. Williamson	15
+	Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization	2000	Pablo A. Parrilo	11
+	Global Optimization with Polynomials and the Problem of Moments	2001	Jean B. Lasserre	10
+ PDF Chat	Sum-of-squares Lower Bounds for Planted Clique	2015	Raghu Meka Aaron Potechin Avi Wigderson	10
+ PDF Chat	Hypercontractivity, sum-of-squares proofs, and their applications	2012	Boaz Barak Fernando G. S. L. Brandão Aram W. Harrow Jonathan A. Kelner David Steurer Yuan Zhou	9
+ PDF Chat	A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem	2016	Boaz Barak Samuel B. Hopkins Jonathan A. Kelner Pravesh K. Kothari Ankur Moitra Aaron Potechin	8
+ PDF Chat	Rounding sum-of-squares relaxations	2014	Boaz Barak Jonathan A. Kelner David Steurer	8
+	Sum of squares lower bounds for refuting any CSP	2017	Pravesh K. Kothari Ryuhei Mori Ryan O’Donnell David Witmer	8
+ PDF Chat	Rounding Semidefinite Programming Hierarchies via Global Correlation	2011	Boaz Barak Prasad Raghavendra David Steurer	8
+ PDF Chat	Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method	2015	Boaz Barak Jonathan A. Kelner David Steurer	7
+	Sum-of-squares proofs and the quest toward optimal algorithms	2014	Boaz Barak David Steurer	7
+	Complexity Theoretic Lower Bounds for Sparse Principal Component Detection	2013	Quentin Berthet Philippe Rigollet	7
+ PDF Chat	Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes	2020	Mrinalkanti Ghosh Fernando Granha Jeronimo Chris Jones Aaron Potechin Goutham Rajendran	6
+	Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems	2015	Yash Deshpande Andrea Montanari	6
+	Graph Matrices: Norm Bounds and Applications	2016	Kwangjun Ahn Dhruv Medarametla Aaron Potechin	6
+ PDF Chat	The Power of Sum-of-Squares for Detecting Hidden Structures	2017	Samuel B. Hopkins Pravesh K. Kothari Aaron Potechin Prasad Raghavendra Tselil Schramm David Steurer	6
+	Lifting sum-of-squares lower bounds: degree-2 to degree-4	2020	Sidhanth Mohanty Prasad Raghavendra Jeff Xu	6
+ PDF Chat	Lower Bounds on the Size of Semidefinite Programming Relaxations	2015	James R. Lee Prasad Raghavendra David Steurer	6
+ PDF Chat	Sum of Squares Lower Bounds from Pairwise Independence	2015	Boaz Barak Siu On Chan Pravesh K. Kothari	6
+	An approach to obtaining global extremums in polynomial mathematical programming problems	1988	N. Z. Shor	4
+	How well do local algorithms solve semidefinite programs?	2017	Fan Zhou Andrea Montanari	4
+ PDF Chat	Polynomial-Time Tensor Decompositions with Sum-of-Squares	2016	Tengyu Ma Jonathan Shi David Steurer	4
+	An Explicit Exact SDP Relaxation for Nonlinear 0-1 Programs	2001	Jean B. Lasserre	4
+	Sum-of-Squares Lower Bounds for Sparse PCA	2015	Tengyu Ma Avi Wigderson	4
+	Tight Lower Bounds for Planted Clique in the Degree-4 SOS Program	2015	Prasad Raghavendra Tselil Schramm	4
+ PDF Chat	Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors	2016	Samuel B. Hopkins Tselil Schramm Jonathan Shi David Steurer	4
+	Tensor principal component analysis via sum-of-square proofs.	2015	Samuel B. Hopkins Jonathan Shi David Steurer	4
+	Sum-of-squares lower bounds for Sparse PCA	2015	Tengyu Ma Avi Wigderson	4
+	Undirected ST-connectivity in log-space	2005	Omer Reingold	4
+	SoS and Planted Clique: Tight Analysis of MPW Moments at all Degrees and an Optimal Lower Bound at Degree Four	2015	Samuel B. Hopkins Pravesh K. Kothari Aaron Potechin	4
+ PDF Chat	Finding a large hidden clique in a random graph	1998	Noga Alon Michael Krivelevich Benny Sudakov	4
+ PDF Chat	Strongly refuting random CSPs below the spectral threshold	2017	Prasad Raghavendra Satish Rao Tselil Schramm	4
+	On colouring random graphs	1975	Geoffrey Grimmett Colin McDiarmid	3
+	Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems.	2015	Yash Deshpande Andrea Montanari	3
+	Infinite Number of Order Parameters for Spin-Glasses	1979	Giorgio Parisi	3
+ PDF Chat	A new proof of Friedman's second eigenvalue theorem and its extension to random lifts	2020	Charles Bordenave	3
+ PDF Chat	Randomly Supported Independence and Resistance	2011	Per Austrin Johan Håstad	3
+	A nullstellensatz and a positivstellensatz in semialgebraic geometry	1974	Gilbert Stengle	3
+	Spectral norm of random tensors	2014	Ryota Tomioka Taiji Suzuki	3
+ PDF Chat	Expander flows, geometric embeddings and graph partitioning	2009	Sanjeev Arora Satish Rao Umesh Vazirani	3
+	Mixture models, robustness, and sum of squares proofs	2018	Samuel B. Hopkins Jerry Li	3
+ PDF Chat	Maximum independent sets on random regular graphs	2016	Jian Ding Allan Sly Nike Sun	3
+ PDF Chat	On independent sets in random graphs	2014	Amin Coja‐Oghlan Charilaos Efthymiou	3
+ PDF Chat	On Quadratic Threshold CSPs	2010	Per Austrin Siavosh Benabbas Avner Magen	3
+	Harald Cramér and the distribution of prime numbers	1995	Andrew Granville	3
+ PDF Chat	Finding Hidden Cliques in Linear Time with High Probability	2013	Yael Dekel Ori Gurel-Gurevich Yuval Peres	3
+ PDF Chat	Hidden Cliques and the Certification of the Restricted Isometry Property	2014	Pascal Koiran Anastasios Zouzias	3
+	Bounds on monotone switching networks for directed connectivity	2009	Aaron Potechin	3
+	On the integrality gap of degree-4 sum of squares for planted clique	2016	Samuel B. Hopkins Pravesh K. Kothari Aaron Potechin Prasad Raghavendra Tselil Schramm	3
+	Finding a large hidden clique in a random graph	1998	Noga Alon Michael Krivelevich Benny Sudakov	3