Nikolai K. Vereshchagin

Publication Activity (10 Years)

Years Active: 1992-2023
Publications (10 Years): 13

Top Topics

Multi Modal Image Registration

Random Selection

Top Venues

Electron. Colloquium Comput. Complex.

IEEE Trans. Inf. Theory

Publications

Mikhail Dektiarev, Nikolai K. Vereshchagin
Half-duplex communication complexity with adversary? can be less than the classical communication complexity. Electron. Colloquium Comput. Complex. (2023)
Nikolai K. Vereshchagin
How Much Randomness is Needed to Convert MA Protocols to AM Protocols? CSR (2022)
Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir, Nikolai K. Vereshchagin
High Entropy Random Selection Protocols. Algorithmica 83 (2) (2021)
Nikolai K. Vereshchagin
Proofs of conservation inequalities for Levin's notion of mutual information of 1974. Theor. Comput. Sci. 856 (2021)
Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin
On the Structure of Ammann A2 Tilings. Discret. Comput. Geom. 63 (3) (2020)
Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolai K. Vereshchagin
Sparse Selfreducible Sets and Nonuniform Lower Bounds. Algorithmica 81 (1) (2019)
Bruno Bauwens, Anton Makhlin, Nikolai K. Vereshchagin, Marius Zimand
Short lists with short programs in short time. Comput. Complex. 27 (1) (2018)
Tarik Kaced, Andrei E. Romashchenko, Nikolai K. Vereshchagin
A Conditional Information Inequality and Its Combinatorial Applications. IEEE Trans. Inf. Theory 64 (5) (2018)
Alexey Milovanov, Nikolai K. Vereshchagin
Stochasticity in Algorithmic Statistics for Polynomial Time. Electron. Colloquium Comput. Complex. 24 (2017)
Nikolai K. Vereshchagin
Short lists with short programs from programs of functions and strings. Theory Comput. Syst. 61 (4) (2017)
Nikolai K. Vereshchagin, Alexander Shen
Algorithmic statistics: forty years later. CoRR (2016)
Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman, Nikolai K. Vereshchagin
Towards a Reverse Newman's Theorem in Interactive Information Complexity. Algorithmica 76 (3) (2016)
Nikolai K. Vereshchagin, Alexander Shen
Algorithmic statistics revisited. CoRR (2015)
Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin
Limit complexities revisited [once more] CoRR (2012)
Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolai K. Vereshchagin
Sparse Selfreducible Sets and Nonuniform Lower Bounds. Electron. Colloquium Comput. Complex. 17 (2010)
Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin
Limit Complexities Revisited. Theory Comput. Syst. 47 (3) (2010)
Nikolai K. Vereshchagin, Paul M. B. Vitányi
Rate distortion and denoising of individual data using Kolmogorov complexity. IEEE Trans. Inf. Theory 56 (7) (2010)
Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin
Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible? Theory Comput. Syst. 46 (1) (2010)
Andrej Muchnik, Ilya Mezhirov, Alexander Shen, Nikolai K. Vereshchagin
Game interpretation of Kolmogorov complexity CoRR (2010)
Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin
Limit complexities revisited CoRR (2008)
Alexey V. Chernov, Alexander Shen, Nikolai K. Vereshchagin, Vladimir Vovk
On-Line Probability, Complexity and Randomness. ALT (2008)
Harry Buhrman, Michal Koucký, Nikolai K. Vereshchagin
Randomised Individual Communication Complexity. Computational Complexity Conference (2008)
Ilya Mezhirov, Nikolai K. Vereshchagin
On Game Semantics of the Affine and Intuitionistic Logics. WoLLIC (2008)
Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin
Inverting Onto Functions and Polynomial Hierarchy. CSR (2007)
Nikolai K. Vereshchagin, Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir
High Entropy Random Selection Protocols. Algebraic Methods in Computational Complexity (2007)
Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai K. Vereshchagin
Partitioning multi-dimensional sets in a small number of "uniform" parts. Eur. J. Comb. 28 (1) (2007)
Harry Buhrman, Nikolai K. Vereshchagin, Ronald de Wolf
On Computation and Communication with Small Bias. Computational Complexity Conference (2007)
Andrej Muchnik, Alexander Shen, Mikhail Ustinov, Nikolai K. Vereshchagin, Michael V. Vyugin
Non-reducible descriptions for conditional Kolmogorov complexity. Theor. Comput. Sci. 384 (1) (2007)
Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi
Individual communication complexity. J. Comput. Syst. Sci. 73 (6) (2007)
Nikolai K. Vereshchagin
Kolmogorov complexity of enumerating finite sets. Inf. Process. Lett. 103 (1) (2007)
Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir, Nikolai K. Vereshchagin
High Entropy Random Selection Protocols. APPROX-RANDOM (2007)
Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin
Kolmogorov Complexity with Error. STACS (2006)
Andrei A. Muchnik, Nikolai K. Vereshchagin
Shannon Entropy vs. Kolmogorov Complexity. CSR (2006)
Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin
Inverting onto functions might not be hard. Electron. Colloquium Comput. Complex. 13 (024) (2006)
Nikolai K. Vereshchagin, Paul M. B. Vitányi
On Algorithmic Rate-Distortion Function. ISIT (2006)
Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin, Michael V. Vyugin
Non-reducible Descriptions for Conditional Kolmogorov Complexity. TAMC (2006)
Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai K. Vereshchagin
Partitioning multi-dimensional sets in a small number of "uniform" parts Electron. Colloquium Comput. Complex. (095) (2005)
Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin
Increasing Kolmogorov Complexity. STACS (2005)
Bruno Durand, Nikolai K. Vereshchagin
Kolmogorov-Loveland stochasticity for finite strings. Inf. Process. Lett. 91 (6) (2004)
Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi
Individual Communication Complexity: Extended Abstract. STACS (2004)
Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin
Increasing Kolmogorov Complexity Electron. Colloquium Comput. Complex. (081) (2004)
Nikolai K. Vereshchagin, Paul M. B. Vitányi
Kolmogorov's structure functions and model selection. IEEE Trans. Inf. Theory 50 (12) (2004)
Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin
Kolmogorov Complexity with Error Electron. Colloquium Comput. Complex. (080) (2004)
Andrei A. Muchnik, Alexander Shen, Nikolai K. Vereshchagin, Michael V. Vyugin
Non-reducible descriptions for conditional Kolmogorov complexity Electron. Colloquium Comput. Complex. (054) (2004)
Bruno Durand, Andrei A. Muchnik, Maxim Ushakov, Nikolai K. Vereshchagin
Ecological Turing Machines. ICALP (2004)
Nikolai K. Vereshchagin
Kolmogorov complexity of enumerating finite sets Electron. Colloquium Comput. Complex. (030) (2004)
Nikolai K. Vereshchagin, Paul M. B. Vitányi
A Theory of Lossy Compression for Individual Data CoRR (2004)
Olga Mitina, Nikolai K. Vereshchagin
How to use several noisy channels with unknown error probabilities. Inf. Comput. 184 (2) (2003)
Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi
Individual Communication Complexity CoRR (2003)
Bruno Durand, Vladimir Kanovei, Vladimir A. Uspensky, Nikolai K. Vereshchagin
Do stronger definitions of randomness exist? Theor. Comput. Sci. 290 (3) (2003)
Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin
Descriptive complexity of computable sequences. Theor. Comput. Sci. 271 (1-2) (2002)
Alexey V. Chernov, Dmitrij P. Skvortsov, Elena Z. Skvortsova, Nikolai K. Vereshchagin
Variants of Realizability for Propositional Formulas and the Logic of the Weak Law of Excluded Middle. CSL (2002)
Alexander Shen, Nikolai K. Vereshchagin
Logical operations and Kolmogorov complexity. Theor. Comput. Sci. 271 (1-2) (2002)
Konstantin Makarychev, Yury Makarychev, Andrei E. Romashchenko, Nikolai K. Vereshchagin
A new class of non-Shannon-type inequalities for entropies. Commun. Inf. Syst. 2 (2) (2002)
Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
Combinatorial interpretation of Kolmogorov complexity. Theor. Comput. Sci. 271 (1-2) (2002)
Nikolai K. Vereshchagin, Paul M. B. Vitányi
Kolmogorov's Structure Functions with an Application to the Foundations of Model Selection CoRR (2002)
Nikolai K. Vereshchagin, Michael V. Vyugin
Independent minimum length programs to translate between given strings. Theor. Comput. Sci. 271 (1-2) (2002)
Nikolai K. Vereshchagin
Kolmogorov complexity conditional to large integers. Theor. Comput. Sci. 271 (1-2) (2002)
Nikolai K. Vereshchagin, Paul M. B. Vitányi
Kolmogorov's Structure Functions with an Application to the Foundations of Model Selection. FOCS (2002)
Alexey V. Chernov, Andrei A. Muchnik, Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
Upper semi-lattice of binary strings with the relation "x is simple conditional to y". Theor. Comput. Sci. 271 (1-2) (2002)
Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin
Descriptive complexity of computable sequences Electron. Colloquium Comput. Complex. (087) (2001)
Alexander Shen, Nikolai K. Vereshchagin
Logical operations and Kolmogorov complexity Electron. Colloquium Comput. Complex. (088) (2001)
Nikolai K. Vereshchagin
An enumerable undecidable set with low prefix complexity: a simplified proof Electron. Colloquium Comput. Complex. (083) (2001)
Andrei A. Muchnik, Nikolai K. Vereshchagin
Logical operations and Kolmogorov complexity. II Electron. Colloquium Comput. Complex. (089) (2001)
Andrei A. Muchnik, Nikolai K. Vereshchagin
Logical Operations and Kolmogorov Complexity II. Computational Complexity Conference (2001)
Nikolai K. Vereshchagin
Kolmogorov Complexity Conditional to Large Integers Electron. Colloquium Comput. Complex. (086) (2001)
Nikolai K. Vereshchagin, Michael V. Vyugin
Independent Minimum Length Programs to Translate between Given Strings. Computational Complexity Conference (2000)
Daniel Hammer, Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
Inequalities for Shannon Entropy and Kolmogorov Complexity. J. Comput. Syst. Sci. 60 (2) (2000)
Nikolai K. Vereshchagin, Michael V. Vyugin
Independent minimum length programs to translate between given strings Electron. Colloquium Comput. Complex. 7 (35) (2000)
Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
Combinatorial Interpretation of Kolmogorov Complexity Electron. Colloquium Comput. Complex. 7 (26) (2000)
Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
Combinatorial Interpretation of Kolmogorov Complexity. Computational Complexity Conference (2000)
Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin
Descriptive Complexity of Computable Sequences. STACS (1999)
Andrei A. Muchnik, Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
Upper Semilattice of Binary Strings with the Relation "x is Simple Conditional to y". Computational Complexity Conference (1999)
Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin
Arthur-Merlin Games in Boolean Decision Trees. J. Comput. Syst. Sci. 59 (2) (1999)
Alexander A. Razborov, Nikolai K. Vereshchagin
One Property of Cross-Intersecting Families Electron. Colloquium Comput. Complex. 6 (14) (1999)
Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin
Arthur-Merlin Games in Boolean Decision Trees. Computational Complexity Conference (1998)
Sylvain Porrot, Max Dauchet, Bruno Durand, Nikolai K. Vereshchagin
Deterministic Rational Transducers and Random Sequences. FoSSaCS (1998)
Nikolai K. Vereshchagin
Randomized Boolean Decision Trees: Several Remarks. Theor. Comput. Sci. 207 (2) (1998)
Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin
Arthur-Merlin Games in Boolean Decision Trees Electron. Colloquium Comput. Complex. 4 (54) (1997)
Daniel Hammer, Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
Inequalities for Shannon entropies and Kolmogorov complexities. Computational Complexity Conference (1997)
Andrei A. Muchnik, Nikolai K. Vereshchagin
A General Method to Construct Oracles Realizing Given Relationships Between Complexity Classes. Theor. Comput. Sci. 157 (2) (1996)
Olga Mitina, Nikolai K. Vereshchagin
How to Use Expert Advice in the Case when Actual Values of Estimated Events Remain Unknown. COLT (1995)
Nikolai K. Vereshchagin
Lower Bounds for Perceptrons Solving some Separation Problems and Oracle Separation of AM from PP. ISTCS (1995)
Nikolai K. Vereshchagin
NP-sets are Co-NP-immune Relative to a Random Oracle. ISTCS (1995)
Lane A. Hemaspaandra, Sanjay Jain, Nikolai K. Vereshchagin
Banishing Robust Turing Completeness. Int. J. Found. Comput. Sci. 4 (3) (1993)
Nikolai K. Vereshchagin
Relationships between NP-sets, Co-NP-sets, and P-sets relative to random oracles. Computational Complexity Conference (1993)
Nikolai K. Vereshchagin
On The Power of PP. Computational Complexity Conference (1992)
Lane A. Hemachandra, Sanjay Jain, Nikolai K. Vereshchagin
Banishing Robust Turing Completeness. LFCS (1992)