It is known that if x ∈ [0, 1] is polynomial time random (i.e. no polynomial time computable martingale succeeds on the binary fractional expansion of x) then x is normal in any integer base greater than one. We show that ...

© 2021, The Author(s).We consider a natural generalization of classical scheduling problems to a setting in which using a time unit for processing a job causes some time-dependent cost, the time-of-use tariff, which must ...

An injective coloring of a graph is a vertex labeling such that two vertices sharing a common neighbor get different labels. In this work we introduce and study what we call additive colorings. An injective coloring of a ...

We present a deterministic algorithm for computing all irreducible factors of degree ≤ d of a given bivariate polynomial f ∈ K [x, y] over an algebraic number field K and their multiplicities, whose running time is polynomial ...

We consider the problem of clique coloring, that is, coloring the vertices of a given graph such that no (maximal) clique of size at least two is monocolored. It is known that interval graphs are 2-clique colorable. In ...

We give an algorithm to compute an absolutely normal number so that the first n digits in its binary expansion are obtained in time polynomial in n; in fact, just above quadratic. The algorithm uses combinatorial tools to ...

Let (Formula presented.) be a smooth, equidimensional, quasi-affine variety of dimension (Formula presented.) over (Formula presented.), and let (Formula presented.) be a (Formula presented.) matrix of coordinate functions ...