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