About me:

I am a new 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. My current research is on the sum of squares hierarchy, a hierarchy of semidefinite programs which is broadly applicable, surprisingly powerful, and in some sense simple as at its heart all the sum of squares hierarchy is using is basic algebra and the fact that squares are non-negative over the real numbers.

I have several research problems in mind both on the sum of squares hierarchy and on other topics and I am currently looking for students.

Contact info:

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

SOS seminar lecture notes:

Lecture notes for my fall 2017 SOS seminar at KTH are here

Research on the sum of squares hierarchy:

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