Hardness escalation in computational complexity theory
Date: Thursday, April 25, 2019
Time: 4:00 PM to 5:00 PM
Event Type: Thesis Defense
Host: Prof. Ronitt Rubinfeld
Contact: Joanne Talbot Hanley, 617-253-6054, firstname.lastname@example.org
Speaker URL: None
TALK: Thesis Defense: Pritish Kamath "Hardness escalation in computational complexity theory," April 25, 2019 at 4pm
Abstract: We prove new "hardness escalation" results in computational complexity theory; a phenomenon where hardness results against seemingly weak models of computation for any problem can be "lifted" in a completely black box manner, to much stronger models of computation by studying a simple gadget composed version of the original problem.
In particular, we will show how lower bounds against the "resolution proof system" can be transformed into lower bounds on the size of "monotone circuits" and the "cutting planes proof system" (all these notions will be defined in the talk). The key point here is that resolution is a significantly weak proof system for which many hardness results are known. On the other hand, there have only been a limited set of techniques to prove lower bounds against monotone circuits and cutting planes proof system. A new result that follows from this approach is that monotone circuits cannot perform Gaussian elimination efficiently; this yields the first exponential monotone circuit size lower bound for a very simple monotone function that is computable by poly-size poly-log-depth non-monotone circuits.
Finally, we describe an intimate connection of these results to the complexity class TFNP, the class of all efficiently verifiable "total" search problems. In particular, we will demonstrate equivalences between computational models and communication complexity analogues of sub-classes of TFNP. The hardness escalation results that we describe (and some others in literature) can thus be viewed as "query-to-communication lifting" theorems for these sub-classes of TFNP.
Created by Joanne Talbot Hanley at Tuesday, April 16, 2019 at 2:06 PM.