| 2008 |
|---|
| 67 | EE | Alexey V. Chernov,
Alexander Shen,
Nikolai K. Vereshchagin,
Vladimir Vovk:
On-Line Probability, Complexity and Randomness.
ALT 2008: 138-153 |
| 66 | EE | Harry Buhrman,
Michal Koucký,
Nikolai K. Vereshchagin:
Randomised Individual Communication Complexity.
IEEE Conference on Computational Complexity 2008: 321-331 |
| 65 | EE | Ilya Mezhirov,
Nikolai K. Vereshchagin:
On Game Semantics of the Affine and Intuitionistic Logics.
WoLLIC 2008: 28-42 |
| 64 | EE | Laurent Bienvenu,
Andrej Muchnik,
Alexander Shen,
Nikolai K. Vereshchagin:
Limit complexities revisited
CoRR abs/0802.2833: (2008) |
| 2007 |
|---|
| 63 | EE | 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 | EE | 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 | EE | Harry Buhrman,
Lance Fortnow,
Michal Koucký,
John D. Rogers,
Nikolai K. Vereshchagin:
Inverting Onto Functions and Polynomial Hierarchy.
CSR 2007: 92-103 |
| 60 | EE | Harry Buhrman,
Nikolai K. Vereshchagin,
Ronald de Wolf:
On Computation and Communication with Small Bias.
IEEE Conference on Computational Complexity 2007: 24-32 |
| 59 | EE | 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 | EE | Nikolai K. Vereshchagin:
Kolmogorov complexity of enumerating finite sets.
Inf. Process. Lett. 103(1): 34-39 (2007) |
| 57 | EE | 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 | EE | 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 | EE | Andrei A. Muchnik,
Nikolai K. Vereshchagin:
Shannon Entropy vs. Kolmogorov Complexity.
CSR 2006: 281-291 |
| 54 | EE | Lance Fortnow,
Troy Lee,
Nikolai K. Vereshchagin:
Kolmogorov Complexity with Error.
STACS 2006: 137-148 |
| 53 | EE | Andrej Muchnik,
Alexander Shen,
Nikolai K. Vereshchagin,
Michael V. Vyugin:
Non-reducible Descriptions for Conditional Kolmogorov Complexity.
TAMC 2006: 308-317 |
| 52 | EE | 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 | EE | Harry Buhrman,
Lance Fortnow,
Ilan Newman,
Nikolai K. Vereshchagin:
Increasing Kolmogorov Complexity.
STACS 2005: 412-421 |
| 50 | EE | 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 | EE | Bruno Durand,
Andrei A. Muchnik,
Maxim Ushakov,
Nikolai K. Vereshchagin:
Ecological Turing Machines.
ICALP 2004: 457-468 |
| 48 | EE | Harry Buhrman,
Hartmut Klauck,
Nikolai K. Vereshchagin,
Paul M. B. Vitányi:
Individual Communication Complexity: Extended Abstract.
STACS 2004: 19-30 |
| 47 | EE | Nikolai K. Vereshchagin,
Paul M. B. Vitányi:
A Theory of Lossy Compression for Individual Data
CoRR cs.IT/0411014: (2004) |
| 46 | EE | Nikolai K. Vereshchagin:
Kolmogorov complexity of enumerating finite sets
Electronic Colloquium on Computational Complexity (ECCC)(030): (2004) |
| 45 | EE | 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 | EE | Lance Fortnow,
Troy Lee,
Nikolai K. Vereshchagin:
Kolmogorov Complexity with Error
Electronic Colloquium on Computational Complexity (ECCC)(080): (2004) |
| 43 | EE | Harry Buhrman,
Lance Fortnow,
Ilan Newman,
Nikolai K. Vereshchagin:
Increasing Kolmogorov Complexity
Electronic Colloquium on Computational Complexity (ECCC)(081): (2004) |
| 42 | EE | 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 | EE | Bruno Durand,
Nikolai K. Vereshchagin:
Kolmogorov-Loveland stochasticity for finite strings.
Inf. Process. Lett. 91(6): 263-269 (2004) |
| 2003 |
|---|
| 40 | EE | Harry Buhrman,
Hartmut Klauck,
Nikolai K. Vereshchagin,
Paul M. B. Vitányi:
Individual Communication Complexity
CoRR cs.CC/0304012: (2003) |
| 39 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | Andrei E. Romashchenko,
Alexander Shen,
Nikolai K. Vereshchagin:
Combinatorial interpretation of Kolmogorov complexity.
Theor. Comput. Sci. 271(1-2): 111-123 (2002) |
| 33 | EE | Alexander Shen,
Nikolai K. Vereshchagin:
Logical operations and Kolmogorov complexity.
Theor. Comput. Sci. 271(1-2): 125-129 (2002) |
| 32 | EE | 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 | EE | Bruno Durand,
Alexander Shen,
Nikolai K. Vereshchagin:
Descriptive complexity of computable sequences.
Theor. Comput. Sci. 271(1-2): 47-58 (2002) |
| 30 | EE | Nikolai K. Vereshchagin:
Kolmogorov complexity conditional to large integers.
Theor. Comput. Sci. 271(1-2): 59-67 (2002) |
| 29 | EE | 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 | EE | Andrei A. Muchnik,
Nikolai K. Vereshchagin:
Logical Operations and Kolmogorov Complexity II.
IEEE Conference on Computational Complexity 2001: 256-265 |
| 27 | EE | Nikolai K. Vereshchagin:
An enumerable undecidable set with low prefix complexity: a simplified proof
Electronic Colloquium on Computational Complexity (ECCC)(083): (2001) |
| 26 | EE | Nikolai K. Vereshchagin:
Kolmogorov Complexity Conditional to Large Integers
Electronic Colloquium on Computational Complexity (ECCC)(086): (2001) |
| 25 | EE | Bruno Durand,
Alexander Shen,
Nikolai K. Vereshchagin:
Descriptive complexity of computable sequences
Electronic Colloquium on Computational Complexity (ECCC)(087): (2001) |
| 24 | EE | Alexander Shen,
Nikolai K. Vereshchagin:
Logical operations and Kolmogorov complexity
Electronic Colloquium on Computational Complexity (ECCC)(088): (2001) |
| 23 | EE | Andrei A. Muchnik,
Nikolai K. Vereshchagin:
Logical operations and Kolmogorov complexity. II
Electronic Colloquium on Computational Complexity (ECCC)(089): (2001) |
| 2000 |
|---|
| 22 | EE | Andrei E. Romashchenko,
Alexander Shen,
Nikolai K. Vereshchagin:
Combinatorial Interpretation of Kolmogorov Complexity.
IEEE Conference on Computational Complexity 2000: 131-137 |
| 21 | EE | Nikolai K. Vereshchagin,
Michael V. Vyugin:
Independent Minimum Length Programs to Translate between Given Strings.
IEEE Conference on Computational Complexity 2000: 138- |
| 20 | EE | Andrei E. Romashchenko,
Alexander Shen,
Nikolai K. Vereshchagin:
Combinatorial Interpretation of Kolmogorov Complexity
Electronic Colloquium on Computational Complexity (ECCC) 7(26): (2000) |
| 19 | EE | 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 | EE | 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 | EE | Bruno Durand,
Alexander Shen,
Nikolai K. Vereshchagin:
Descriptive Complexity of Computable Sequences.
STACS 1999: 153-162 |
| 15 | EE | 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 | EE | Sylvain Porrot,
Max Dauchet,
Bruno Durand,
Nikolai K. Vereshchagin:
Deterministic Rational Transducers and Random Sequences.
FoSSaCS 1998: 258-272 |
| 12 | EE | 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 | EE | Nikolai K. Vereshchagin:
Randomized Boolean Decision Trees: Several Remarks.
Theor. Comput. Sci. 207(2): 329-342 (1998) |
| 1997 |
|---|
| 10 | EE | 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 | EE | 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 | EE | 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 | EE | 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 |
