Andrei E. Romashchenko

Orcid: 0000-0001-7723-7880

Affiliations:
  • LIRMM, CNRS, University of Montpellier, France
  • IITP of Moscow, Russia


According to our database1, Andrei E. Romashchenko authored at least 50 papers between 1997 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Spectral Approach to the Communication Complexity of Multi-Party Key Agreement.
Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

2022
Clustering with respect to the information distance.
Theor. Comput. Sci., 2022

Resource-bounded Kolmogorov complexity provides an obstacle to soficness of multidimensional shifts.
J. Comput. Syst. Sci., 2022

Inequalities for space-bounded Kolmogorov complexity.
Comput., 2022

2021
27 Open Problems in Kolmogorov Complexity.
SIGACT News, 2021

2020
On OBDD-based Algorithms and Proof Systems that Dynamically Change the order of Variables.
J. Symb. Log., 2020

Inequalities for space-bounded Kolmogorov complexity.
CoRR, 2020

Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory.
Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

2019
An Operational Characterization of Mutual Information in Algorithmic Information Theory.
J. ACM, 2019

On a conditional inequality in Kolmogorov complexity and its applications in communication complexity.
CoRR, 2019

How to Use Undiscovered Information Inequalities: Direct Applications of the Copy Lemma.
Proceedings of the IEEE International Symposium on Information Theory, 2019

2018
A Conditional Information Inequality and Its Combinatorial Applications.
IEEE Trans. Inf. Theory, 2018

On the Combinatorial Version of the Slepian-Wolf Problem.
IEEE Trans. Inf. Theory, 2018

The expressiveness of quasiperiodic and minimal shifts of finite type.
CoRR, 2018

Algorithmic Measures of Information for Tuples of Words and for Patterns in Multidimensional Shifts of Finite Type.
, 2018

2017
On the Expressive Power of Quasiperiodic SFT.
Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

2016
Coding in the fork network in the framework of Kolmogorov complexity.
CoRR, 2016

2015
Topological Arguments for Kolmogorov Complexity.
Theory Comput. Syst., 2015

Conditional Information Inequalities and Combinatorial Applications.
CoRR, 2015

Quasiperiodicity and Non-computability in Tilings.
Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Randomized Polynomial Time Protocol for Combinatorial Slepian-Wolf Problem.
Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

2014
Pseudo-Random Graphs and Bit Probe Schemes with One-Sided Error.
Theory Comput. Syst., 2014

The axiomatic power of Kolmogorov complexity.
Ann. Pure Appl. Log., 2014

2013
Conditional Information Inequalities for Entropic and Almost Entropic Points.
IEEE Trans. Inf. Theory, 2013

2012
Fixed-point tile sets and their applications.
J. Comput. Syst. Sci., 2012

Conditional and unconditional information inequalities: an algebraic example
CoRR, 2012

On the non-robustness of essentially conditional information inequalities.
Proceedings of the 2012 IEEE Information Theory Workshop, 2012

2011
Variations on Muchnik's Conditional Complexity Theorem.
Theory Comput. Syst., 2011

Constraint information inequalities revisited
CoRR, 2011

On essentially conditional information inequalities.
Proceedings of the 2011 IEEE International Symposium on Information Theory Proceedings, 2011

2010
Stability of properties of Kolmogorov complexity under relativization.
Probl. Inf. Transm., 2010

1D Effectively Closed Subshifts and 2D Tilings.
Proceedings of the Second Symposium on Cellular Automata "Journées Automates Cellulaires", 2010

Fixed Point Argument and Tilings without Long Range Order.
Proceedings of the 7th Workshop on Fixed Points in Computer Science, 2010

Effective Closed Subshifts in 1D Can Be Implemented in 2D.
Proceedings of the Fields of Logic and Computation, 2010

2009
Fixed Point Theorem and Aperiodic Tilings.
Bull. EATCS, 2009

High Complexity Tilings with Sparse Errors.
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

2008
Fixed Point and Aperiodic Tilings.
Electron. Colloquium Comput. Complex., 2008

A Random Oracle Does Not Help Extract the Mutual Information.
Proceedings of the Mathematical Foundations of Computer Science 2008, 2008

Sparse sets.
Proceedings of the First Symposium on Cellular Automata "Journées Automates Cellulaires" (JAC 2008), 2008

2006
Reliable Computations Based on Locally Decodable Codes.
Proceedings of the STACS 2006, 2006

2005
Resource bounded symmetry of information revisited.
Theor. Comput. Sci., 2005

2004
On Polynomially Time Bounded Symmetry of Information
Electron. Colloquium Comput. Complex., 2004

2003
A Criterion for Extractability of Mutual Information for a Triple of Strings.
Probl. Inf. Transm., 2003

Extracting the Mutual Information for a Triple of Binary Strings.
Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002
Combinatorial interpretation of Kolmogorov complexity.
Theor. Comput. Sci., 2002

Upper semi-lattice of binary strings with the relation "x is simple conditional to y".
Theor. Comput. Sci., 2002

A new class of non-Shannon-type inequalities for entropies.
Commun. Inf. Syst., 2002

2000
Inequalities for Shannon Entropy and Kolmogorov Complexity.
J. Comput. Syst. Sci., 2000

1999
Upper Semilattice of Binary Strings with the Relation "x is Simple Conditional to y".
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1997
Inequalities for Shannon entropies and Kolmogorov complexities.
Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997


  Loading...