Department of Computer Science and the College
Aaron Potechin is broadly interested in discrete mathematics, particularly computational complexity theory. Much of his work is focused on proving lower bounds for particular computational models. He first encountered complexity theory in high school through the P versus NP problem. As an undergraduate in mathematics at Princeton University, he studied the complexity class L (logarithmic space), which led to his breakthrough work on monotone switching networks and monotone space complexity. For the past few years, he has studied the performance of the sum-of-squares hierarchy, a powerful and broadly applicable hierarchy of semidefinite programs. Among other results, he proved a breakthrough sum-of-squares lower bound on the planted clique problem.
His research has been published in ACM (Association for Computing Machinery) Transactions on Algorithms, Theory of Computing, Journal of the ACM, Annals of Combinatorics, and Designs, Codes, and Cryptography. His work has also been presented at numerous conferences, including FOCS (Foundations of Computer Science) 2017 and 2016, COLT (Conference on Learning Theory) 2017, and Computational Complexity Conference 2017.
Potechin holds a PhD in mathematics from the Massachusetts Institute of Technology and completed a joint postdoctoral fellowship between the Simons Collaboration on Algorithms and Geometry and the Institute for Advanced Study. Most recently, he was a postdoctoral fellow at the KTH Royal Institute of Technology in Sweden.