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

Michael Franklin
UChicago CS News

Mike Franklin, Dan Nicolae Receive 2023 Arthur L. Kelly Faculty Prize

Jun 02, 2023
UChicago CS News

Computer Science Class Shows Students How To Successfully Create Circuit Boards Without Engineering Experience

May 17, 2023
UChicago CS News

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

May 16, 2023
UChicago CS News

CS Chair Michael Franklin Elected to the American Academy of Arts & Sciences

Apr 28, 2023
UChicago CS News

UChicago CS Researchers Shine at CHI 2023 with 12 Papers and Multiple Awards

Apr 19, 2023
UChicago CS News

New Prototypes AeroRigUI and ThrowIO Take Spatial Interaction to New Heights – Literally

Apr 18, 2023
UChicago CS News

PhD Student Kevin Bryson Receives NSF Graduate Research Fellowship to Create Equitable Algorithmic Data Tools

Apr 14, 2023
UChicago CS News

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

Apr 07, 2023
UChicago CS News

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

Apr 03, 2023
UChicago CS News

UChicago, Stanford Researchers Explore How Robots and Computers Can Help Strangers Have Meaningful In-Person Conversations

Mar 29, 2023
UChicago CS News

Virtual Bakery Game Serves Up Both Cupcakes and Quantum Concepts For K-12 Students

Mar 27, 2023
Students posing at competition
UChicago CS News

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

Mar 17, 2023
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