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.
Lecture notes for my fall 2017 SOS seminar at KTH are here
| 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 |