Paper List

Papers

On the second moment of the determinant of random symmetric, Wigner, and Hermitian matrices. Dominik Beck, Zelin Lv, and Aaron Potechin. arXiv

Hardness of sampling for the anti-ferromagnetic Ising model on random graphs. Neng Huang, Will Perkins, and Aaron Potechin. arXiv

On induced subgraphs of H(n,3) with maximum degree 1. Aaron Potechin and Hing Yin Tsang. arXiv

Sum-of-Squares Lower Bounds for Non-Gaussian Component Analysis. Ilias Diakonikolas, Sushrut Karmalkar, Shuo Pang, and Aaron Potechin. FOCS 2024.

Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs. Pravesh Kothari, Aaron Potechin, and Jeff Xu. STOC 2024. arXiv

Clique Is Hard on Average for Unary Sherali-Adams. Susanna F. de Rezende, Aaron Potechin, and Kilian Risse. FOCS 2023. arXiv

Separating MAX 2-AND, MAX DI-CUT and MAX CUT. Joshua Brakensiek, Neng Huang, Aaron Potechin, and Uri Zwick. FOCS 2023. arXiv

Ellipsoid Fitting Up to a Constant. Jun-Ting Hsieh, Pravesh Kothari, Aaron Potechin, and Jeff Xu. ICALP 2023. arXiv

Near-optimal fitting of ellipsoids to random points. Aaron Potechin, Paxton Turner, Prayaag Venkat, and Alex Wein. COLT 2023. arXiv

Sum-of-squares lower bounds for densest k-subgraph. Chris Jones, Aaron Potechin, Goutham Rajendran, and Jeff Xu. STOC 2023. arXiv

The Sixth Moment of Random Determinants. Dominik Beck, Zelin Lv, and Aaron Potechin. Journal of Integer Sequences, Vol. 26, Article 23.6.3. 2023. arXiv

On Mixing Distributions Via Random Orthogonal Matrices and the Spectrum of the Singular Values of Multi-Z Shaped Graph Matrices. Wenjun Cai and Aaron Potechin. arXiv

Bounds on the Total Coefficient Size of Nullstellensatz Proofs of the Pigeonhole Principle and the Ordering Principle. Aaron Potechin and Aaron Zhang. ICALP 2024. arXiv

Almost-Orthogonal Bases for Inner Product Polynomials. Chris Jones and Aaron Potechin. ITCS 2022. arXiv

Expander Random Walks: The General Case and Limitations. Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, and Amnon Ta-Shma. ICALP 2022. ECCC

Sum-of-Squares Lower Bounds for Sparse Independent Set. Chris Jones, Aaron Potechin, Goutham Rajendran, Madhur Tulsiani, and Jeff Xu. FOCS 2021. arXiv

SoS certification for symmetric quadratic functions and its connection to constrained Boolean hypercube optimization. Adam Kurpisz, Aaron Potechin, and Elias Samuel Wirth. ICALP 2021. arXiv

Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 SOS. Bohdan Kivva and Aaron Potechin. arXiv

Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems. Aaron Potechin and Goutham Rajendran. arXiv
Note: A version of this paper, "Sub-exponential time Sum-of-Squares lower bounds for Principal Components Analysis", appeared in NeurIPS 2022.

On the Mysteries of MAX NAE-SAT. Joshua Brakensiek, Neng Huang, Aaron Potechin, and Uri Zwick. SODA 2021. arXiv

Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes. Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones, Aaron Potechin, Goutham Rajendran. FOCS 2020. arXiv

The Spectrum of the Singular Values of Z-Shaped Graph Matrices. Wenjun Cai and Aaron Potechin. arXiv

A Conjecture on Induced Subgraphs of Cayley Graphs. Aaron Potechin and Hing Yin Tsang. arXiv
Note: Our conjecture was quickly refuted, see this paper.

Graph Matrices: Norm Bounds and Applications. Kwangjun Ahn, Dhruv Medarametla, and Aaron Potechin. arXiv
Note: This is a major update of the paper "Bounds on the Norms of Uniform Low Degree Graph Matrices." which appeared in RANDOM 2016. This paper now handles graph matrices with hyperedges and different types of vertices. We also handle general input distributions and show how graph matrices can be used to simplify the proofs of several technical lemmas in other papers.

On the Approximability of Presidential Type Predicates. Neng Huang and Aaron Potechin. APPROX 2020. arXiv

Sum of squares bounds for the ordering principle. Aaron Potechin. CCC 2020. arXiv

On the approximation resistance of balanced linear threshold functions. Aaron Potechin. STOC 2019. arXiv

Lengths of Words Accepted by Nondeterministic Finite Automata. Aaron Potechin and Jeffrey Shallit. Information Processing Letters Volume 162, October 2020. arXiv

Sum of squares lower bounds from symmetry and a good story. Aaron Potechin. ITCS 2019. arXiv

A Note on Property Testing Sum of Squares and Multivariate Polynomial Interpolation. Aaron Potechin and Liu Yang. arXiv

The power of sum-of-squares for detecting hidden structures. Sam Hopkins, Pravesh Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer. FOCS 2017. arXiv

Exact tensor completion with sum-of-squares. Aaron Potechin and David Steurer. COLT 2017. arXiv

A note on amortized branching program complexity. Aaron Potechin. CCC 2017. arXiv

A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. Boaz Barak, Sam Hopkins, Jonathan Kelner, Pravesh Kothari, Ankur Moitra, and Aaron Potechin. FOCS 2016. arXiv

On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique. Sam Hopkins, Pravesh Kothari, Aaron Potechin, Prasad Raghavendra, and Tselil Schramm. SODA 2016. This paper merges https://arxiv.org/abs/1507.05230 and https://arxiv.org/abs/1507.05136.

Sum-of-squares lower bounds for planted clique. Raghu Meka, Aaron Potechin, and Avi Wigderson. STOC 2015. arXiv

A note on a problem of Erdos and Rothschild. Aaron Potechin. arXiv

Bounds on the size of sound monotone switching networks accepting permutation sets of directed trees. Joshua Brakensiek and Aaron Potechin. arXiv

Improved upper and lower bound techniques for monotone switching networks for directed connectivity. Aaron Potechin. arXiv

Tight bounds for monotone switching networks via Fourier Analysis. Siu Man Chan and Aaron Potechin. Theory of Computing Volume 10 (2014) Issue 15 p.389-419. ECCC

Bounds on monotone switching networks for directed connectivity. Aaron Potechin. JACM Volume 64, Issue 4 Article No. 29, 2017. arXiv

The critical group of a line graph. Andrew Berget, Andrew Manion, Molly Maxwell, Aaron Potechin, and Victor Reiner. Annals of Combinatorics Volume 16 (2012) Issue 3 p.449-488. arXiv

Proof of Han's hook expansion conjecture. Kevin Carde, Joe Loubert, Aaron Potechin, and Adrian Sanborn. arXiv

Maximal Caps in AG(6,3). Aaron Potechin. Designs, Codes, and Cryptography. Volume 46 (2008) Issue 3 p.243-259.