slideshow 3

Complexity seminar

The seminar takes place in the seminar room of IM, rear building, ground floor, Friday  at  14:00 - 16:00
Chair: Michal Koucky, Pavel Pudlak
The programme is announced via the mailing list.

Linear separation complexity of a random function

Pavel Hrubes
Friday, 18. March 2022 - 14:00 to 15:30

in IM, rear building, ground floor

Linear separation complexity of a Boolean function is a measure of how hard it is to distinguish accepting and rejecting inputs by means of a linear program. I will discuss nontrivial upper and lower bounds on separation complexity of a random function.

Joint work with Navid Talebanfard

Data structure lower bounds and popular conjectures

Michal Koucký
Friday, 11. March 2022 - 14:00 to 15:30

in IM, rear building, ground floor

We investigate the relative power of several conjectures that attracted
recently lot of interest. We establish a connection between the Network Coding
Conjecture (NCC) of Li and Li and several data structure like problems such as
non-adaptive function inversion of Hellman and the well-studied problem of
polynomial evaluation and interpolation. In turn these data structure problems
imply super-linear circuit lower bounds for explicit functions such as integer
sorting and multi-point polynomial evaluation.

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


Friday, 19. February 2021 - 14:30 to 16:30

in IM, rear building, ground floor

Apologies for the inconvenience.