About me:

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 complexity.

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 July 2018.

Contact info:

Email address: aaronpotechin at gmail dot com (recommended for now)
UChicago email address: potechin at cs dot uchicago dot edu

Here is my current CV.

Research on the sum of squares hierarchy:

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
Talk slides
D.  Medarametla, A. Potechin. Bounds on the Norms of Uniform Low Degree Graph Matrices. RANDOM 2016.
https://arxiv.org/abs/1604.03423
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
https://arxiv.org/abs/1301.3780
A. Potechin. Improved upper and lower bound techniques for monotone switching networks for directed connectivity
https://arxiv.org/abs/1302.3726
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

Other research:

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