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.
UChicago CS News

UChicago Hosts NSF Workshop on Frontiers of Quantum Advantage

Aug 15, 2022
UChicago CS News

New 2022-23 CS Faculty Add Expertise in Linguistics, Visualization, Economics, and Data Science Education

Aug 11, 2022
In the News

UChicago Co-Leads $10 Million NSF Institute on Foundations of Data Science

Aug 09, 2022
In the News

Bill Fefferman Comments on New Standards for Quantum-Proof Cryptography

Jul 07, 2022
UChicago CS News

UChicago London Colloquium Features Data Science, Quantum Research

Jul 01, 2022
Video

Is it Ethical to Use Facial Imaging in Decision-Making?

Jun 28, 2022
UChicago CS News

Single Sign-On Migration for Chameleon Project Receives PEARC Best Paper Award

Jun 27, 2022
UChicago CS News

Faculty Bill Fefferman and Chenhao Tan Receive Google Research Scholar Awards

Jun 21, 2022
UChicago CS News

DSI Summer Lab Returns In-Person With 49 Students From Across the U.S.

Jun 14, 2022
UChicago CS News

First-Year PhD Student Co-Authors Outstanding Paper Award Winner at TQC 2022

Apr 28, 2022
UChicago CS News

UChicago CS Labs Join Museum of Science & Industry For Robot Block Party

Apr 20, 2022
UChicago CS News

Three UChicago CS Security Projects Receive Funding From c3.ai Institute

Mar 25, 2022
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