[Colloquium] Theory Seminar

[Donna Brooms via Colloquium]

 The University of Chicago

Department of Computer Science & Mathematics

Combinatorics & Theory Seminar

 

Today, Tuesday, February 19, 2019

Ryerson 251 @ 3:30pm						



 							Robert Robere

                                       
DIMACS & IAS

http://www.cs.toronto.edu/~robere/

 

Title: “Lifting with Simple Gadgets and Applications for Cutting Planes”

 

Abstract: A recent line of work in complexity theory ("lifting theorems") analyze lower bounds in communication complexity by reducing them to lower bounds in query complexity, which is usually a much easier task. These techniques have proven to be very powerful, resolving a number of open problems. Further, due to known connections between communication, circuit, and proof complexity, these tools have (so far) been extremely successful in resolving a number of open problems in all of these areas. In this work, we strongly generalize an existing lifting theorem that reduces *monotone span program* lower bounds --- which is a circuit complexity measure --- to *Nullstellensatz degree* lower bounds --- which is a proof complexity measure. We apply our new lifting theorem to resolve several open problems in proof complexity and monotone circuit complexity, including: - an exponential separation between Cutting Planes proofs with *exponentially large coefficients* and Cutting Planes proofs with *polynomially bounded coefficients*, assuming the space is bounded - the first exponential-size separation between semantic Tree-Like Cutting planes with *exponentially large coefficients* and semantic Tree-Like Cutting Planes with *polynomially bounded coefficients", and - the first exponential-size separation between *monotone boolean formulas* and *monotone real formulas*, where the latter is a circuit model introduced by Krajicek that has played a key role in proof complexity. This is joint work with Susanna de Rezende, Or Meir, Jakob Nordstrom, Toniann Pitassi, and Marc Vinyals.

 Host: Prof. Aaron Potechin

(Refreshments will be served prior to the talk in Ry. 255 @ 3:15pm)

 


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20190219/185cfd97/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: clip_image001.jpg
Type: image/jpeg
Size: 2176 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20190219/185cfd97/attachment-0001.jpg>