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.

KTH email address: apote at kth dot se

UChicago email address: potechin at cs dot uchicago dot edu

Here is my current CV.

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. FOCS 2010 https://arxiv.org/abs/0911.0664 |

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 |