| Publication | Date of Publication | Type |
|---|
Total conditional complexity of certain objects
Information and Computation | 2026-02-02 | Paper |
Half-duplex communication complexity with adversary can be less than the classical communication complexity
Sbornik: Mathematics | 2025-09-19 | Paper |
Chair of Mathematical Logic and Theory of Algorithms
Moscow University Mathematics Bulletin | 2025-07-11 | Paper |
| A new simple family of non-periodic tilings with square tiles | 2023-07-30 | Paper |
Information disclosure in the framework of Kolmogorov complexity
Theoretical Computer Science | 2023-04-20 | Paper |
| Kolmogorov Last Discovery? (Kolmogorov and Algorithmic Statictics) | 2023-03-23 | Paper |
| How much randomness is needed to convert MA protocols to AM protocols? | 2022-11-11 | Paper |
A family of non-periodic tilings of the plane by right golden triangles
Discrete & Computational Geometry | 2022-06-03 | Paper |
Information disclosure in the framework of Kolmogorov complexity
(available as arXiv preprint) | 2021-08-03 | Paper |
High entropy random selection protocols
Algorithmica | 2021-03-26 | Paper |
Proofs of conservation inequalities for Levin's notion of mutual information of 1974
Theoretical Computer Science | 2021-01-19 | Paper |
| scientific article; zbMATH DE number 7204268 (Why is no real title available?) | 2020-05-26 | Paper |
On the structure of Ammann A2 tilings
Discrete & Computational Geometry | 2020-04-07 | Paper |
Descriptive complexity of computable sequences revisited
Theoretical Computer Science | 2020-01-29 | Paper |
Sparse selfreducible sets and nonuniform lower bounds
Algorithmica | 2019-01-11 | Paper |
A Conditional Information Inequality and Its Combinatorial Applications
IEEE Transactions on Information Theory | 2018-09-14 | Paper |
Short lists with short programs in short time
Computational Complexity | 2018-04-18 | Paper |
Short lists with short programs from programs of functions and strings
Theory of Computing Systems | 2018-02-01 | Paper |
Kolmogorov Complexity and Algorithmic Randomness
Mathematical Surveys and Monographs | 2017-12-28 | Paper |
Encoding invariance in average case complexity
Theory of Computing Systems | 2017-11-07 | Paper |
Rate Distortion and Denoising of Individual Data Using Kolmogorov Complexity
IEEE Transactions on Information Theory | 2017-07-27 | Paper |
Algorithmic statistics: forty years later
Computability and Complexity | 2017-04-04 | Paper |
Towards a reverse Newman's theorem in interactive information complexity
Algorithmica | 2016-11-29 | Paper |
Algorithmic minimal sufficient statistics: a new approach
Theory of Computing Systems | 2016-05-19 | Paper |
Algorithmic statistics revisited
Measures of Complexity | 2016-05-13 | Paper |
| Short lists with short programs for functions | 2014-09-20 | Paper |
Aperiodic Tilings by Right Triangles
Descriptional Complexity of Formal Systems | 2014-08-07 | Paper |
On joint conditional complexity (entropy)
Proceedings of the Steklov Institute of Mathematics | 2014-08-04 | Paper |
Randomized communication complexity of approximating Kolmogorov complexity
Computer Science - Theory and Applications | 2014-06-24 | Paper |
On algorithmic strong sufficient statistics
Lecture Notes in Computer Science | 2013-08-05 | Paper |
Improving on Gutfreund, Shaltiel, and Ta-Shma's paper ``If NP languages are hard on the worst-case, then it is easy to find their hard instances''
Computer Science – Theory and Applications | 2013-06-14 | Paper |
| Limit complexities revisited | 2013-03-19 | Paper |
| Limit complexities revisited [once more] | 2012-04-01 | Paper |
Test martingales, Bayes factors and \(p\)-values
Statistical Science | 2011-08-19 | Paper |
| scientific article; zbMATH DE number 5935734 (Why is no real title available?) | 2011-08-04 | Paper |
| scientific article; zbMATH DE number 5935712 (Why is no real title available?) | 2011-08-03 | Paper |
Insuring against loss of evidence in game-theoretic probability
Statistics & Probability Letters | 2011-01-14 | Paper |
Limit complexities revisited
Theory of Computing Systems | 2010-10-06 | Paper |
Algorithmic minimal sufficient statistic revisited
Mathematical Theory and Computational Practice | 2010-07-28 | Paper |
On abstract resource semantics and computability logic
Journal of Computer and System Sciences | 2010-07-08 | Paper |
An encoding invariant version of polynomial time computable distributions
Computer Science – Theory and Applications | 2010-06-22 | Paper |
Kolmogorov complexity of enumerating finite sets
Information Processing Letters | 2010-03-24 | Paper |
Does the polynomial hierarchy collapse if onto functions are invertible?
Theory of Computing Systems | 2010-03-05 | Paper |
| scientific article; zbMATH DE number 5605130 (Why is no real title available?) | 2009-09-19 | Paper |
Kolmogorov Complexity and Model Selection
Computer Science - Theory and Applications | 2009-08-18 | Paper |
Kolmogorov-Loveland stochasticity for finite strings
Information Processing Letters | 2009-07-21 | Paper |
High Entropy Random Selection Protocols
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-02-17 | Paper |
Kolmogorov's Structure Functions and Model Selection
IEEE Transactions on Information Theory | 2008-12-21 | Paper |
On-Line Probability, Complexity and Randomness
Lecture Notes in Computer Science | 2008-10-14 | Paper |
On Game Semantics of the Affine and Intuitionistic Logics
Logic, Language, Information and Computation | 2008-07-10 | Paper |
Inverting Onto Functions and Polynomial Hierarchy
Computer Science – Theory and Applications | 2008-06-03 | Paper |
Kolmogorov Complexity with Error
STACS 2006 | 2008-03-19 | Paper |
STACS 2004
Lecture Notes in Computer Science | 2007-10-01 | Paper |
Non-reducible descriptions for conditional Kolmogorov complexity
Theoretical Computer Science | 2007-09-28 | Paper |
Individual communication complexity
Journal of Computer and System Sciences | 2007-08-23 | Paper |
Shannon Entropy vs. Kolmogorov Complexity
Computer Science – Theory and Applications | 2007-05-02 | Paper |
Theory and Applications of Models of Computation
Lecture Notes in Computer Science | 2007-04-30 | Paper |
| scientific article; zbMATH DE number 5145337 (Why is no real title available?) | 2007-04-23 | Paper |
Partitioning multi-dimensional sets in a small number of ``uniform'' parts
European Journal of Combinatorics | 2006-12-07 | Paper |
A new class of non-Shannon-type inequalities for entropies
Communications in Information and Systems | 2006-06-20 | Paper |
STACS 2005
Lecture Notes in Computer Science | 2005-12-02 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2005-08-24 | Paper |
| scientific article; zbMATH DE number 2174389 (Why is no real title available?) | 2005-06-08 | Paper |
How to use several noisy channels with unknown error probabilities
Information and Computation | 2003-08-19 | Paper |
Do stronger definitions of randomness exist?
Theoretical Computer Science | 2003-08-17 | Paper |
| scientific article; zbMATH DE number 1948155 (Why is no real title available?) | 2003-07-10 | Paper |
| scientific article; zbMATH DE number 1880324 (Why is no real title available?) | 2003-03-12 | Paper |
| scientific article; zbMATH DE number 1793700 (Why is no real title available?) | 2002-09-01 | Paper |
Inequalities for Shannon entropy and Kolmogorov complexity
Journal of Computer and System Sciences | 2002-07-10 | Paper |
Independent minimum length programs to translate between given strings
Theoretical Computer Science | 2002-03-03 | Paper |
Upper semi-lattice of binary strings with the relation ``\(x\) is simple conditional to \(y\)''
Theoretical Computer Science | 2002-03-03 | Paper |
Combinatorial interpretation of Kolmogorov complexity
Theoretical Computer Science | 2002-03-03 | Paper |
Logical operations and Kolmogorov complexity
Theoretical Computer Science | 2002-03-03 | Paper |
Kolmogorov complexity conditional to large integers
Theoretical Computer Science | 2002-03-03 | Paper |
Descriptive complexity of computable sequences
Theoretical Computer Science | 2002-03-03 | Paper |
| scientific article; zbMATH DE number 1678398 (Why is no real title available?) | 2001-12-04 | Paper |
Arthur-Merlin games in Boolean decision trees
Journal of Computer and System Sciences | 2000-11-22 | Paper |
| scientific article; zbMATH DE number 1297597 (Why is no real title available?) | 1999-06-09 | Paper |
Randomized Boolean decision trees: Several remarks
Theoretical Computer Science | 1999-01-12 | Paper |
Oracle separation of complexity classes and lower bounds for perceptrons solving separation problems
Izvestiya: Mathematics | 1997-08-18 | Paper |
A general method to construct oracles realizing given relationships between complexity classes
Theoretical Computer Science | 1997-02-27 | Paper |
RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
Russian Academy of Sciences. Izvestiya Mathematics | 1994-12-06 | Paper |
| scientific article; zbMATH DE number 641289 (Why is no real title available?) | 1994-09-21 | Paper |
BANISHING ROBUST TURING COMPLETENESS
International Journal of Foundations of Computer Science | 1994-04-27 | Paper |
New proof of the solvability of the elementary theory of linearly ordered sets
Mathematical Notes | 1990-01-01 | Paper |
Occurrence of zero in a linear recursive sequence
Mathematical Notes | 1985-01-01 | Paper |
| scientific article; zbMATH DE number 3946216 (Why is no real title available?) | 1984-01-01 | Paper |
