slideshow 3

Complexity seminar

usually takes place each Friday at 13:30 in IM, rear building, ground floor
Chair: Michal Koucky, Pavel Pudlak
The programme is announced via the mailing list.

Matroids, 3-regular graphs and random restrictions

Pavel Pudlák
IM, CAS
Friday, 11. May 2018 - 13:30 to 15:00

in IM, rear building, ground floor

I will show some connections between matroids and random restrictions of Tseitin tautologies on 3-regular graphs. In particular I will show that the domains of the restrictions are flats in a matroid that is dual to a bicircular matroid. I will pose several problems concerning how these facts can be generalized to other kinds of restrictions and other graphs. This talk will be a sort of a continuation of Navid's, but I will recall everything that is needed.

Half-duplex communication complexity

Alexander V. Smal
Steklov Math. Inst., St. Petersburg
Friday, 4. May 2018 - 13:30 to 15:00

in IM, rear building, ground floor

Suppose Alice and Bob are communicating bits to each other in order to compute some function f but instead of a classical communication channel they have a pair of walkie-talkie devices. They can use some classical communication protocol for f where each round one player sends bit and the other one receives it. The question is whether talking via walkie-talkie gives them more power? Using walkie-talkie instead of a classical communication channel allows players two extra possibilities: to speak simultaneously (but in this case they do not hear each other) and to listen at the same time (but in this case they do not transfer any bits). We show that for some definitions this non-classical communication model is in fact more powerful than the classical one as it allows to compute some functions in smaller number of rounds. We also introduce round elimination technique for proving lower bounds in this setting and use it to prove lower bounds for some Boolean functions. Join... more

Complexity meets Computability: Connections between Computational Complexity Theory and the Kolmogorov Random Strings

Eric Allender
Rutgers University
Friday, 27. April 2018 - 13:30 to 15:00

in IM, rear building, ground floor

In this talk, I will survey some results (some dating back more than a decade) indicating that certain computational complexity classes can be characterized in terms of efficient reducibility to the (undecidable) set of Kolmogorov-random strings.  There have been a few new developments, and there are a lot of open questions. Some of the main results in this line of research: Let U be a universal Turing machine, and let R_U be {x : K_U(x) is at least |x|}.  That is, R_U is the set of Kolmogorov-random strings, when K-complexity is defined using universal machine U. When we write "R" instead of "R_U" in statement, it will mean that the statement holds for EVERY universal machine U.  Let P_tt(A) denote the class of sets that are polynomial-time non-adaptively reducible to A (also known as the class of sets that are polynomial-time truth-table reducible to A).  Let P(A) denote the class of sets that are poly-time Turing-reducible to A. Theorem:... more

Random 3-regular graphs from random 3-regular graphs

Navid Talebanfard
IM CAS
Friday, 23. March 2018 - 13:30 to 15:00

in IM, rear building, ground floor

Given a 3-regular graph we define a natural process which gives a random topological minor of this graph. We show that if the original graph is uniformly distributed, so is the resulting topological minor over the space of 3-regular graphs of the same size. Based on ongoing work with Pavel Pudlák and Neil Thapen.

Pages