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

UChicago Partners With UMass On NSF Expedition To Elevate Computational Decarbonization As A New Field In Computing

May 23, 2024
UChicago CS News

Assistant Professor Raul Castro Fernandez Awarded NSF CAREER Grant to investigate Data-sharing Markets

May 21, 2024
UChicago CS News

Empowering Middle School Girls in Tech: compileHER’s <prompt/HER> Capstone Event

May 20, 2024
UChicago CS News

Haifeng Xu Wins Best Paper Award at Leading AI Conference for Pioneering Research on Mechanism Design for LLMs

May 17, 2024
UChicago CS News

Fred Chong Receives Quantrell Award for Excellence in Teaching

May 16, 2024
UChicago CS News

Unveiling Attention Receipts: Tangible Reflections on Digital Consumption

May 15, 2024
UChicago CS News

NASA to Launch UChicago Undergraduates’ Satellite

May 14, 2024
UChicago CS News

University of Chicago Computer Science Researchers To Present Ten Papers at CHI 2024

May 06, 2024
UChicago CS News

Two UChicago MPCS Students Win the Apple Swift Student Challenge

May 01, 2024
In the News

How Artificial Intelligence Can Transform U.S. Energy Infrastructure

Apr 29, 2024
In the News

Community Data Fellow Stephania Tello Zamudio helps broaden internet access for Illinois residents

Apr 29, 2024
UChicago CS News

Two UChicago CS Students Awarded NSF Graduate Research Fellowship

Apr 24, 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