| 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 | 299 | 2019 |
| 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 | 172 | 2017 |
| 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 | 126 | 2015 |
| Exact tensor completion with sum-of-squares A Potechin, D Steurer Conference on Learning Theory, 1619-1673, 2017 | 84 | 2017 |
| Maximal caps in AG (6, 3) A Potechin Designs, Codes and Cryptography 46, 243-259, 2008 | 56 | 2008 |
| Sum-of-squares lower bounds for Sherrington-Kirkpatrick via planted affine planes M Ghosh, FG Jeronimo, C Jones, A Potechin, G Rajendran 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS …, 2020 | 55 | 2020 |
| 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), 1-31, 2018 | 50 | 2018 |
| The critical group of a line graph A Berget, A Manion, M Maxwell, A Potechin, V Reiner Annals of Combinatorics 16, 449-488, 2012 | 36 | 2012 |
| Sum-of-squares lower bounds for sparse independent set C Jones, A Potechin, G Rajendran, M Tulsiani, J Xu 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS …, 2022 | 33 | 2022 |
| 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 | 29 | 2012 |
| 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 | 26 | 2015 |
| Bounds on monotone switching networks for directed connectivity A Potechin 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 553-562, 2010 | 26 | 2010 |
| Graph matrices: Norm bounds and applications K Ahn, D Medarametla, A Potechin arXiv preprint arXiv:1604.03423, 2016 | 25 | 2016 |
| Machinery for proving sum-of-squares lower bounds on certification problems A Potechin, G Rajendran arXiv preprint arXiv:2011.04253, 2020 | 18 | 2020 |
| Lengths of words accepted by nondeterministic finite automata A Potechin, J Shallit Information Processing Letters 162, 105993, 2020 | 15 | 2020 |
| Bounds on the norms of uniform low degree graph matrices D Medarametla, A Potechin Approximation, Randomization, and Combinatorial Optimization. Algorithms and …, 2016 | 15 | 2016 |
| Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 sos B Kivva, A Potechin arXiv preprint arXiv:2011.09416, 2020 | 14 | 2020 |
| Sub-exponential time sum-of-squares lower bounds for principal components analysis A Potechin, G Rajendran Advances in Neural Information Processing Systems 35, 35724-35740, 2022 | 13 | 2022 |
| Sum-of-squares lower bounds for densest k-subgraph C Jones, A Potechin, G Rajendran, J Xu Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 84-95, 2023 | 12 | 2023 |
| A note on amortized branching program complexity A Potechin arXiv preprint arXiv:1611.06632, 2016 | 12 | 2016 |