Proving super-logarithmic lower bounds on the depth of circuits (i.e., P \neq NC^1) is one of the main frontiers of circuit complexity.
In 1991, Karchmer, Raz and Wigderson observed that we could resolve this question by proving the following conjecture: Given two non-constant boolean functions f, g, the depth complexity of their composition is approximately equal to the sum of their individual depth complexities.
Several works have made progress towards resolving this conjecture by proving it for every outer function f, but only when composed with two specific inner functions g. In this talk, I will present a recent result that extends the range of inner functions that can be handled to include any function g whose depth complexity can be lower bounded via a certain lifting theorem. Based on a joint work with Or Meir, Jakob Nordstrom, Toniann Pitassi, and Robert Robere.
published by Navid Talebanfard on Tue, 17/11/2020 - 22:12
