Andrei Romashchenko

Available identifiers

zbMath Open romashchenko.andreiWikidataQ102334363 ScholiaQ102334363MaRDI QIDQ235580

List of research outcomes

Publication	Date of Publication	Type
Inequalities for space-bounded Kolmogorov complexity	2023-01-12	Paper
Clustering with respect to the information distance	2022-08-25	Paper
https://portal.mardi4nfdi.de/entity/Q5089211	2022-07-18	Paper
Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts	2022-07-18	Paper
Resource-bounded Kolmogorov complexity provides an obstacle to soficness of multidimensional shifts	2022-05-16	Paper
Clustering with Respect to the Information Distance	2021-10-04	Paper
An operational characterization of mutual information in algorithmic information theory	2021-07-28	Paper
https://portal.mardi4nfdi.de/entity/Q4986310	2021-04-27	Paper
The expressiveness of quasiperiodic and minimal shifts of finite type	2021-03-03	Paper
ON OBDD-BASED ALGORITHMS AND PROOF SYSTEMS THAT DYNAMICALLY CHANGE THE ORDER OF VARIABLES	2021-01-29	Paper
On the Expressive Power of Quasiperiodic SFT.	2020-05-26	Paper
Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory	2020-04-28	Paper
An Operational Characterization of Mutual Information in Algorithmic Information Theory	2020-02-11	Paper
On the Combinatorial Version of the Slepian–Wolf Problem	2018-09-19	Paper
A Conditional Information Inequality and Its Combinatorial Applications	2018-09-14	Paper
On OBDD-Based Algorithms and Proof Systems That Dynamically Change Order of Variables	2018-04-19	Paper
Conditional Information Inequalities for Entropic and Almost Entropic Points	2017-06-08	Paper
Quasiperiodicity and Non-computability in Tilings	2015-09-16	Paper
Randomized Polynomial Time Protocol for Combinatorial Slepian-Wolf Problem	2015-09-16	Paper
Topological arguments for Kolmogorov complexity	2015-07-20	Paper
Pseudo-random graphs and bit probe schemes with one-sided error	2015-02-05	Paper
The axiomatic power of Kolmogorov complexity	2014-06-06	Paper
Fixed-point tile sets and their applications	2012-08-17	Paper
On the Non-robustness of Essentially Conditional Information Inequalities	2012-07-23	Paper
Conditional and unconditional information inequalities: an algebraic example	2012-01-30	Paper
Variations on Muchnik's conditional complexity theorem	2011-10-11	Paper
Pseudo-random graphs and bit probe schemes with one-sided error	2011-06-17	Paper
Stability of properties of Kolmogorov complexity under relativization	2011-01-25	Paper
Effective Closed Subshifts in 1D Can Be Implemented in 2D	2010-09-03	Paper
Variations on Muchnik's conditional complexity theorem	2009-08-18	Paper
High Complexity Tilings with Sparse Errors	2009-07-14	Paper
A Random Oracle Does Not Help Extract the Mutual Information	2009-02-03	Paper
Fixed Point and Aperiodic Tilings	2008-10-30	Paper
Reliable Computations Based on Locally Decodable Codes	2008-03-19	Paper
A new class of non-Shannon-type inequalities for entropies	2006-06-20	Paper
Resource bounded symmetry of information revisited	2005-12-06	Paper
Mathematical Foundations of Computer Science 2004	2005-08-22	Paper
A criterion for extractability of mutual information for a triple of strings	2005-08-17	Paper
Pairs of words with nonmaterializable mutual information	2003-11-20	Paper
Inequalities for Shannon entropy and Kolmogorov complexity	2002-07-10	Paper
Sequences of binary strings with relation of conditional simplicity	2002-04-14	Paper
Upper semi-lattice of binary strings with the relation ``\(x\) is simple conditional to \(y\)	2002-03-03	Paper
Combinatorial interpretation of Kolmogorov complexity	2002-03-03	Paper

Research outcomes over time

Doctoral students

No records found.

Known relations from the MaRDI Knowledge Graph

Property	Value
MaRDI profile type	MaRDI person profile
instance of	human

This page was built for person: Andrei Romashchenko