I am broadly interested in discrete mathematics and particularly
interested in computational complexity theory. Much of my work is
on proving lower bounds for particular computational models; my
two biggest projects so far have been analyzing the performance of
the sum of squares hierarchy, a hierarchy of semidefinite programs
which is one of the most powerful tools known for combinatorial
optimization problems, and analyzing the power of monotone
switching networks, which are closely related to monotone space
I am currently a postdoc at KTH working with Johan Hastad, Jakob
Nordstrom, and Per Austrin. I will be joining the University of
Chicago's computer science department as an assistant professor in
Here is my current CV.
|A. Potechin and L. Yang. A Note on Property
Testing Sum of Squares and Multivariate Polynomial
Interpolation. Draft here,
will be posted to arXiv soon.
|S. Hopkins, P. Kothari, A. Potechin, P.
Raghavendra, T. Schramm, D. Steurer. The power of
sum-of-squares for detecting hidden structures. FOCS 2017.
Working draft here, will be
posted to arXiv soon.
|D. Steurer and A. Potechin. Exact tensor
completion with sum-of-squares. COLT 2017 https://arxiv.org/abs/1702.06237
|B. Barak, S. Hopkins, J. Kelner, P. Kothari,
A. Moitra, A. Potechin. A Nearly Tight Sum-of-Squares Lower
Bound for the Planted Clique Problem. FOCS 2016. https://arxiv.org/abs/1604.03084
|D. Medarametla, A. Potechin. Bounds on
the Norms of Uniform Low Degree Graph Matrices. RANDOM 2016.
|S. Hopkins. P. Kothari. A. Potechin. P.
Raghavendra. T. Schramm. On the Integrality Gap of Degree-4
Sum of Squares for Planted Clique. SODA 2016. Merge of https://arxiv.org/abs/1507.05230
|R. Meka, A. Potechin. A. Wigderson.
Sum-of-squares lower bounds for planted clique. STOC 2015. https://arxiv.org/abs/1503.06447
|J. Brakensiek, A. Potechin. Bounds on the
size of sound monotone switching networks accepting
permutation sets of directed trees
|A. Potechin. Improved upper and lower bound
techniques for monotone switching networks for directed
|S. Chan, A. Potechin. Tight bounds for
monotone switching networks via Fourier Analysis. Theory of
Computing Volume 10 (2014) Issue 15 p.389-419 https://eccc.hpi-web.de/report/2012/185/
|A. Potechin. Bounds on monotone switching
networks for directed connectivity. FOCS 2010 https://arxiv.org/abs/0911.0664
|A. Potechin. A note on amortized branching
program complexity. CCC 2017 https://arxiv.org/abs/1611.06632
|A. Potechin. A note on a problem of Erdos and
|A. Berget. A. Manion. M. Maxwell. A.
Potechin. V. Reiner. The critical group of a line graph.
Annals of Combinatorics Volume 16 (2012) Issue 3
|K. Carde. J. Loubert. A. Potechin. A.
Sanborn. Proof of Han's hook expansion conjecture. https://arxiv.org/abs/0808.0928
|A. Potechin. Maximal Caps in AG(6,3).
Designs, Codes, and Cryptography. Volume 46 (2008) Issue 3