"A new approach to KRW conjecture "
Ivan Mikhailin (UCSD)
Monday March 30th 2-3pm
Zoom Meeting https://ucsd.zoom.us/my/csetheoryseminar
Abstract: One way to prove that NC1 does not contain P is by showing that the optimal way to compute the composition of functions is the naive one: compute one and then compute the other. This program was first presented by Karchmer, Raz, and Wigderson and is known by KRW conjecture. The conjecture looks particularly appealing when formulated in terms of lower bound on the depth of communication protocols for Karchmer-Wigderson games. Despite some early advances in the 90s, there was no particular progress in this area until a few years ago. We present a new approach with some immediate results. It relies on redefining what the composition of function is. We also show how to avoid certain technical difficulties that were plaguing potential ways to prove KRW conjecture by switching from normal communication to half-duplex communication.