slideshow 3

Complexity seminar

usually takes place each Friday at 14:00 - 16:00 temporarily on Zoom, normally in IM, rear building, ground floor
Chair: Michal Koucky, Pavel Pudlak
The programme is announced via the mailing list...

Testing Equality in Communication Graphs
Klim Efremenko
Tel-Aviv University
Friday, 19. May 2017 - 13:30 to 15:00

in IM, rear building, ground floor

Let $G=(V,E)$ be a connected undirected graph with $k$ vertices. Suppose
that on each vertex of the graph there is a player having an $n$-bit
string. Each player is allowed to communicate with its neighbors according
to a (static) agreed communication protocol and the players must decide,
deterministically, if their inputs are all equal. What is the minimum
possible total number of bits transmitted in a protocol solving
this problem? We determine this minimum up to a lower order
additive term in many cases (but not for all graphs).  
In particular, we show that it is $kn/2+o(n)$ for any
Hamiltonian $k$-vertex graph, and that for any $2$-edge connected 
graph with $m$ edges containing no
two adjacent vertices of degree exceeding $2$ it is $mn/2+o(n)$.
The proofs combine graph theoretic ideas with
tools from additive number theory.

Cluster Planarity
Filip Šedivý
Faculty of Mathematics and Physics, Charles Univ.
Friday, 7. April 2017 - 13:30 to 15:00

in IM, rear building, ground floor

This thesis studies the problem of clustered planarity and follows two
directions. First direction deals with computational complexity, where we
show how clustered planarity can be solved in linear nondeterministic time
in terms of the number of vertices of the input graph. Second directions
is characterization of restricted versions of clustered planarity using
minimal non-clustered-planar instances. For this purpose we introduce a
notion of clustered minor using several operations reducing clustered
graphs. We show that these operations preserve clustered planarity. We
show that in the case of clustered graphs where clusters have size 2 and
the graph is a cycle or a path, there are only finitely many minimal
non-clustered-planar minors. We also mention known results about the
computational complexity of clustered planarity.

Complexity theory beyond deterministic exponential time and applications Parts II

Igor Carboni Oliveira
MFF, UK
Friday, 17. March 2017 - 13:30 to 15:00

in IM, rear building, ground floor

Part I. (this will be on the Seminar on limits of efficient computation on Marh 15)
I'll survey a variety of connections between non-uniform circuit
lower bounds, non-trivial proof systems, non-trivial learning algorithms, and
variants of natural properties. In particular, I plan to discuss how one can
prove new unconditional lower bounds for standard complexity classes such as
REXP, ZPEXP, BPEXP, and NEXP by designing algorithms with a non-trivial
running time, and to present some open problems. 

Part II. I'll focus on a recent application of some of the
complexity-theoretic techniques behind these results. I'll describe in more
detail recent progress on the problem of efficiently generating large
canonical prime numbers, via pseudodeterministic pseudorandomness. If there
is enough time and interest, we will also discuss some non-constructive
aspects of the result, and connections to... more

Lower bounds on Non-adaptive Data Structures for Median and Predecessor search
Anup Rao
Univ. of Washington, Seattle, USA
Friday, 10. March 2017 - 13:30 to 15:00

in IM, rear building, ground floor

What is the best way to maintain a subset of {1,2,...,m} so that the median
of the set can be easily recovered? We are interested in the algorithms that
access the fewest memory locations when adding an element to the set and
computing the median of the set. We prove the first lower bounds for such
algorithms. We say that the algorithm handles insertions non-adaptively if
the locations of memory accessed depend only on the element being inserted,
and not on the contents of the memory. If the algorithm handles insertions
non-adaptively, then our lower bounds imply that Binary Search Trees are
essentially optimal (our results give a more general tradeoff between the
parameters of the algorithm). In addition, we investigate the predecessor
search problem, where the algorithm is required to compute the predecessor of
any element in the set. Here we prove that if computing the predecessors can
be done non-adaptively... more

Pages