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

6. workshop Centra základů moderní informatiky

The sixth workshop of the Center for Foundations of Modern Computer Science will take place on Monday and Tuesday September 7 and 8, 2020, in Kutná Hora as a part of a joint meeting of IUUK and KAM.

Abstracts

Tereza Klimošová: On Vizing’s edge colouring question

In his 1965 seminal paper on edge colouring, Vizing proved that a $(\Delta+1)$-edge colouring can be reached from any given proper edge colouring through a series of Kempe changes, where $\Delta$ is the maximum degree of the graph. He concludes the paper with the following question: can an optimal edge colouring be reached from any given proper edge colouring through a series of Kempe changes? In other words, if the graph is $\Delta$-edge-colourable, can we always reach a $\Delta$-edge-colouring? We answer this question in the affirmative for triangle-free graphs.

This is joint work with Marthe Bonamy, Oscar Defrain, Aurélie Lagoutte and Jonathan Narboni.

Ida Kantor: What we learned in Manhattan

When investigating lines in general metric spaces, the plane with the Manhattan metric provides a convenient playground, not trivial, and yet not too complex. Several ideas first discovered in the context of Manhattan metric later proved very useful in investigating general metric spaces. We will survey these and suggest possible directions for future research along these lines.

Martin Balko: On ordered Ramsey numbers of tripartite 3-uniform hypergraphs

For an integer k >= 2, an ordered k-uniform hypergraph H is a k-uniform hypergraph together with a fixed linear ordering of its vertex set. The ordered Ramsey number R(H,G) of two ordered k-uniform hypergraphs H and G is the smallest positive integer N such that every red-blue coloring of the hyperedges of the ordered complete k-uniform hypergraph K^(k)_N on N vertices contains a blue copy of H or a red copy of G.

The ordered Ramsey numbers are quite extensively studied for ordered graphs, but little is known about ordered hypergraphs of higher uniformity. We provide some of the first nontrivial estimates on ordered Ramsey numbers of ordered 3-uniform hypergraphs. In particular, we prove that for all positive integers d,n and for every ordered 3-uniform hypergraph H on n vertices with maximum degree d and with interval chromatic number 3 there is an epsilon=epsilon(d)>0 such that R(H,H) <= 2^(O(n^(2-epsilon))). In fact, we prove this upper bound for the number R(G,K^(3)_3(n)), where G is an ordered 3-uniform hypergraph with n vertices and maximum degree d and K^(3)_3(n) is the ordered complete tripartite hypergraph with consecutive color classes of size n. We show that this bound is not far from the truth by proving R(H,K^(3)_3(n)) >= 2^(Omega(n\log(n))) for some fixed ordered 3-uniform hypergraph H.

This is joint work with Máté Vizer.

Pavel Hubáček: Verifiable Delay Functions from Lucas Sequences

A Verifiable Delay Function (VDF) is a function which satisfies two properties. First, it is a delay function, i.e., it must take a prescribed (wall) time T to compute irrespective of the amount of available parallelism. Second, it should be possible for anyone to quickly verify (e.g., in logarithmic time in T) the value of the function given a short proof. Practical VDFs were recently constructed based on the assumption that repeated squaring is an inherently sequential problem in the works of Pietrzak and Wesolowski. These constructions found applications for example in decentralized cryptographic currencies and secure randomness beacons. We generalize the repeated squaring approach and construct more structured VDFs based on the sequential hardness of Lucas sequences in order to enable further applications.