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
IM CAS
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ý
MFF UK
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

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

CANCELLED

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

in IM, rear building, ground floor

Apologies for the inconvenience.

Pages