21 citations · 60 across the 30 of their papers we have counts for
35 papers
Recognizable Picture Languages: Separating UREC from coUREC via Communication Complexity
Antonin Callard, Andrei Romashchenko, Véronique Terrier +1
We introduce communication-complexity lifting techniques into the study of recognizable picture languages. As an application, we resolve a long-standing open problem of Anselmo et…
Size Bounds for CQs Under Acyclic Constraints
Stefan Mengel, Andrei Romashchenko
We study size bounds for conjunctive query (CQ) results which in recent years have played a crucial role in database theory. In particular, we compare the so-called entropic bound…
Beyond Mutual Information: Extension Profiles and Shape Functions of Random Variable Pairs
Rostislav Matveev, Andrei Romashchenko
We study the extension profile of a pair of jointly distributed finite-valued random variables , defined as the set of all triples of numbers …
Spectral Conditions for the Ingleton Inequality
Rostislav Matveev, Andrei Romashchenko
The Ingleton inequality is a classical linear information inequality that holds for representable matroids but fails to be universally valid for entropic vectors. Understanding the…
Structural Properties of Entropic Vectors and Stability of the Ingleton Inequality
Rostislav Matveev, Andrei Romashchenko
We study constrained versions of the Ingleton inequality in the entropic setting and quantify its stability under small violations of conditional independence. Although the classic…
Algebraic Barriers to Halving Algorithmic Information Quantities in Correlated Strings
Andrei Romashchenko
We study the possibility of scaling down algorithmic information quantities in tuples of correlated strings. In particular, we address a question raised by Alexander Shen: whether,…