Back to TGINF

# ACC lower bounds for NQP

Speaker: Chi-Ning
Title: ACC lower bounds for NQP
Date: 09 Jul 2018 5:30pm-7:00pm
Location: MD 221
Food: Thai food
Audience background:
Talk style:

Abstract: In 2011, Williams proved the seminal ACC0 lower bound for NEXP and open the new approach of proving circuit lower bound from circuit satisfiability algorithm. One of the key step of the connection between lower bound and algorithm is the easy witness lemma introduced by Impagliazzo, Kabanets, and Wigderson in 2002 for NE. In this paper, Murray and Williams prove easy witness lemma for lower bound nondeterministic time classes such as NQP and thus result in ACC lower bound these two classes.

In this talk, we will first explain the connection between circuit lower bound and satisfiability algorithm especially on how easy witness lemma plays an important role here. If time allows, we will sketch the proof of the original easy witness lemma by IKW and point out which parts of the proof broke down and were fixed by Murray and Williams.