About me:

I am an assistant professor in the Department of Computer Science at the University of Chicago. I am broadly interested in discrete mathematics and particularly interested in computational complexity theory. I love thinking about problems in my head and I am most driven when there is something I feel should be true and I am trying to figure out how to prove it, which is probably why I've been attracted to lower bounds like a moth to a flame. My current research is on the sum of squares hierarchy, a hierarchy of semidefinite programs which is one of the most powerful tools known for combinatorial optimization problems.

Contact info:

Email address: potechin at uchicago dot edu
Here is my current CV.

SOS course:

The course website for my fall 2018 class on SOS is here.
Lecture notes for the fall 2017 iteration of this course at KTH are here

Research on the sum of squares hierarchy:

A. Potechin. Sum of squares bounds for the total ordering principle. https://arxiv.org/abs/1812.01163
A. Potechin. Sum of squares lower bounds from symmetry and a good story. https://arxiv.org/abs/1711.11469
A. Potechin and L. Yang. A Note on Property Testing Sum of Squares and Multivariate Polynomial Interpolation. https://arxiv.org/abs/1709.03198
S. Hopkins, P. Kothari, A. Potechin, P. Raghavendra, T. Schramm, D. Steurer. The power of sum-of-squares for detecting hidden structures. FOCS 2017. https://arxiv.org/abs/1710.05017
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
Talk slides
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 and https://arxiv.org/abs/1507.05136
R. Meka, A. Potechin. A. Wigderson. Sum-of-squares lower bounds for planted clique. STOC 2015. https://arxiv.org/abs/1503.06447

Research on proving monotone space lower bounds via the switching network model:

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 connectivity
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. JACM Volume 64, Issue 4 Article No. 29, 2017 https://arxiv.org/abs/0911.0664

Other research:

A. Potechin. On the approximation resistance of balanced linear threshold functions. https://arxiv.org/abs/1807.04421
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 Rothschild. https://arxiv.org/abs/1412.1838
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 p.449-488  https://arxiv.org/abs/0904.1246
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 p.243-259