Date & Time:
October 29, 2019 3:30 pm – 4:30 pm
Location:
Ryerson 251, 1100 E. 58th St., Chicago, IL,
10/29/2019 03:30 PM 10/29/2019 04:30 PM America/Chicago Mika Goos (IAS) – Automated Proof Search: The Aftermath Department of Mathematics & Computer Science Combinatorics & Theory Seminar Ryerson 251, 1100 E. 58th St., Chicago, IL,

Automated Proof Search: The Aftermath

In a breathtaking breakthrough, Atserias and Muller (FOCS'19, Best Paper)
settled the complexity of finding short proofs in Resolution, the most basic
propositional proof system. Namely, given an unsatisfiable CNF formula F, they
showed it is NP-hard to find a Resolution refutation of F in time polynomial in
the length of the shortest such refutation.

In this talk, we present a simple proof of the Atserias–Muller theorem.
The new proof generalises better: We obtain analogous hardness results for
Nullstellensatz, Polynomial Calculus, Sherali–Adams, and (with more work)
Cutting Planes. An open problem is to include Sum-of-Squares in this list.

Based on joint works with Sajin Koroth, Ian Mertz, Jakob Nordström, Toniann
Pitassi, Susanna de Rezende, Robert Robere, Dmitry Sokolov.

Host: Aaron Potechin

Mika Goos

Member, School of Mathematics, Institute for Advanced Studies

Mika Göös is a member of the School of Mathematics at the Institute for Advanced Study. Previously, he was a postdoctoral fellow in the Theory of Computing group at Harvard. He obtained his PhD from the University of Toronto (2016) under the supervision of Toniann Pitassi. He also holds an MSc from the University of Oxford (2011) and a BSc from Aalto University (2010). His research interests revolve around computational complexity theory.

Related News & Events

UChicago CS News

Federal budget cuts threaten to decimate America’s AI superiority—and other countries are watching

Feb 25, 2025
Netflix logo on phone screen
UChicago CS News

The Hidden Cost of Netflix’s Autoplay: A Study on Viewing Patterns and User Control

Feb 25, 2025
Raul Castro Fernandez
UChicago CS News

Raul Castro Fernandez among six UChicago scientists awarded prestigious Sloan Fellowships in 2025

Feb 18, 2025
UChicago CS News

Quantum Leap: New Research Reveals Secrets of Random Quantum Circuits

Feb 04, 2025
UChicago CS News

Fred Chong from the Department of Computer Science Named ACM Fellow for Contributions to Quantum Computing

Jan 22, 2025
UChicago CS News

Rethinking AI as a Thought Partner: Perspectives on Writing, Programming, and More

Jan 16, 2025
UChicago CS News

UChicago Partners On New National Science Foundation Large-Scale Research Infrastructure For Education

Dec 10, 2024
UChicago CS News

Saturdays with CSIL — How Undergraduates are Transforming CS Education for Local High School Students

Dec 05, 2024
UChicago CS News

UChicago Researchers Receive Google Privacy Faculty Award for Research on AI Privacy Risks

Nov 22, 2024
UChicago CS News

The Climate App Designed to Tackle Chatham’s Flooding Crisis

Nov 21, 2024
In the News

Globus Receives Multiple Honors in 2024 HPCwire Readers’ and Editors’ Choice Awards

Nov 20, 2024
In the News

Argonne Team Breaks New Ground in AI-Driven Protein Design

Nov 15, 2024
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