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.
Video

Nightshade: Data Poisoning to Fight Generative AI with Ben Zhao

Jan 23, 2024

Research Suggests That Privacy and Security Protection Fell To The Wayside During Remote Learning

A qualitative research study conducted by faculty and students at the University of Chicago and University of Maryland revealed key...
Oct 18, 2023

UChicago Researchers Win Internet Defense Prize and Distinguished Paper Awards at USENIX Security

Sep 05, 2023

Chicago Public Schools Student Chris Deng Pursues Internet Equity with University of Chicago Faculty

May 16, 2023

Computer Science Displays Catch Attention at MSI’s Annual Robot Block Party

Apr 07, 2023

UChicago / School of the Art Institute Class Uses Art to Highlight Data Privacy Dangers

Apr 03, 2023
Students posing at competition

UChicago Undergrad Team Places Second Overall In Regionals For World’s Largest Programming Competition

Mar 17, 2023
Young students on computers

UChicago and NYU Research Team Finds Edtech Tools Could Pose Privacy Risks For Students

Feb 21, 2023

UChicago Scientists Develop New Tool to Protect Artists from AI Mimicry

Feb 13, 2023

Professors Rebecca Willett and Ben Zhao Discuss the Future of AI on Public Radio

Jan 26, 2023

Professor Heather Zheng Named ACM Fellow

Jan 18, 2023

Professor Fred Chong Named IEEE Fellow

Dec 09, 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