Nikolai K. Vereshchagin

	2008
67		Alexey V. Chernov, Alexander Shen, Nikolai K. Vereshchagin, Vladimir Vovk: On-Line Probability, Complexity and Randomness. ALT 2008: 138-153
66		Harry Buhrman, Michal Koucký, Nikolai K. Vereshchagin: Randomised Individual Communication Complexity. IEEE Conference on Computational Complexity 2008: 321-331
65		Ilya Mezhirov, Nikolai K. Vereshchagin: On Game Semantics of the Affine and Intuitionistic Logics. WoLLIC 2008: 28-42
64		Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin: Limit complexities revisited CoRR abs/0802.2833: (2008)
	2007
63		Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir, Nikolai K. Vereshchagin: High Entropy Random Selection Protocols. APPROX-RANDOM 2007: 366-379
62		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
61		Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin: Inverting Onto Functions and Polynomial Hierarchy. CSR 2007: 92-103
60		Harry Buhrman, Nikolai K. Vereshchagin, Ronald de Wolf: On Computation and Communication with Small Bias. IEEE Conference on Computational Complexity 2007: 24-32
59		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)
58		Nikolai K. Vereshchagin: Kolmogorov complexity of enumerating finite sets. Inf. Process. Lett. 103(1): 34-39 (2007)
57		Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi: Individual communication complexity. J. Comput. Syst. Sci. 73(6): 973-985 (2007)
56		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)
	2006
55		Andrei A. Muchnik, Nikolai K. Vereshchagin: Shannon Entropy vs. Kolmogorov Complexity. CSR 2006: 281-291
54		Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin: Kolmogorov Complexity with Error. STACS 2006: 137-148
53		Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin, Michael V. Vyugin: Non-reducible Descriptions for Conditional Kolmogorov Complexity. TAMC 2006: 308-317
52		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
51		Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin: Increasing Kolmogorov Complexity. STACS 2005: 412-421
50		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
49		Bruno Durand, Andrei A. Muchnik, Maxim Ushakov, Nikolai K. Vereshchagin: Ecological Turing Machines. ICALP 2004: 457-468
48		Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi: Individual Communication Complexity: Extended Abstract. STACS 2004: 19-30
47		Nikolai K. Vereshchagin, Paul M. B. Vitányi: A Theory of Lossy Compression for Individual Data CoRR cs.IT/0411014: (2004)
46		Nikolai K. Vereshchagin: Kolmogorov complexity of enumerating finite sets Electronic Colloquium on Computational Complexity (ECCC)(030): (2004)
45		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)
44		Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin: Kolmogorov Complexity with Error Electronic Colloquium on Computational Complexity (ECCC)(080): (2004)
43		Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin: Increasing Kolmogorov Complexity Electronic Colloquium on Computational Complexity (ECCC)(081): (2004)
42		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)
41		Bruno Durand, Nikolai K. Vereshchagin: Kolmogorov-Loveland stochasticity for finite strings. Inf. Process. Lett. 91(6): 263-269 (2004)
	2003
40		Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi: Individual Communication Complexity CoRR cs.CC/0304012: (2003)
39		Olga Mitina, Nikolai K. Vereshchagin: How to use several noisy channels with unknown error probabilities. Inf. Comput. 184(2): 229-241 (2003)
38		Bruno Durand, Vladimir Kanovei, Vladimir A. Uspensky, Nikolai K. Vereshchagin: Do stronger definitions of randomness exist? Theor. Comput. Sci. 290(3): 1987-1996 (2003)
	2002
37		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
36		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
35		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)
34		Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin: Combinatorial interpretation of Kolmogorov complexity. Theor. Comput. Sci. 271(1-2): 111-123 (2002)
33		Alexander Shen, Nikolai K. Vereshchagin: Logical operations and Kolmogorov complexity. Theor. Comput. Sci. 271(1-2): 125-129 (2002)
32		Nikolai K. Vereshchagin, Michael V. Vyugin: Independent minimum length programs to translate between given strings. Theor. Comput. Sci. 271(1-2): 131-143 (2002)
31		Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin: Descriptive complexity of computable sequences. Theor. Comput. Sci. 271(1-2): 47-58 (2002)
30		Nikolai K. Vereshchagin: Kolmogorov complexity conditional to large integers. Theor. Comput. Sci. 271(1-2): 59-67 (2002)
29		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)
	2001
28		Andrei A. Muchnik, Nikolai K. Vereshchagin: Logical Operations and Kolmogorov Complexity II. IEEE Conference on Computational Complexity 2001: 256-265
27		Nikolai K. Vereshchagin: An enumerable undecidable set with low prefix complexity: a simplified proof Electronic Colloquium on Computational Complexity (ECCC)(083): (2001)
26		Nikolai K. Vereshchagin: Kolmogorov Complexity Conditional to Large Integers Electronic Colloquium on Computational Complexity (ECCC)(086): (2001)
25		Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin: Descriptive complexity of computable sequences Electronic Colloquium on Computational Complexity (ECCC)(087): (2001)
24		Alexander Shen, Nikolai K. Vereshchagin: Logical operations and Kolmogorov complexity Electronic Colloquium on Computational Complexity (ECCC)(088): (2001)
23		Andrei A. Muchnik, Nikolai K. Vereshchagin: Logical operations and Kolmogorov complexity. II Electronic Colloquium on Computational Complexity (ECCC)(089): (2001)
	2000
22		Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin: Combinatorial Interpretation of Kolmogorov Complexity. IEEE Conference on Computational Complexity 2000: 131-137
21		Nikolai K. Vereshchagin, Michael V. Vyugin: Independent Minimum Length Programs to Translate between Given Strings. IEEE Conference on Computational Complexity 2000: 138-
20		Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin: Combinatorial Interpretation of Kolmogorov Complexity Electronic Colloquium on Computational Complexity (ECCC) 7(26): (2000)
19		Nikolai K. Vereshchagin, Michael V. Vyugin: Independent minimum length programs to translate between given strings Electronic Colloquium on Computational Complexity (ECCC) 7(35): (2000)
18		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)
	1999
17		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-
16		Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin: Descriptive Complexity of Computable Sequences. STACS 1999: 153-162
15		Alexander A. Razborov, Nikolai K. Vereshchagin: One Property of Cross-Intersecting Families Electronic Colloquium on Computational Complexity (ECCC) 6(14): (1999)
14		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)
	1998
13		Sylvain Porrot, Max Dauchet, Bruno Durand, Nikolai K. Vereshchagin: Deterministic Rational Transducers and Random Sequences. FoSSaCS 1998: 258-272
12		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
11		Nikolai K. Vereshchagin: Randomized Boolean Decision Trees: Several Remarks. Theor. Comput. Sci. 207(2): 329-342 (1998)
	1997
10		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
9		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
8		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
7		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
6		Nikolai K. Vereshchagin: NP-sets are Co-NP-immune Relative to a Random Oracle. ISTCS 1995: 40-45
5		Nikolai K. Vereshchagin: Lower Bounds for Perceptrons Solving some Separation Problems and Oracle Separation of AM from PP. ISTCS 1995: 46-51
	1993
4		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
3		Lane A. Hemaspaandra, Sanjay Jain, Nikolai K. Vereshchagin: Banishing Robust Turing Completeness. Int. J. Found. Comput. Sci. 4(3): 245-265 (1993)
	1992
2		Lane A. Hemachandra, Sanjay Jain, Nikolai K. Vereshchagin: Banishing Robust Turing Completeness. LFCS 1992: 186-197
1		Nikolai K. Vereshchagin: On The Power of PP. Structure in Complexity Theory Conference 1992: 138-143

Coauthor Index

1	Noga Alon	[50] [59]
2	Laurent Bienvenu	[64]
3	Harry Buhrman	[40] [43] [48] [51] [52] [57] [60] [61] [62] [63] [66]
4	Alexey V. Chernov	[29] [37] [67]
5	Matthias Christandl	[62] [63]
6	Max Dauchet	[13]
7	Bruno Durand	[13] [16] [25] [31] [38] [41] [49]
8	Lance Fortnow	[43] [44] [51] [52] [54] [61]
9	Daniel Hammer	[10] [18]
10	Lane A. Hemaspaandra (Lane A. Hemachandra)	[2] [3]
11	Sanjay Jain	[2] [3]
12	Vladimir Kanovei	[38]
13	Hartmut Klauck	[40] [48] [57]
14	Michal Koucký	[52] [61] [62] [63] [66]
15	Troy Lee	[44] [54]
16	Zvi Lotker	[62] [63]
17	Ilya Mezhirov	[65]
18	Olga Mitina	[7] [39]
19	Andrej Muchnik (Andrei A. Muchnik)	[8] [17] [23] [28] [29] [45] [49] [53] [55] [56] [64]
20	Ilan Newman	[43] [50] [51] [59]
21	Boaz Patt-Shamir	[62] [63]
22	Sylvain Porrot	[13]
23	Ran Raz	[9] [12] [14]
24	Alexander A. Razborov	[15]
25	John D. Rogers	[52] [61]
26	Andrei E. Romashchenko	[10] [17] [18] [20] [22] [29] [34]
27	Alexander Shen	[10] [16] [17] [18] [20] [22] [24] [25] [29] [31] [33] [34] [45] [50] [53] [56] [59] [64] [67]
28	Dmitrij P. Skvortsov	[37]
29	Elena Z. Skvortsova	[37]
30	Gábor Tardos	[9] [12] [14] [50] [59]
31	Maxim Ushakov	[49]
32	Vladimir A. Uspensky	[38]
33	Mikhail Ustinov	[56]
34	Oleg Verbitsky	[9] [12] [14]
35	Paul M. B. Vitányi	[35] [36] [40] [42] [47] [48] [57]
36	Vladimir Vovk (Volodya Vovk, V. G. Vovk)	[67]
37	Michael V. Vyugin	[19] [21] [32] [45] [53] [56]
38	Ronald de Wolf	[60]

Colors in the list of coauthors