Andrei A. Muchnik

24 papers A* 1A 2B 1Misc 1Journal 19
YearRankTypeTitle / Venue / Authors
2015 J jnl
Algorithmic aspects of decomposition and equivalence of finite-valued transducers.
Probl. Inf. Transm.
Andrei A. Muchnik, Konstantin Yu. Gorbunov
2013 J jnl
Determinization of ordinal automata.
Probl. Inf. Transm.
Andrei A. Muchnik
2010 J jnl
Stability of properties of Kolmogorov complexity under relativization.
Probl. Inf. Transm.
Andrei A. Muchnik, Andrei E. Romashchenko
2009 J jnl
Algorithmic randomness and splitting of supermartingales.
Probl. Inf. Transm.
Andrei A. Muchnik
2009 J jnl
Sequences close to periodic
CoRR
Andrei A. Muchnik, Yuri Pritykin, Alexei L. Semenov
2008 B conf
A Random Oracle Does Not Help Extract the Mutual Information.
MFCS
Andrei A. Muchnik, Andrei Romashchenko
2006 Misc conf
Shannon Entropy vs. Kolmogorov Complexity.
CSR
Andrei A. Muchnik, Nikolai K. Vereshchagin
2004 A* conf
Ecological Turing Machines.
ICALP
Bruno Durand, Andrei A. Muchnik, Maxim Ushakov, Nikolai K. Vereshchagin
2004 J jnl
Enumerations of the Kolmogorov Function
Electron. Colloquium Comput. Complex.
Richard Beigel, Harry Buhrman, Peter A. Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrei A. Muchnik, Frank Stephan, Leen Torenvliet
2004 J jnl
Non-reducible descriptions for conditional Kolmogorov complexity
Electron. Colloquium Comput. Complex.
Andrei A. Muchnik, Alexander Shen, Nikolai K. Vereshchagin, Michael V. Vyugin
2003 J jnl
Almost periodic sequences.
Theor. Comput. Sci.
Andrei A. Muchnik, Alexei L. Semenov, Maxim Ushakov
2003 J jnl
On the Role of the Law of Large Numbers in the Theory of Randomness.
Probl. Inf. Transm.
Andrei A. Muchnik, Alexei L. Semenov
2003 J jnl
One application of real-valued interpretation of formal power series.
Theor. Comput. Sci.
Andrei A. Muchnik
2003 J jnl
The definable criterion for definability in Presburger arithmetic and its applications.
Theor. Comput. Sci.
Andrei A. Muchnik
2002 J jnl
Conditional complexity and codes.
Theor. Comput. Sci.
Andrei A. Muchnik
2002 J jnl
Kolmogorov entropy in the context of computability theory.
Theor. Comput. Sci.
Andrei A. Muchnik, Semen Ye. Positselsky
2002 J jnl
Upper semi-lattice of binary strings with the relation "x is simple conditional to y".
Theor. Comput. Sci.
Alexey V. Chernov, Andrei A. Muchnik, Andrei Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
2001 A conf
Logical Operations and Kolmogorov Complexity II.
CCC
Andrei A. Muchnik, Nikolai K. Vereshchagin
2001 J jnl
Logical operations and Kolmogorov complexity. II
Electron. Colloquium Comput. Complex.
Andrei A. Muchnik, Nikolai K. Vereshchagin
2000 J jnl
Multi-conditional Descriptions and Codes in Kolmogorov Complexity
Electron. Colloquium Comput. Complex.
Andrei A. Muchnik, Alexei L. Semenov
1999 A conf
Upper Semilattice of Binary Strings with the Relation "x is Simple Conditional to y".
CCC
Andrei A. Muchnik, Andrei Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
1998 J jnl
Mathematical Metaphysics of Randomness.
Theor. Comput. Sci.
Andrei A. Muchnik, Alexei L. Semenov, Vladimir A. Uspensky
1998 J jnl
On Common Information.
Theor. Comput. Sci.
Andrei A. Muchnik
1996 J jnl
A General Method to Construct Oracles Realizing Given Relationships Between Complexity Classes.
Theor. Comput. Sci.
Andrei A. Muchnik, Nikolai K. Vereshchagin