Aaron Potechin, Expert in Complexity Theory, Joins UChicago CS as Asst. Professor
While applied computer scientists do the research behind tomorrow’s technology, theoretical computer scientists are already mapping out the boundaries of the day after tomorrow. CS theory bridges mathematics and the broad array of tasks computers execute in the modern world — analysis, learning, security, and beyond — by investigating what is mathematically possible for us to compute.
Aaron Potechin, a new assistant professor who joined the department this summer, is the latest addition to the long and storied history of theoretical CS at the University of Chicago. In Potechin’s sub-field of computational complexity theory, researchers study just how difficult it is to solve a particular computational problem, searching for its speed limits and resource demands.
“In math, as in life, we have all kinds of problems,” Potechin said. “In complexity theory, we look at you solving that problem, and we think about questions like how long will it take you, how much paper are you going to need. Or for a computer, how many steps does it take, how much memory does it need, and so on.”
At recent postdoctoral appointments with the KTH Royal Institute of Technology in Sweden, the Simons Collaboration on Algorithms and Geometry at Cornell University and the Institute for Advanced Study, Potechin has focused on the sum-of-squares hierarchy. Based upon the simple algebraic principle that all squares of real numbers are non-negative, sum-of-squares is broadly applicable to a range of computational problems. It can be applied to any system of polynomial equations, and captures the best-known algorithm for several problems including max cut, sparsest cut and unique games.
Other aspects of Potechin’s research involve the search for lower bounds — the theoretical “speed limits” for a particular computational model. Lower bounds are important because they improve our understanding of what our models can and cannot do. This helps theorists determine whether we should keep searching for a better algorithm or we have already found the best possible algorithm.
“A lower bound is an impossibility statement. It's saying no matter how clever you are, no matter what you come up with, you can't do better than this,“ Potechin said. “In order to prove lower bounds, you have to really understand the model you’re working with. I'm very driven when there's something which I feel should be true and don't know how to prove it, and that's a very common situation in lower bounds.”
In joining UChicago CS, Potechin adds to a strong cohort of complexity theorists, including Alexander Razborov, Ketan Mulmuley, Laszlo Babai, Janos Simon, Andy Drucker, and Madhur Tulsiani.
