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
Friday, 16. October 2020 - 14:30 to 16:30

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
Friday, 2. October 2020 - 14:30 to 16:30

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