Date & Time:
February 19, 2019 3:30 pm – 4:30 pm
Location:
Ryerson 251, 1100 E. 58th St., Chicago, IL,
02/19/2019 03:30 PM 02/19/2019 04:30 PM America/Chicago Robert Robere (Rutgers) – Lifting with Simple Gadgets and Applications for Cutting Planes Ryerson 251, 1100 E. 58th St., Chicago, IL,

Lifting with Simple Gadgets and Applications for Cutting Planes

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: Aaron Potechin

Card Image 741424f

Robert Robere

Postdoctoral Researcher, Rutgers University and the Institute for Advanced Study

I am a postdoctoral researcher jointly appointed between DIMACS at Rutgers University (January-August 2019) and the Institute for Advanced Study in Princeton (September 2019-August 2020). Prior to this, I was a research fellow in the Lower Bounds program at the Simons Institute for the Theory of Computing at UC Berkeley.

I received my PhD from the University of Toronto, where I was a member of the DCS Theory Group under the supervision of Toni Pitassi and Stephen Cook.

My primary area of research is computational complexity theory, with an emphasis in circuit complexity, proof complexity, communication complexity, and related topics. I also have a deep interest in the theory and practice of SAT solving and model checking.

Related News & Events

Card Image af1a746
Card Image
UChicago CS News

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

Card Image b332a15
Card Image
UChicago CS News

New CS and DSI Faculty Haifeng Xu Brings Strategic Intelligence to NeurIPS 2022

Card Image bcae520
Card Image
UChicago CS News

UChicago CS Research Finds New Angle on Database Query Processing with Geometry

Card Image b5ae273
Card Image
UChicago CS News

Asst. Prof. Aloni Cohen Receives Award For Revealing Flaws in Deidentifying Data

Card Image daaa4c0
Card Image
UChicago CS News

UChicago Hosts NSF Workshop on Frontiers of Quantum Advantage

Card Image 0958a21
Card Image
UChicago CS News

New 2022-23 Faculty Add Expertise in Linguistics, Visualization, Economics, and Data Science Education

Card Image 5f2650c
Card Image
In the News

UChicago Co-Leads $10 Million NSF Institute on Foundations of Data Science

Card Image b698e70
Card Image
In the News

Bill Fefferman Comments on New Standards for Quantum-Proof Cryptography

Card Image 2f10e5b
Card Image
UChicago CS News

UChicago London Colloquium Features Data Science, Quantum Research

Card Image 3cc4a0f
Card Image
UChicago CS News

Faculty Bill Fefferman and Chenhao Tan Receive Google Research Scholar Awards

Card Image f20f6d2
Card Image
UChicago CS News

First-Year PhD Student Co-Authors Outstanding Paper Award Winner at TQC 2022

Card Image 9e6a76a
Card Image
In the News

Quanta Magazine Features Prof. Bill Fefferman’s Work on Quantum Algorithms

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