The SCEAS System
Navigation Menu

Search the dblp DataBase

Title:
Author:

Nikolai K. Vereshchagin: [Publications] [Author Rank by year] [Co-authors] [Prefers] [Cites] [Cited by]

Publications of Author

  1. Daniel Hammer, Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
    Inequalities for Shannon entropies and Kolmogorov complexities. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 1997, pp:13-23 [Conf]
  2. 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". [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 1999, pp:114-0 [Conf]
  3. Andrei A. Muchnik, Nikolai K. Vereshchagin
    Logical Operations and Kolmogorov Complexity II. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 2001, pp:256-265 [Conf]
  4. Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin
    Arthur-Merlin Games in Boolean Decision Trees. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 1998, pp:58-67 [Conf]
  5. Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
    Combinatorial Interpretation of Kolmogorov Complexity. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 2000, pp:131-137 [Conf]
  6. Nikolai K. Vereshchagin
    On The Power of PP. [Citation Graph (0, 0)][DBLP]
    Structure in Complexity Theory Conference, 1992, pp:138-143 [Conf]
  7. Nikolai K. Vereshchagin
    Relationships between NP-sets, Co-NP-sets, and P-sets relative to random oracles. [Citation Graph (0, 0)][DBLP]
    Structure in Complexity Theory Conference, 1993, pp:132-138 [Conf]
  8. Nikolai K. Vereshchagin, Michael V. Vyugin
    Independent Minimum Length Programs to Translate between Given Strings. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 2000, pp:138-0 [Conf]
  9. Olga Mitina, Nikolai K. Vereshchagin
    How to Use Expert Advice in the Case when Actual Values of Estimated Events Remain Unknown. [Citation Graph (0, 0)][DBLP]
    COLT, 1995, pp:91-97 [Conf]
  10. 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. [Citation Graph (0, 0)][DBLP]
    CSL, 2002, pp:74-88 [Conf]
  11. Andrei A. Muchnik, Nikolai K. Vereshchagin
    Shannon Entropy vs. Kolmogorov Complexity. [Citation Graph (0, 0)][DBLP]
    CSR, 2006, pp:281-291 [Conf]
  12. Nikolai K. Vereshchagin, Paul M. B. Vitányi
    Kolmogorov's Structure Functions with an Application to the Foundations of Model Selection. [Citation Graph (0, 0)][DBLP]
    FOCS, 2002, pp:751-760 [Conf]
  13. Sylvain Porrot, Max Dauchet, Bruno Durand, Nikolai K. Vereshchagin
    Deterministic Rational Transducers and Random Sequences. [Citation Graph (0, 0)][DBLP]
    FoSSaCS, 1998, pp:258-272 [Conf]
  14. Bruno Durand, Andrei A. Muchnik, Maxim Ushakov, Nikolai K. Vereshchagin
    Ecological Turing Machines. [Citation Graph (0, 0)][DBLP]
    ICALP, 2004, pp:457-468 [Conf]
  15. Nikolai K. Vereshchagin
    Lower Bounds for Perceptrons Solving some Separation Problems and Oracle Separation of AM from PP. [Citation Graph (0, 0)][DBLP]
    ISTCS, 1995, pp:46-51 [Conf]
  16. Nikolai K. Vereshchagin
    NP-sets are Co-NP-immune Relative to a Random Oracle. [Citation Graph (0, 0)][DBLP]
    ISTCS, 1995, pp:40-45 [Conf]
  17. Lane A. Hemachandra, Sanjay Jain, Nikolai K. Vereshchagin
    Banishing Robust Turing Completeness. [Citation Graph (0, 0)][DBLP]
    LFCS, 1992, pp:186-197 [Conf]
  18. Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin
    Increasing Kolmogorov Complexity. [Citation Graph (0, 0)][DBLP]
    STACS, 2005, pp:412-421 [Conf]
  19. Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi
    Individual Communication Complexity: Extended Abstract. [Citation Graph (0, 0)][DBLP]
    STACS, 2004, pp:19-30 [Conf]
  20. Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin
    Descriptive Complexity of Computable Sequences. [Citation Graph (0, 0)][DBLP]
    STACS, 1999, pp:153-162 [Conf]
  21. Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin
    Kolmogorov Complexity with Error. [Citation Graph (0, 0)][DBLP]
    STACS, 2006, pp:137-148 [Conf]
  22. Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin, Michael V. Vyugin
    Non-reducible Descriptions for Conditional Kolmogorov Complexity. [Citation Graph (0, 0)][DBLP]
    TAMC, 2006, pp:308-317 [Conf]
  23. Nikolai K. Vereshchagin, Paul M. B. Vitányi
    Kolmogorov's Structure Functions with an Application to the Foundations of Model Selection [Citation Graph (0, 0)][DBLP]
    CoRR, 2002, v:0, n:, pp:- [Journal]
  24. Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi
    Individual Communication Complexity [Citation Graph (0, 0)][DBLP]
    CoRR, 2003, v:0, n:, pp:- [Journal]
  25. Nikolai K. Vereshchagin, Paul M. B. Vitányi
    A Theory of Lossy Compression for Individual Data [Citation Graph (0, 0)][DBLP]
    CoRR, 2004, v:0, n:, pp:- [Journal]
  26. Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
    Combinatorial Interpretation of Kolmogorov Complexity [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2000, v:7, n:26, pp:- [Journal]
  27. Nikolai K. Vereshchagin, Michael V. Vyugin
    Independent minimum length programs to translate between given strings [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2000, v:7, n:35, pp:- [Journal]
  28. Nikolai K. Vereshchagin
    An enumerable undecidable set with low prefix complexity: a simplified proof [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2001, v:, n:083, pp:- [Journal]
  29. Nikolai K. Vereshchagin
    Kolmogorov Complexity Conditional to Large Integers [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2001, v:, n:086, pp:- [Journal]
  30. Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin
    Descriptive complexity of computable sequences [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2001, v:, n:087, pp:- [Journal]
  31. Alexander Shen, Nikolai K. Vereshchagin
    Logical operations and Kolmogorov complexity [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2001, v:, n:088, pp:- [Journal]
  32. Andrei A. Muchnik, Nikolai K. Vereshchagin
    Logical operations and Kolmogorov complexity. II [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2001, v:, n:089, pp:- [Journal]
  33. Nikolai K. Vereshchagin
    Kolmogorov complexity of enumerating finite sets [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2004, v:, n:030, pp:- [Journal]
  34. Andrei A. Muchnik, Alexander Shen, Nikolai K. Vereshchagin, Michael V. Vyugin
    Non-reducible descriptions for conditional Kolmogorov complexity [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2004, v:, n:054, pp:- [Journal]
  35. Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin
    Kolmogorov Complexity with Error [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2004, v:, n:080, pp:- [Journal]
  36. Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin
    Increasing Kolmogorov Complexity [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2004, v:, n:081, pp:- [Journal]
  37. Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai K. Vereshchagin
    Partitioning multi-dimensional sets in a small number of ``uniform'' parts [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2005, v:, n:095, pp:- [Journal]
  38. Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin
    Arthur-Merlin Games in Boolean Decision Trees [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1997, v:4, n:54, pp:- [Journal]
  39. Alexander A. Razborov, Nikolai K. Vereshchagin
    One Property of Cross-Intersecting Families [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1999, v:6, n:14, pp:- [Journal]
  40. Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai K. Vereshchagin
    Partitioning multi-dimensional sets in a small number of "uniform" parts. [Citation Graph (0, 0)][DBLP]
    Eur. J. Comb., 2007, v:28, n:1, pp:134-144 [Journal]
  41. Olga Mitina, Nikolai K. Vereshchagin
    How to use several noisy channels with unknown error probabilities. [Citation Graph (0, 0)][DBLP]
    Inf. Comput., 2003, v:184, n:2, pp:229-241 [Journal]
  42. Lane A. Hemaspaandra, Sanjay Jain, Nikolai K. Vereshchagin
    Banishing Robust Turing Completeness. [Citation Graph (0, 0)][DBLP]
    Int. J. Found. Comput. Sci., 1993, v:4, n:3, pp:245-265 [Journal]
  43. Bruno Durand, Nikolai K. Vereshchagin
    Kolmogorov-Loveland stochasticity for finite strings. [Citation Graph (0, 0)][DBLP]
    Inf. Process. Lett., 2004, v:91, n:6, pp:263-269 [Journal]
  44. Nikolai K. Vereshchagin
    Kolmogorov complexity of enumerating finite sets. [Citation Graph (0, 0)][DBLP]
    Inf. Process. Lett., 2007, v:103, n:1, pp:34-39 [Journal]
  45. Daniel Hammer, Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
    Inequalities for Shannon Entropy and Kolmogorov Complexity. [Citation Graph (0, 0)][DBLP]
    J. Comput. Syst. Sci., 2000, v:60, n:2, pp:442-464 [Journal]
  46. Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin
    Arthur-Merlin Games in Boolean Decision Trees. [Citation Graph (0, 0)][DBLP]
    J. Comput. Syst. Sci., 1999, v:59, n:2, pp:346-372 [Journal]
  47. 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". [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 2002, v:271, n:1-2, pp:69-95 [Journal]
  48. Bruno Durand, Vladimir Kanovei, Vladimir A. Uspensky, Nikolai K. Vereshchagin
    Do stronger definitions of randomness exist? [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 2003, v:290, n:3, pp:1987-1996 [Journal]
  49. Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin
    Descriptive complexity of computable sequences. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 2002, v:271, n:1-2, pp:47-58 [Journal]
  50. Andrei A. Muchnik, Nikolai K. Vereshchagin
    A General Method to Construct Oracles Realizing Given Relationships Between Complexity Classes. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 1996, v:157, n:2, pp:227-258 [Journal]
  51. Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
    Combinatorial interpretation of Kolmogorov complexity. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 2002, v:271, n:1-2, pp:111-123 [Journal]
  52. Alexander Shen, Nikolai K. Vereshchagin
    Logical operations and Kolmogorov complexity. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 2002, v:271, n:1-2, pp:125-129 [Journal]
  53. Nikolai K. Vereshchagin
    Kolmogorov complexity conditional to large integers. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 2002, v:271, n:1-2, pp:59-67 [Journal]
  54. Nikolai K. Vereshchagin
    Randomized Boolean Decision Trees: Several Remarks. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 1998, v:207, n:2, pp:329-342 [Journal]
  55. Nikolai K. Vereshchagin, Michael V. Vyugin
    Independent minimum length programs to translate between given strings. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 2002, v:271, n:1-2, pp:131-143 [Journal]
  56. Nikolai K. Vereshchagin, Paul M. B. Vitányi
    Kolmogorov's structure functions and model selection. [Citation Graph (0, 0)][DBLP]
    IEEE Transactions on Information Theory, 2004, v:50, n:12, pp:3265-3290 [Journal]
  57. Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir, Nikolai K. Vereshchagin
    High Entropy Random Selection Protocols. [Citation Graph (0, 0)][DBLP]
    APPROX-RANDOM, 2007, pp:366-379 [Conf]
  58. Harry Buhrman, Nikolai K. Vereshchagin, Ronald de Wolf
    On Computation and Communication with Small Bias. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 2007, pp:24-32 [Conf]
  59. Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin
    Inverting Onto Functions and Polynomial Hierarchy. [Citation Graph (0, 0)][DBLP]
    CSR, 2007, pp:92-103 [Conf]
  60. Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi
    Individual communication complexity. [Citation Graph (0, 0)][DBLP]
    J. Comput. Syst. Sci., 2007, v:73, n:6, pp:973-985 [Journal]
  61. Andrej Muchnik, Alexander Shen, Mikhail Ustinov, Nikolai K. Vereshchagin, Michael V. Vyugin
    Non-reducible descriptions for conditional Kolmogorov complexity. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 2007, v:384, n:1, pp:77-86 [Journal]

  62. On-Line Probability, Complexity and Randomness. [Citation Graph (, )][DBLP]


  63. Randomised Individual Communication Complexity. [Citation Graph (, )][DBLP]


  64. High Entropy Random Selection Protocols. [Citation Graph (, )][DBLP]


  65. On Game Semantics of the Affine and Intuitionistic Logics. [Citation Graph (, )][DBLP]


  66. Limit complexities revisited [Citation Graph (, )][DBLP]


  67. Game interpretation of Kolmogorov complexity [Citation Graph (, )][DBLP]


  68. Inverting onto functions might not be hard. [Citation Graph (, )][DBLP]


Search in 0.005secs, Finished in 0.009secs
NOTICE1
System may not be available sometimes or not working properly, since it is still in development with continuous upgrades
NOTICE2
The rankings that are presented on this page should NOT be considered as formal since the citation info is incomplete in DBLP
 
System created by asidirop@csd.auth.gr [http://users.auth.gr/~asidirop/] © 2002
for Data Engineering Laboratory, Department of Informatics, Aristotle University © 2002