
Ivan Mihajlin
 (Steklov Institute, Saint Petersburg)

XORKRW conjecture and composition of universal relation and a function

Abstract:

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 XORKRW. 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.

n/a
 (n/a)

CANCELLED

Abstract:

Apologies for the inconvenience.
Michal Koucky, Pavel Pudlak
organizers