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.

Related News

More UChicago CS stories from this research area.
In the News

Quanta Magazine Features Prof. Bill Fefferman’s Work on Quantum Algorithms

Jan 20, 2022
UChicago CS News

UChicago CS Prof. Ben Zhao Named ACM Fellow

Jan 19, 2022
UChicago CS News

CS 4th Year Sophie Veys Receives CRA Undergraduate Research Award

Jan 14, 2022
UChicago CS News

In-Fridge Controller Could Scale Up Quantum Computers, Award-Winning UChicago Research Finds

Jan 10, 2022
UChicago CS News

UChicago Workshop Highlights Internet Frontiers and Opportunities

Dec 02, 2021
In the News

Asst. Prof. Blase Ur Discusses the “Metaverse” on Chicago Tonight

Nov 05, 2021
UChicago CS News

EPiQC Research Receives Best Paper Award at IEEE Quantum Week

Oct 22, 2021
UChicago CS News

UChicago and EPiQC Alum Yongshan Ding Joins Yale in Faculty Position

Oct 08, 2021
UChicago CS News

Five UChicago CS Students Named to Siebel Scholars 2022 Class

Sep 23, 2021
UChicago CS News

Trio of New UChicago CS Faculty Join for 2021-22 Academic Year

Sep 16, 2021
UChicago CS News

UChicago Researchers Excel in IBM Quantum Open Science Challenge

Jul 30, 2021
UChicago CS News

Largest-Ever DSI Summer Lab Adds 55 Students, New Social Impact Track

Jul 13, 2021
arrow-down-largearrow-left-largearrow-right-large-greyarrow-right-large-yellowarrow-right-largearrow-right-smallbutton-arrowclosedocumentfacebookfacet-arrow-down-whitefacet-arrow-downPage 1CheckedCheckedicon-apple-t5backgroundLayer 1icon-google-t5icon-office365-t5icon-outlook-t5backgroundLayer 1icon-outlookcom-t5backgroundLayer 1icon-yahoo-t5backgroundLayer 1internal-yellowinternalintranetlinkedinlinkoutpauseplaypresentationsearch-bluesearchshareslider-arrow-nextslider-arrow-prevtwittervideoyoutube