slideshow 3

Complexity seminar

XOR-KRW conjecture and composition of universal relation and a function

Ivan Mihajlin
Steklov Institute, Saint Petersburg


Friday, 4. June 2021 - 14:30 to 16:30

One of the major open problems in theoretic computer science is
showing the existence of a problem that could be solved in polynomial
time but not by a logarithmic depth circuit (P vs NC_1). One approach
that has a lot of progress in the last several years is to prove
Karchmer, Raz, and Wigderson conjecture. It states that there is no
better way to compute the composition of two functions than applying
them one by one.

In this talk, we will discuss the modification of KRW conjecture
called XOR-KRW. We will look at some partial results about the
composition of a universal relation with a function. We will also
discuss reasons to be optimistic about actually separating P and NC_1.