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
... more
Complexity seminar
The seminar takes place in the seminar room of IM, rear building, ground floor, Friday at 14:00 - 16:00Chair: Michal Koucky, Pavel Pudlak
The programme is announced via the mailing list.
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
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... 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.
Graphons as weak* limits
Jan Hladký
IM CAS
Friday, 19. January 2018 - 13:30 to 15:00
in IM, rear building, ground floor
Around 2004, Lovasz and Szegedy came up with a certain compactification of the space of finite graphs.
More precisely, they proved that there exists a metric - now called the cut-distance - which yields a
compact topology. Their proof of compactnes relies on the Szemeredi regularity lemma. An entire theory,
with applications in extremal graph theory and random graphs, developed from this statement. I will
talk about approaching the cut-norm topology via the weak* topology. This approach gives a new view of
many properties, and in particular yields a quick and elementary proof of the Lovasz-Szegedy theorem.
The talk will be self-contained. Various bits of this are joint work with Martin Dolezal, Jan Grebik,
Jon Noel, Diana Piguet, Israel Rocha, Vaclav Rozhon, Maria Saumell.