dblp.uni-trier.dewww.uni-trier.de

Nikolai K. Vereshchagin

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeer - CSB - Google - MSN - Yahoo

2008
67EEAlexey V. Chernov, Alexander Shen, Nikolai K. Vereshchagin, Vladimir Vovk: On-Line Probability, Complexity and Randomness. ALT 2008: 138-153
66EEHarry Buhrman, Michal Koucký, Nikolai K. Vereshchagin: Randomised Individual Communication Complexity. IEEE Conference on Computational Complexity 2008: 321-331
65EEIlya Mezhirov, Nikolai K. Vereshchagin: On Game Semantics of the Affine and Intuitionistic Logics. WoLLIC 2008: 28-42
64EELaurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin: Limit complexities revisited CoRR abs/0802.2833: (2008)
2007
63EEHarry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir, Nikolai K. Vereshchagin: High Entropy Random Selection Protocols. APPROX-RANDOM 2007: 366-379
62EENikolai K. Vereshchagin, Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir: High Entropy Random Selection Protocols. Algebraic Methods in Computational Complexity 2007
61EEHarry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin: Inverting Onto Functions and Polynomial Hierarchy. CSR 2007: 92-103
60EEHarry Buhrman, Nikolai K. Vereshchagin, Ronald de Wolf: On Computation and Communication with Small Bias. IEEE Conference on Computational Complexity 2007: 24-32
59EENoga 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)
58EENikolai K. Vereshchagin: Kolmogorov complexity of enumerating finite sets. Inf. Process. Lett. 103(1): 34-39 (2007)
57EEHarry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi: Individual communication complexity. J. Comput. Syst. Sci. 73(6): 973-985 (2007)
56EEAndrej 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
55EEAndrei A. Muchnik, Nikolai K. Vereshchagin: Shannon Entropy vs. Kolmogorov Complexity. CSR 2006: 281-291
54EELance Fortnow, Troy Lee, Nikolai K. Vereshchagin: Kolmogorov Complexity with Error. STACS 2006: 137-148
53EEAndrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin, Michael V. Vyugin: Non-reducible Descriptions for Conditional Kolmogorov Complexity. TAMC 2006: 308-317
52EEHarry 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
51EEHarry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin: Increasing Kolmogorov Complexity. STACS 2005: 412-421
50EENoga 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
49EEBruno Durand, Andrei A. Muchnik, Maxim Ushakov, Nikolai K. Vereshchagin: Ecological Turing Machines. ICALP 2004: 457-468
48EEHarry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi: Individual Communication Complexity: Extended Abstract. STACS 2004: 19-30
47EENikolai K. Vereshchagin, Paul M. B. Vitányi: A Theory of Lossy Compression for Individual Data CoRR cs.IT/0411014: (2004)
46EENikolai K. Vereshchagin: Kolmogorov complexity of enumerating finite sets Electronic Colloquium on Computational Complexity (ECCC)(030): (2004)
45EEAndrei 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)
44EELance Fortnow, Troy Lee, Nikolai K. Vereshchagin: Kolmogorov Complexity with Error Electronic Colloquium on Computational Complexity (ECCC)(080): (2004)
43EEHarry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin: Increasing Kolmogorov Complexity Electronic Colloquium on Computational Complexity (ECCC)(081): (2004)
42EENikolai K. Vereshchagin, Paul M. B. Vitányi: Kolmogorov's structure functions and model selection. IEEE Transactions on Information Theory 50(12): 3265-3290 (2004)
41EEBruno Durand, Nikolai K. Vereshchagin: Kolmogorov-Loveland stochasticity for finite strings. Inf. Process. Lett. 91(6): 263-269 (2004)
2003
40EEHarry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi: Individual Communication Complexity CoRR cs.CC/0304012: (2003)
39EEOlga 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
37EEAlexey 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
36EENikolai K. Vereshchagin, Paul M. B. Vitányi: Kolmogorov's Structure Functions with an Application to the Foundations of Model Selection. FOCS 2002: 751-760
35EENikolai 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)
34EEAndrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin: Combinatorial interpretation of Kolmogorov complexity. Theor. Comput. Sci. 271(1-2): 111-123 (2002)
33EEAlexander Shen, Nikolai K. Vereshchagin: Logical operations and Kolmogorov complexity. Theor. Comput. Sci. 271(1-2): 125-129 (2002)
32EENikolai K. Vereshchagin, Michael V. Vyugin: Independent minimum length programs to translate between given strings. Theor. Comput. Sci. 271(1-2): 131-143 (2002)
31EEBruno Durand, Alexander Shen, Nikolai K. Vereshchagin: Descriptive complexity of computable sequences. Theor. Comput. Sci. 271(1-2): 47-58 (2002)
30EENikolai K. Vereshchagin: Kolmogorov complexity conditional to large integers. Theor. Comput. Sci. 271(1-2): 59-67 (2002)
29EEAlexey 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
28EEAndrei A. Muchnik, Nikolai K. Vereshchagin: Logical Operations and Kolmogorov Complexity II. IEEE Conference on Computational Complexity 2001: 256-265
27EENikolai K. Vereshchagin: An enumerable undecidable set with low prefix complexity: a simplified proof Electronic Colloquium on Computational Complexity (ECCC)(083): (2001)
26EENikolai K. Vereshchagin: Kolmogorov Complexity Conditional to Large Integers Electronic Colloquium on Computational Complexity (ECCC)(086): (2001)
25EEBruno Durand, Alexander Shen, Nikolai K. Vereshchagin: Descriptive complexity of computable sequences Electronic Colloquium on Computational Complexity (ECCC)(087): (2001)
24EEAlexander Shen, Nikolai K. Vereshchagin: Logical operations and Kolmogorov complexity Electronic Colloquium on Computational Complexity (ECCC)(088): (2001)
23EEAndrei A. Muchnik, Nikolai K. Vereshchagin: Logical operations and Kolmogorov complexity. II Electronic Colloquium on Computational Complexity (ECCC)(089): (2001)
2000
22EEAndrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin: Combinatorial Interpretation of Kolmogorov Complexity. IEEE Conference on Computational Complexity 2000: 131-137
21EENikolai K. Vereshchagin, Michael V. Vyugin: Independent Minimum Length Programs to Translate between Given Strings. IEEE Conference on Computational Complexity 2000: 138-
20EEAndrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin: Combinatorial Interpretation of Kolmogorov Complexity Electronic Colloquium on Computational Complexity (ECCC) 7(26): (2000)
19EENikolai 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
17EEAndrei 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-
16EEBruno Durand, Alexander Shen, Nikolai K. Vereshchagin: Descriptive Complexity of Computable Sequences. STACS 1999: 153-162
15EEAlexander 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
13EESylvain Porrot, Max Dauchet, Bruno Durand, Nikolai K. Vereshchagin: Deterministic Rational Transducers and Random Sequences. FoSSaCS 1998: 258-272
12EERan Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin: Arthur-Merlin Games in Boolean Decision Trees. IEEE Conference on Computational Complexity 1998: 58-67
11EENikolai K. Vereshchagin: Randomized Boolean Decision Trees: Several Remarks. Theor. Comput. Sci. 207(2): 329-342 (1998)
1997
10EEDaniel Hammer, Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin: Inequalities for Shannon entropies and Kolmogorov complexities. IEEE Conference on Computational Complexity 1997: 13-23
9EERan 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
8EEAndrei 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
7EEOlga 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

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

Colors in the list of coauthors

Copyright © Sun May 17 03:24:02 2009 by Michael Ley (ley@uni-trier.de)