Aaron Potechin
TitleCited byYear
A nearly tight sum-of-squares lower bound for the planted clique problem
B Barak, S Hopkins, J Kelner, PK Kothari, A Moitra, A Potechin
SIAM Journal on Computing 48 (2), 687-735, 2019
772019
Sum-of-squares lower bounds for planted clique
R Meka, A Potechin, A Wigderson
Proceedings of the forty-seventh annual ACM symposium on Theory of computing …, 2015
612015
Maximal caps in AG (6, 3)
A Potechin
Designs, Codes and Cryptography 46 (3), 243-259, 2008
352008
Exact tensor completion with sum-of-squares
A Potechin, D Steurer
arXiv preprint arXiv:1702.06237, 2017
322017
Tight bounds for monotone switching networks via Fourier analysis
SM Chan, A Potechin
Proceedings of the forty-fourth annual ACM symposium on Theory of computing …, 2012
282012
Bounds on monotone switching networks for directed connectivity
A Potechin
arXiv preprint arXiv:0911.0664, 2009
282009
On the integrality gap of degree-4 sum of squares for planted clique
SB Hopkins, P Kothari, AH Potechin, P Raghavendra, T Schramm
ACM Transactions on Algorithms (TALG) 14 (3), 28, 2018
252018
The power of sum-of-squares for detecting hidden structures
SB Hopkins, PK Kothari, A Potechin, P Raghavendra, T Schramm, ...
2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS …, 2017
252017
The critical group of a line graph
A Berget, A Manion, M Maxwell, A Potechin, V Reiner
Annals of Combinatorics 16 (3), 449-488, 2012
202012
Sos and planted clique: Tight analysis of MPW moments at all degrees and an optimal lower bound at degree four
SB Hopkins, PK Kothari, A Potechin
arXiv preprint arXiv:1507.05230, 2015
112015
Proof of Han's hook expansion conjecture
K Carde, J Loubert, A Potechin, A Sanborn
arXiv preprint arXiv:0808.0928, 2008
102008
Bounds on monotone switching networks for directed connectivity
A Potechin
Journal of the ACM (JACM) 64 (4), 29, 2017
62017
Bounds on the norms of uniform low degree graph matrices
D Medarametla, A Potechin
arXiv preprint arXiv:1604.03423, 2016
32016
Sum of squares lower bounds from symmetry and a good story
A Potechin
arXiv preprint arXiv:1711.11469, 2017
22017
A note on amortized space complexity
A Potechin
CoRR, abs/1611.06632, 2016
22016
Sum of squares bounds for the total ordering principle
A Potechin
arXiv preprint arXiv:1812.01163, 2018
12018
On the approximation resistance of balanced linear threshold functions
A Potechin
arXiv preprint arXiv:1807.04421, 2018
12018
A note on amortized branching program complexity
A Potechin
arXiv preprint arXiv:1611.06632, 2016
12016
Improved upper and lower bound techniques for monotone switching networks for directed connectivity
A Potechin
arXiv preprint arXiv:1302.3726, 2013
12013
Bounds on the size of sound monotone switching networks accepting permutation sets of directed trees
J Brakensiek, A Potechin
arXiv preprint arXiv:1301.3780, 2013
12013
The system can't perform the operation now. Try again later.
Articles 1–20