- D. Chistikov, S. Kiefer, A. Murawski, D. Purser. The big-O problem. Logical Methods in Computer Science (2022).
Given two weighted automata (or labelled Markov chains), is there a constant c such that the weight of every word in the first automaton is at most c times its weight in the second?
- D. Chistikov, S. Kiefer, A. Murawski, D. Purser. The big-O problem for labelled Markov chains and weighted automata. CONCUR 2020. [DROPS] Extended version in Logical Methods in Computer Science (2022).
- D. Chistikov, A. Murawski, D. Purser. Asymmetric distances for approximate differential privacy. CONCUR 2019.
We measure distances between states in labelled Markov chains in the spirit of bisimilarity relation. It turns out that asymmetric distance functions are, in some sense, better.
- D. Chistikov, A. Murawski, D. Purser. Bisimilarity distances for approximate differential privacy. ATVA 2018.
A pair of states in a labelled Markov chain can be bisimilar or not bisimilar. We extend this equivalence relation to a distance function which upper-bounds the δ parameter in approximate differential privacy.
- D. Chistikov, S. Kiefer, I. Marušić, M. Shirmohammadi, J. Worrell. On rationality of nonnegative matrix factorization. SODA 2017. Further version in SIAM Journal on Applied Algebra and Geometry (2017).
We find a matrix for which the nonnegative rank over the reals and over the rationals are different. Consequently, state minimization of hidden Markov models may require irrational probabilities.
- D. Chistikov, S. Kiefer, I. Marušić, M. Shirmohammadi, J. Worrell. On restricted nonnegative matrix factorization.
There exists a pair of 3D polytopes with rational vertices, one inside the other, such that every intermediate polytope with 5 vertices must have a vertex with an irrational coordinate.