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.

Combinatorial miniatures from low depth complexity, chapter one

Navid Talebanfard
Institute of Mathematics, CAS
Friday, 23. October 2020 - 14:30 to 16:30
In what is hopefully going to be a series of talks, I will survey very natural extremal combinatorial questions arising from complexity theory. I will point out several questions and report some progress. In the first chapter we will look at a relaxation of VC dimension and prove a Sauer-Shelah type theorem.

Tree codes - recent progress

Pavel Pudlak
IM
Friday, 16. October 2020 - 14:30 to 16:30

https://cesnet.zoom.us/j/94887138486?pwd=SkZLUkdYUGlHU3ZiV0E5MjBqbTBaQT09

password: zeno

The problem of finding an explicit construction of good tree codes over a constant size alphabet is still open. In this talk I will explain the problem and mention some recent results and proposed approaches to this problem.

Bare quantum simultaneity versus classical interactivity in communication complexity

Dmitry Gavinsky
IM, CAS
Friday, 2. October 2020 - 14:30 to 16:30

https://cesnet.zoom.us/j/98453959650?pwd=TEpEbjNqYThDQzFaSHhxNEhZcEFVUT09

The password is the last name in small case of the famed British mathematician, the founder of computability theory.

We shall see a relational problem that is easy for the weakest quantum model of communication – simultaneous message passing (without shared resources); at the same time, the problem is difficult for the strongest classical model – interactive (two-way) communication.

Super Strong ETH is true for strong PPSZ

Navid Talebanfard
IM, CAS
Friday, 24. April 2020 - 13:30 to 15:00
Super Strong ETH states that there is no k-SAT algorithm with running time
2^(1 - f_k)m where f_k >> 1/k. We prove that this hypothesis is true for
the strong version of the PPSZ algorithm. Previously such a bound was
known only for the weak version of PPSZ. Our construction is based on a
modification of satisfiable Tseitin formulas over a certain class of high
girth... more

Pages