Nikolai K. Vereshchagin

Nikolay K. Vereshchagin

	2013
i26		Bruno Bauwens, Anton Makhlin, Nikolay K. Vereshchagin, Marius Zimand: Short lists with short programs in short time. CoRR abs/1301.1547 (2013)
i25		Bruno Bauwens, Anton Makhlin, Nikolay K. Vereshchagin, Marius Zimand: Short lists with short programs in short time. Electronic Colloquium on Computational Complexity (ECCC) 20: 7 (2013)
	2012
i24		Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin: Limit complexities revisited [once more]. CoRR abs/1204.0201 (2012)
	2011
j25		Nikolay K. Vereshchagin: 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". Electronic Colloquium on Computational Complexity (ECCC) 18: 167 (2011)
e1		Alexander S. Kulikov, Nikolay K. Vereshchagin (Eds.): Computer Science - Theory and Applications - 6th International Computer Science Symposium in Russia, CSR 2011, St. Petersburg, Russia, June 14-18, 2011. Proceedings. Lecture Notes in Computer Science 6651, Springer 2011, isbn 978-3-642-20711-2
	2010
j24		Ilya Mezhirov, Nikolay K. Vereshchagin: On abstract resource semantics and computability logic. J. Comput. Syst. Sci. 76(5): 356-372 (2010)
j23		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): 143-156 (2010)
j22		Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin: Limit Complexities Revisited. Theory Comput. Syst. 47(3): 720-736 (2010)
j21		Nikolai K. Vereshchagin, Paul M. B. Vitányi: Rate distortion and denoising of individual data using Kolmogorov complexity. IEEE Transactions on Information Theory 56(7): 3438-3454 (2010)
c32		Nikolay K. Vereshchagin: An Encoding Invariant Version of Polynomial Time Computable Distributions. CSR 2010: 371-383
i23		Andrej Muchnik, Ilya Mezhirov, Alexander Shen, Nikolai K. Vereshchagin: Game interpretation of Kolmogorov complexity. CoRR abs/1003.4712 (2010)
i22		Nikolay K. Vereshchagin: {Algorithmic Minimal Sufficient Statistics: a New Definition. Electronic Colloquium on Computational Complexity (ECCC) 17: 90 (2010)
i21		Nikolay K. Vereshchagin: An Encoding Invariant Version of Polynomial Time Computable Distributions. Electronic Colloquium on Computational Complexity (ECCC) 17: 91 (2010)
i20		Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolai K. Vereshchagin: Sparse Selfreducible Sets and Nonuniform Lower Bounds. Electronic Colloquium on Computational Complexity (ECCC) 17: 163 (2010)
	2009
c31		Nikolay K. Vereshchagin: Algorithmic Minimal Sufficient Statistic Revisited. CiE 2009: 478-487
c30		Nikolay K. Vereshchagin: Kolmogorov Complexity and Model Selection. CSR 2009: 19-24
	2008
j20		Nikolay K. Vereshchagin: Kolmogorov Complexity and Games. Bulletin of the EATCS 94: 43-75 (2008)
c29		Alexey V. Chernov, Alexander Shen, Nikolai K. Vereshchagin, Vladimir Vovk: On-Line Probability, Complexity and Randomness. ALT 2008: 138-153
c28		Harry Buhrman, Michal Koucký, Nikolai K. Vereshchagin: Randomised Individual Communication Complexity. IEEE Conference on Computational Complexity 2008: 321-331
c27		Ilya Mezhirov, Nikolai K. Vereshchagin: On Game Semantics of the Affine and Intuitionistic Logics. WoLLIC 2008: 28-42
i19		Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin: Limit complexities revisited. CoRR abs/0802.2833 (2008)
	2007
j19		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): 134-144 (2007)
j18		Nikolai K. Vereshchagin: Kolmogorov complexity of enumerating finite sets. Inf. Process. Lett. 103(1): 34-39 (2007)
j17		Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi: Individual communication complexity. J. Comput. Syst. Sci. 73(6): 973-985 (2007)
j16		Andrej Muchnik, Alexander Shen, Mikhail Ustinov, Nikolai K. Vereshchagin, Michael V. Vyugin: Non-reducible descriptions for conditional Kolmogorov complexity. Theor. Comput. Sci. 384(1): 77-86 (2007)
c26		Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir, Nikolai K. Vereshchagin: High Entropy Random Selection Protocols. APPROX-RANDOM 2007: 366-379
c25		Harry Buhrman, Nikolai K. Vereshchagin, Ronald de Wolf: On Computation and Communication with Small Bias. IEEE Conference on Computational Complexity 2007: 24-32
c24		Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin: Inverting Onto Functions and Polynomial Hierarchy. CSR 2007: 92-103
c23		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
	2006
c22		Andrei A. Muchnik, Nikolai K. Vereshchagin: Shannon Entropy vs. Kolmogorov Complexity. CSR 2006: 281-291
c21		Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin: Kolmogorov Complexity with Error. STACS 2006: 137-148
c20		Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin, Michael V. Vyugin: Non-reducible Descriptions for Conditional Kolmogorov Complexity. TAMC 2006: 308-317
i18		Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin: Inverting onto functions might not be hard. Electronic Colloquium on Computational Complexity (ECCC) 13(024) (2006)
	2005
c19		Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin: Increasing Kolmogorov Complexity. STACS 2005: 412-421
i17		Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai K. Vereshchagin: Partitioning multi-dimensional sets in a small number of ``uniform'' parts. Electronic Colloquium on Computational Complexity (ECCC)(095) (2005)
	2004
j15		Bruno Durand, Nikolai K. Vereshchagin: Kolmogorov-Loveland stochasticity for finite strings. Inf. Process. Lett. 91(6): 263-269 (2004)
j14		Nikolai K. Vereshchagin, Paul M. B. Vitányi: Kolmogorov's structure functions and model selection. IEEE Transactions on Information Theory 50(12): 3265-3290 (2004)
c18		Bruno Durand, Andrei A. Muchnik, Maxim Ushakov, Nikolai K. Vereshchagin: Ecological Turing Machines. ICALP 2004: 457-468
c17		Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi: Individual Communication Complexity: Extended Abstract. STACS 2004: 19-30
i16		Nikolai K. Vereshchagin, Paul M. B. Vitányi: A Theory of Lossy Compression for Individual Data. CoRR cs.IT/0411014 (2004)
i15		Nikolai K. Vereshchagin: Kolmogorov complexity of enumerating finite sets. Electronic Colloquium on Computational Complexity (ECCC)(030) (2004)
i14		Andrei A. Muchnik, Alexander Shen, Nikolai K. Vereshchagin, Michael V. Vyugin: Non-reducible descriptions for conditional Kolmogorov complexity. Electronic Colloquium on Computational Complexity (ECCC)(054) (2004)
i13		Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin: Kolmogorov Complexity with Error. Electronic Colloquium on Computational Complexity (ECCC)(080) (2004)
i12		Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin: Increasing Kolmogorov Complexity. Electronic Colloquium on Computational Complexity (ECCC)(081) (2004)
	2003
j13		Olga Mitina, Nikolai K. Vereshchagin: How to use several noisy channels with unknown error probabilities. Inf. Comput. 184(2): 229-241 (2003)
j12		Bruno Durand, Vladimir Kanovei, Vladimir A. Uspensky, Nikolai K. Vereshchagin: Do stronger definitions of randomness exist? Theor. Comput. Sci. 290(3): 1987-1996 (2003)
i11		Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi: Individual Communication Complexity. CoRR cs.CC/0304012 (2003)
	2002
j11		Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin: Descriptive complexity of computable sequences. Theor. Comput. Sci. 271(1-2): 47-58 (2002)
j10		Nikolai K. Vereshchagin: Kolmogorov complexity conditional to large integers. Theor. Comput. Sci. 271(1-2): 59-67 (2002)
j9		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): 69-95 (2002)
j8		Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin: Combinatorial interpretation of Kolmogorov complexity. Theor. Comput. Sci. 271(1-2): 111-123 (2002)
j7		Alexander Shen, Nikolai K. Vereshchagin: Logical operations and Kolmogorov complexity. Theor. Comput. Sci. 271(1-2): 125-129 (2002)
j6		Nikolai K. Vereshchagin, Michael V. Vyugin: Independent minimum length programs to translate between given strings. Theor. Comput. Sci. 271(1-2): 131-143 (2002)
c16		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: 74-88
c15		Nikolai K. Vereshchagin, Paul M. B. Vitányi: Kolmogorov's Structure Functions with an Application to the Foundations of Model Selection. FOCS 2002: 751-760
i10		Nikolai K. Vereshchagin, Paul M. B. Vitányi: Kolmogorov's Structure Functions with an Application to the Foundations of Model Selection. CoRR cs.CC/0204037 (2002)
	2001
c14		Andrei A. Muchnik, Nikolai K. Vereshchagin: Logical Operations and Kolmogorov Complexity II. IEEE Conference on Computational Complexity 2001: 256-265
i9		Nikolai K. Vereshchagin: An enumerable undecidable set with low prefix complexity: a simplified proof. Electronic Colloquium on Computational Complexity (ECCC)(083) (2001)
i8		Nikolai K. Vereshchagin: Kolmogorov Complexity Conditional to Large Integers. Electronic Colloquium on Computational Complexity (ECCC)(086) (2001)
i7		Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin: Descriptive complexity of computable sequences. Electronic Colloquium on Computational Complexity (ECCC)(087) (2001)
i6		Alexander Shen, Nikolai K. Vereshchagin: Logical operations and Kolmogorov complexity. Electronic Colloquium on Computational Complexity (ECCC)(088) (2001)
i5		Andrei A. Muchnik, Nikolai K. Vereshchagin: Logical operations and Kolmogorov complexity. II. Electronic Colloquium on Computational Complexity (ECCC)(089) (2001)
	2000
j5		Daniel Hammer, Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin: Inequalities for Shannon Entropy and Kolmogorov Complexity. J. Comput. Syst. Sci. 60(2): 442-464 (2000)
c13		Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin: Combinatorial Interpretation of Kolmogorov Complexity. IEEE Conference on Computational Complexity 2000: 131-137
c12		Nikolai K. Vereshchagin, Michael V. Vyugin: Independent Minimum Length Programs to Translate between Given Strings. IEEE Conference on Computational Complexity 2000: 138-
i4		Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin: Combinatorial Interpretation of Kolmogorov Complexity. Electronic Colloquium on Computational Complexity (ECCC) 7(26) (2000)
i3		Nikolai K. Vereshchagin, Michael V. Vyugin: Independent minimum length programs to translate between given strings. Electronic Colloquium on Computational Complexity (ECCC) 7(35) (2000)
	1999
j4		Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin: Arthur-Merlin Games in Boolean Decision Trees. J. Comput. Syst. Sci. 59(2): 346-372 (1999)
c11		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". IEEE Conference on Computational Complexity 1999: 114-
c10		Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin: Descriptive Complexity of Computable Sequences. STACS 1999: 153-162
i2		Alexander A. Razborov, Nikolai K. Vereshchagin: One Property of Cross-Intersecting Families. Electronic Colloquium on Computational Complexity (ECCC) 6(14) (1999)
	1998
j3		Nikolai K. Vereshchagin: Randomized Boolean Decision Trees: Several Remarks. Theor. Comput. Sci. 207(2): 329-342 (1998)
c9		Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin: Arthur-Merlin Games in Boolean Decision Trees. IEEE Conference on Computational Complexity 1998: 58-67
c8		Sylvain Porrot, Max Dauchet, Bruno Durand, Nikolai K. Vereshchagin: Deterministic Rational Transducers and Random Sequences. FoSSaCS 1998: 258-272
	1997
c7		Daniel Hammer, Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin: Inequalities for Shannon entropies and Kolmogorov complexities. IEEE Conference on Computational Complexity 1997: 13-23
i1		Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin: Arthur-Merlin Games in Boolean Decision Trees. Electronic Colloquium on Computational Complexity (ECCC) 4(54) (1997)
	1996
j2		Andrei A. Muchnik, Nikolai K. Vereshchagin: A General Method to Construct Oracles Realizing Given Relationships Between Complexity Classes. Theor. Comput. Sci. 157(2): 227-258 (1996)
	1995
c6		Olga Mitina, Nikolai K. Vereshchagin: How to Use Expert Advice in the Case when Actual Values of Estimated Events Remain Unknown. COLT 1995: 91-97
c5		Nikolai K. Vereshchagin: NP-sets are Co-NP-immune Relative to a Random Oracle. ISTCS 1995: 40-45
c4		Nikolai K. Vereshchagin: Lower Bounds for Perceptrons Solving some Separation Problems and Oracle Separation of AM from PP. ISTCS 1995: 46-51
	1993
j1		Lane A. Hemaspaandra, Sanjay Jain, Nikolai K. Vereshchagin: Banishing Robust Turing Completeness. Int. J. Found. Comput. Sci. 4(3): 245-265 (1993)
c3		Nikolai K. Vereshchagin: Relationships between NP-sets, Co-NP-sets, and P-sets relative to random oracles. Structure in Complexity Theory Conference 1993: 132-138
	1992
c2		Nikolai K. Vereshchagin: On The Power of PP. Structure in Complexity Theory Conference 1992: 138-143
c1		Lane A. Hemachandra, Sanjay Jain, Nikolai K. Vereshchagin: Banishing Robust Turing Completeness. LFCS 1992: 186-197

Coauthor Index

Last update Wed May 22 23:52:43 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page