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

https://cesnet.zoom.us/j/91685914606?pwd=Z2tSd3l1UUJ4RHhNV2VkWnc1ZXltZz09

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.

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.