On The Power of PP. - Nikolai K. Vereshchagin (SCT, 1992)

Relationships between NP-sets, Co-NP-sets, and P-sets relative to random oracles. - Nikolai K. Vereshchagin (SCT, 1993)

Banishing Robust Turing Completeness. - Lane A. Hemaspaandra; Sanjay Jain 001; Nikolai K. Vereshchagin (Int. J. Found. Comput. Sci., 1993)

How to Use Expert Advice in the Case when Actual Values of Estimated Events Remain Unknown. - Olga Mitina; Nikolai K. Vereshchagin (COLT, 1995)

NP-sets are Co-NP-immune Relative to a Random Oracle. - Nikolai K. Vereshchagin (ISTCS, 1995)

Lower Bounds for Perceptrons Solving some Separation Problems and Oracle Separation of AM from PP. - Nikolai K. Vereshchagin (ISTCS, 1995)

A General Method to Construct Oracles Realizing Given Relationships Between Complexity Classes. - Andrei A. Muchnik; Nikolai K. Vereshchagin (Theor. Comput. Sci., 1996)

Inequalities for Shannon entropies and Kolmogorov complexities. - Daniel Hammer; Andrei E. Romashchenko; Alexander Shen 001; Nikolai K. Vereshchagin (CCC, 1997)

Deterministic Rational Transducers and Random Sequences. - Sylvain Porrot; Max Dauchet; Bruno Durand 001; Nikolai K. Vereshchagin (FoSSaCS, 1998)

Randomized Boolean Decision Trees: Several Remarks. - Nikolai K. Vereshchagin (Theor. Comput. Sci., 1998)

Provability, complexity, grammars. - Lev D. Beklemishev; Mati Pentus; Nikolai K. Vereshchagin (American Mathematical Society, 1999)

Upper Semilattice of Binary Strings with the Relation "x is Simple Conditional to y". - Andrei A. Muchnik; Andrei E. Romashchenko; Alexander Shen 001; Nikolai K. Vereshchagin (CCC, 1999)

One Property of Cross-Intersecting Families - Alexander A. Razborov; Nikolai K. Vereshchagin (Electron. Colloquium Comput. Complex., 1999)

Arthur-Merlin Games in Boolean Decision Trees. - Ran Raz; Gábor Tardos; Oleg Verbitsky 001; Nikolai K. Vereshchagin (J. Comput. Syst. Sci., 1999)

Inequalities for Shannon Entropy and Kolmogorov Complexity. - Daniel Hammer; Andrei E. Romashchenko; Alexander Shen 001; Nikolai K. Vereshchagin (J. Comput. Syst. Sci., 2000)

An enumerable undecidable set with low prefix complexity: a simplified proof - Nikolai K. Vereshchagin (Electron. Colloquium Comput. Complex., 2001)

Logical operations and Kolmogorov complexity. II - Andrei A. Muchnik; Nikolai K. Vereshchagin (Electron. Colloquium Comput. Complex., 2001)

Basic set theory. - Alexander Shen 001; Nikolai K. Vereshchagin (American Mathematical Society, 2002)

Variants of Realizability for Propositional Formulas and the Logic of the Weak Law of Excluded Middle. - Alexey V. Chernov; Dmitrij P. Skvortsov; Elena Z. Skvortsova; Nikolai K. Vereshchagin (CSL, 2002)

Kolmogorov's Structure Functions with an Application to the Foundations of Model Selection. - Nikolai K. Vereshchagin; Paul M. B. Vitányi (FOCS, 2002)

A new class of non-Shannon-type inequalities for entropies. - Konstantin Makarychev; Yury Makarychev; Andrei E. Romashchenko; Nikolai K. Vereshchagin (Commun. Inf. Syst., 2002)

Upper semi-lattice of binary strings with the relation "x is simple conditional to y". - Alexey V. Chernov; Andrei A. Muchnik; Andrei E. Romashchenko; Alexander Shen 001; Nikolai K. Vereshchagin (Theor. Comput. Sci., 2002)

Descriptive complexity of computable sequences. - Bruno Durand 001; Alexander Shen 001; Nikolai K. Vereshchagin (Theor. Comput. Sci., 2002)

Combinatorial interpretation of Kolmogorov complexity. - Andrei E. Romashchenko; Alexander Shen 001; Nikolai K. Vereshchagin (Theor. Comput. Sci., 2002)

Logical operations and Kolmogorov complexity. - Alexander Shen 001; Nikolai K. Vereshchagin (Theor. Comput. Sci., 2002)

Kolmogorov complexity conditional to large integers. - Nikolai K. Vereshchagin (Theor. Comput. Sci., 2002)

Independent minimum length programs to translate between given strings. - Nikolai K. Vereshchagin; Michael V. Vyugin (Theor. Comput. Sci., 2002)

How to use several noisy channels with unknown error probabilities. - Olga Mitina; Nikolai K. Vereshchagin (Inf. Comput., 2003)

Do stronger definitions of randomness exist? - Bruno Durand 001; Vladimir Kanovei; Vladimir A. Uspensky; Nikolai K. Vereshchagin (Theor. Comput. Sci., 2003)

Ecological Turing Machines. - Bruno Durand 001; Andrei A. Muchnik; Maxim Ushakov; Nikolai K. Vereshchagin (ICALP, 2004)

Individual Communication Complexity: Extended Abstract. - Harry Buhrman; Hartmut Klauck; Nikolai K. Vereshchagin; Paul M. B. Vitányi (STACS, 2004)

A Theory of Lossy Compression for Individual Data - Nikolai K. Vereshchagin; Paul M. B. Vitányi (CoRR, 2004)

Non-reducible descriptions for conditional Kolmogorov complexity - Andrei A. Muchnik; Alexander Shen 001; Nikolai K. Vereshchagin; Michael V. Vyugin (Electron. Colloquium Comput. Complex., 2004)

Kolmogorov Complexity with Error - Lance Fortnow; Troy Lee; Nikolai K. Vereshchagin (Electron. Colloquium Comput. Complex., 2004)

Increasing Kolmogorov Complexity - Harry Buhrman; Lance Fortnow; Ilan Newman; Nikolai K. Vereshchagin (Electron. Colloquium Comput. Complex., 2004)

Kolmogorov-Loveland stochasticity for finite strings. - Bruno Durand 001; Nikolai K. Vereshchagin (Inf. Process. Lett., 2004)

Kolmogorov's structure functions and model selection. - Nikolai K. Vereshchagin; Paul M. B. Vitányi (IEEE Trans. Inf. Theory, 2004)

Partitioning multi-dimensional sets in a small number of "uniform" parts - Noga Alon; Ilan Newman; Alexander Shen 001; Gábor Tardos; Nikolai K. Vereshchagin (Electron. Colloquium Comput. Complex., 2005)

Shannon Entropy vs. Kolmogorov Complexity. - Andrei A. Muchnik; Nikolai K. Vereshchagin (CSR, 2006)

On Algorithmic Rate-Distortion Function. - Nikolai K. Vereshchagin; Paul M. B. Vitányi (ISIT, 2006)

Inverting onto functions might not be hard. - Harry Buhrman; Lance Fortnow; Michal Koucký 001; John D. Rogers; Nikolai K. Vereshchagin (Electron. Colloquium Comput. Complex., 2006)

On Computation and Communication with Small Bias. - Harry Buhrman; Nikolai K. Vereshchagin; Ronald de Wolf (CCC, 2007)

Inverting Onto Functions and Polynomial Hierarchy. - Harry Buhrman; Lance Fortnow; Michal Koucký 001; John D. Rogers; Nikolai K. Vereshchagin (CSR, 2007)

Kolmogorov complexity of enumerating finite sets. - Nikolai K. Vereshchagin (Inf. Process. Lett., 2007)

Individual communication complexity. - Harry Buhrman; Hartmut Klauck; Nikolai K. Vereshchagin; Paul M. B. Vitányi (J. Comput. Syst. Sci., 2007)

Non-reducible descriptions for conditional Kolmogorov complexity. - Andrej Muchnik; Alexander Shen 001; Mikhail Ustinov; Nikolai K. Vereshchagin; Michael V. Vyugin (Theor. Comput. Sci., 2007)

On-Line Probability, Complexity and Randomness. - Alexey V. Chernov; Alexander Shen 001; Nikolai K. Vereshchagin; Vladimir Vovk (ALT, 2008)

Randomised Individual Communication Complexity. - Harry Buhrman; Michal Koucký 001; Nikolai K. Vereshchagin (CCC, 2008)

On Game Semantics of the Affine and Intuitionistic Logics. - Ilya Mezhirov; Nikolai K. Vereshchagin (WoLLIC, 2008)

Kolmogorov Complexity and Games. - Nikolay K. Vereshchagin (Bull. EATCS, 2008)

Algorithmic Minimal Sufficient Statistic Revisited. - Nikolay K. Vereshchagin (CiE, 2009)

Kolmogorov Complexity and Model Selection. - Nikolay K. Vereshchagin (CSR, 2009)

Game interpretation of Kolmogorov complexity - Andrej Muchnik; Ilya Mezhirov; Alexander Shen 001; Nikolai K. Vereshchagin (CoRR, 2010)

Sparse Selfreducible Sets and Nonuniform Lower Bounds. - Harry Buhrman; Leen Torenvliet; Falk Unger; Nikolai K. Vereshchagin (Electron. Colloquium Comput. Complex., 2010)

Algorithmic Minimal Sufficient Statistics: a New Definition. - Nikolay K. Vereshchagin (Electron. Colloquium Comput. Complex., 2010)

An Encoding Invariant Version of Polynomial Time Computable Distributions. - Nikolay K. Vereshchagin (Electron. Colloquium Comput. Complex., 2010)

On abstract resource semantics and computability logic. - Ilya Mezhirov; Nikolay K. Vereshchagin (J. Comput. Syst. Sci., 2010)

Limit Complexities Revisited. - Laurent Bienvenu; Andrej Muchnik; Alexander Shen 001; Nikolai K. Vereshchagin (Theory Comput. Syst., 2010)

Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible? - Harry Buhrman; Lance Fortnow; Michal Koucký 001; John D. Rogers; Nikolai K. Vereshchagin (Theory Comput. Syst., 2010)

Rate distortion and denoising of individual data using Kolmogorov complexity. - Nikolai K. Vereshchagin; Paul M. B. Vitányi (IEEE Trans. Inf. Theory, 2010)

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". - Nikolay K. Vereshchagin (Electron. Colloquium Comput. Complex., 2011)

Limit complexities revisited [once more] - Laurent Bienvenu; Andrej Muchnik; Alexander Shen 001; Nikolai K. Vereshchagin (CoRR, 2012)

On Algorithmic Strong Sufficient Statistics. - Nikolay K. Vereshchagin (CiE, 2013)

Randomized communication complexity of appropximating Kolmogorov complexity. - Nikolay K. Vereshchagin (Electron. Colloquium Comput. Complex., 2013)

Randomized Communication Complexity of Approximating Kolmogorov Complexity. - Nikolay K. Vereshchagin (CSR, 2014)

Aperiodic Tilings by Right Triangles. - Nikolay K. Vereshchagin (DCFS, 2014)

Encoding Invariance in Average Case Complexity. - Nikolay K. Vereshchagin (Theory Comput. Syst., 2014)

Editorial. - Nikolay K. Vereshchagin (Theory Comput. Syst., 2014)

Conditional Information Inequalities and Combinatorial Applications. - Tarik Kaced; Andrei E. Romashchenko; Nikolay K. Vereshchagin (CoRR, 2015)

Algorithmic statistics revisited. - Nikolai K. Vereshchagin; Alexander Shen 001 (CoRR, 2015)

Towards a Reverse Newman's Theorem in Interactive Information Complexity. - Joshua Brody; Harry Buhrman; Michal Koucký 001; Bruno Loff; Florian Speelman; Nikolai K. Vereshchagin (Algorithmica, 2016)

Algorithmic Minimal Sufficient Statistics: a New Approach. - Nikolay K. Vereshchagin (Theory Comput. Syst., 2016)

Algorithmic Statistics: Forty Years Later. - Nikolay K. Vereshchagin; Alexander Shen 001 (Computability and Complexity, 2017)

Stochasticity in Algorithmic Statistics for Polynomial Time. - Alexey Milovanov; Nikolai K. Vereshchagin (Electron. Colloquium Comput. Complex., 2017)

Short lists with short programs from programs of functions and strings. - Nikolai K. Vereshchagin (Theory Comput. Syst., 2017)

Short lists with short programs in short time. - Bruno Bauwens; Anton Makhlin; Nikolai K. Vereshchagin; Marius Zimand (Comput. Complex., 2018)

A Conditional Information Inequality and Its Combinatorial Applications. - Tarik Kaced; Andrei E. Romashchenko; Nikolai K. Vereshchagin (IEEE Trans. Inf. Theory, 2018)

On the Structure of Ammann A2 Tilings. - Bruno Durand 001; Alexander Shen 001; Nikolai K. Vereshchagin (Discret. Comput. Geom., 2020)

Descriptive complexity of computable sequences revisited. - Nikolay K. Vereshchagin (Theor. Comput. Sci., 2020)

High Entropy Random Selection Protocols. - Harry Buhrman; Matthias Christandl; Michal Koucký 001; Zvi Lotker; Boaz Patt-Shamir; Nikolai K. Vereshchagin (Algorithmica, 2021)

Proofs of conservation inequalities for Levin's notion of mutual information of 1974. - Nikolai K. Vereshchagin (Theor. Comput. Sci., 2021)

A Family of Non-Periodic Tilings of the Plane by Right Golden Triangles. - Nikolay K. Vereshchagin (Discret. Comput. Geom., 2022)

How much randomness is needed to convert MA protocols to AM protocols? - Nikolay K. Vereshchagin (Electron. Colloquium Comput. Complex., 2022)

On information content in certain objects. - Nikolay K. Vereshchagin (CoRR, 2023)

Half-duplex communication complexity with adversary? can be less than the classical communication complexity. - Mikhail Dektiarev; Nikolai K. Vereshchagin (Electron. Colloquium Comput. Complex., 2023)

Information disclosure in the framework of Kolmogorov complexity. - Nikolay K. Vereshchagin (Theor. Comput. Sci., 2023)