Li-Yang Tan: Unconditional Lower Bounds in Complexity Theory

Tuesday, December 8, 2015 - 4:00pm to 5:00pm
Refreshments: 
Light Refreshments at 3:50pm
Location: 
Patil/Kiva G449
Speaker: 
Li-Yang Tan
Abstract: I will present three recent results, each establishing new unconditional lower bounds in fundamental and well-studied models of computation: 
 
1. (Circuit Complexity) We prove an average-case depth hierarchy theorem for Boolean circuits, an average-case extension of the classical (worst-case) depth hierarchy theorem of Sipser, Yao, and Håstad. This resolves a main open problem in Håstad’s 1986 Ph.D. thesis. Via a classical connection between Boolean circuits and structural complexity, our circuit lower bound implies that the polynomial hierarchy is infinite relative to a random oracle, resolving a similarly longstanding conjecture of Håstad, Cai, and Babai from the 1980s. Joint work with Ben Rossman and Rocco Servedio (FOCS 2015). 
 
2. (Proof Complexity) We prove the first super-polynomial lower bounds against the "depth-d Frege" proof system for d = \Theta(\sqrt{\log n}). This is an exponential improvement of the work of Pitassi et al. (1993) and Krajicek et al. (1995), which gave super-polynomial lower bounds against depth-d Frege for d = \Theta(\log log n) and has stood as the state of the art for the past two decades. Joint work with Toni Pitassi, Ben Rossman, and Rocco Servedio. 
 
3. (Property Testing) We prove that any non-adaptive algorithm for testing whether an unknown Boolean function is monotone versus far-from-monotone must make essentially \Omega(\sqrt{n}) many queries. This is an exponential improvement of the previous \Omega(\log n) lower bound of Fischer et al. from 2002. Very recently, Khot et al. matched our lower bound with a \tilde{O}(\sqrt{n})-query non-adaptive tester, capping off almost two decades of work on this basic problem. Joint works with Xi Chen, Anindya De, and Rocco Servedio (FOCS 2014, STOC 2015). 
 
The common essential ingredient in the first two lower bounds is the method of random projections, a generalization of the classical method of random restrictions that has played a pivotal role in complexity theory. For the third lower bound, we build on and extend recently-developed multidimensional central limit theorems to analyze the success probability of property testing algorithms.