All reports by Author Andrei Romashchenko:

__
TR19-001
| 5th January 2019
__

Dmitry Itsykson, Alexander Knop, Andrei Romashchenko, Dmitry Sokolov#### On OBDD-based algorithms and proof systems that dynamically change order of variables

__
TR18-043
| 22nd February 2018
__

Andrei Romashchenko, Marius Zimand#### An operational characterization of mutual information in algorithmic information theory

Revisions: 2

__
TR08-030
| 16th November 2007
__

Bruno Durand, Alexander Shen, Andrei Romashchenko#### Fixed Point and Aperiodic Tilings

__
TR04-031
| 22nd March 2004
__

Troy Lee, Andrei Romashchenko#### On Polynomially Time Bounded Symmetry of Information

__
TR00-026
| 11th April 2000
__

Andrei Romashchenko, Alexander Shen, Nikolay Vereshchagin#### Combinatorial Interpretation of Kolmogorov Complexity

Dmitry Itsykson, Alexander Knop, Andrei Romashchenko, Dmitry Sokolov

In 2004 Atserias, Kolaitis and Vardi proposed OBDD-based propositional proof systems that prove unsatisfiability of a CNF formula by deduction of identically false OBDD from OBDDs representing clauses of the initial formula. All OBDDs in such proofs have the same order of variables. We initiate the study of OBDD based ... more >>>

Andrei Romashchenko, Marius Zimand

We show that the mutual information, in the sense of Kolmogorov complexity, of any pair of strings

$x$ and $y$ is equal, up to logarithmic precision, to the length of the longest shared secret key that

two parties, one having $x$ and the complexity profile of the pair and the ...
more >>>

Bruno Durand, Alexander Shen, Andrei Romashchenko

An aperiodic tile set was first constructed by R.Berger while

proving the undecidability of the domino problem. It turned out

that aperiodic tile sets appear in many topics ranging from

logic (the Entscheidungsproblem) to physics (quasicrystals)

We present a new construction of an aperiodic tile set. The

flexibility of this ...
more >>>

Troy Lee, Andrei Romashchenko

The information contained in a string $x$ about a string $y$

is defined as the difference between the Kolmogorov complexity

of $y$ and the conditional Kolmogorov complexity of $y$ given $x$,

i.e., $I(x:y)=\C(y)-\C(y|x)$. From the well-known Kolmogorov--Levin Theorem it follows that $I(x:y)$ is symmetric up to a small ...
more >>>

Andrei Romashchenko, Alexander Shen, Nikolay Vereshchagin

The very first Kolmogorov's paper on algorithmic

information theory was entitled `Three approaches to the

definition of the quantity of information'. These three

approaches were called combinatorial, probabilistic and

algorithmic. Trying to establish formal connections

between combinatorial and algorithmic approaches, we

prove that any ...
more >>>