Hardness escalation in computational complexity theory

Speaker: Pritish Kamath , MIT

Date: Thursday, April 25, 2019

Time: 4:00 PM to 5:00 PM

Public: Yes

Location: 32-G449

Event Type: Thesis Defense

Room Description:

Host: Prof. Ronitt Rubinfeld

Contact: Joanne Talbot Hanley, 617-253-6054, joanne@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: 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.

Research Areas:

Impact Areas:

This event is not part of a series.

Created by Joanne Talbot Hanley Email at Tuesday, April 16, 2019 at 2:06 PM.