Reducing randomness in Isolation Lemma on decomposable graphs

Prelegent(ci)

Michał Pilipczuk

Termin

1 kwietnia 2021 12:15

Informacje na temat wydarzenia

online

Seminarium

Seminarium "Algorytmika"

---

The classic Isolation Lemma of Mulmuley et al. states that if
F is a non-empty family of subsets of a universe U of size n, and we
draw a weight function f : U -> {1,...,2n} uniformly at random, then
with probability at least 1/2 there is a unique element of F that has
the minimum weight w.r.t. f. Obviously, drawing such a weight function
uniformly at random requires using O(n log n) random bits. We study how
much we can reduce the amount of randomness needed in case we know that
the family F in question comprises of some nicely behaving combinatorial
objects in a decomposable graph. For instance, we provide an isolation
scheme that uses O(t log n + log^2 n) random bits for Hamiltonian Cycles
in graphs of treewidth t, which can be generalized to isolating any
MSO-definable family of objects using f(t) log n + O(log^2 n) random
bits. A concrete corollary of our randomness-efficient isolation schemes
is an algorithm for Hamiltonian Cycle in planar graphs (and in fact, in
any class of graphs that admits balanced separators of size O(n^{1/2}))
that achieves determinism, time complexity 2^O(sqrt{n}), and polynomial
space complexity at the same time.

This is a joint work with Jesper Nederlof, Céline Swennenhuis, and Karol
Węgrzycki (♥).

---