8th workshop of the Center for Foundations of Modern Computer Science

8. workshop Centra základů moderní informatiky

The eighth workshop of the Center for Foundations of Modern Computer Science took place on Monday September 13, 2021, in Kutná Hora as a part of a joint meeting of IUUK and KAM.

Abstracts

Pavel Veselý: Relative Error Streaming Quantiles

We discuss approximating quantiles and distributions using streaming algorithms that process the input in one pass and maintain a small data structure, called sketch. We focus on providing the relative error guarantee, which helps to understand the tails of the input distribution as it allows one to estimate percentiles such as 99, 99.9, 99.99, etc., with increasing accuracy. We describe a new algorithm, called ReqSketch, with a close-to-optimal space requirement. Moreover, the sketch maintained by the algorithm is fully mergeable, which means that the guarantees from the streaming setting hold even in more general distributed or parallel settings. We also compare ReqSketch with a heuristic called t-digest that has been deployed by several major tech companies and show how to construct inputs for t-digest that induce an almost arbitrarily large error.

Irena Penev: Coloring $(4K_1,C_4,C_6)$-free graphs

A graph is even-hole-free if it contains no induced cycles of even length. Even-hole-free graphs can be recognized in polynomial time, and furthermore, the Maximum Clique problem can be solved in polynomial time for such graphs. However, the time complexity of the Vertex Coloring problem is open for this class. The time complexity of Vertex Coloring is also open for graphs of stability number at most three. In this talk, we consider the intersection of these two classes: even-hole-free graphs of stability number at most three, or equivalently,  $(4K_1,C_4,C_6)$-free graphs. We show that such graphs can be recognized and colored in cubic time.