• Ivan Mihajlin
    • (Steklov Institute, Saint Petersburg)
    • XOR-KRW 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 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.
    • 04.06.21   14:30
    • n/a
    • (n/a)
    • Abstract:
    • Apologies for the inconvenience.
    • 19.02.21   14:30

    Michal Koucky, Pavel Pudlak