Research areas: Computational complexity, Kolmogorov complexity, decidable theories

Research papers

• Glenn Shafer, Alexander Shen, Nikolai Vereshchagin, Vladimir Vovk. "Test martingales, Bayes factors, and p-values".Statistical Science 26:1 (2011) 84-101.
• A. Philip Dawid, Steven de Rooij, Glenn Shaffer, Alexander Shen, Nikolay Vereshchagin, Vladimir Vovk. "Insuring against lost of evidence in game-theoretic probability". PDF. Statistics and Probability Letters, 81:1 (2011), 157-162.
• Andrej Muchnik, Ilya Mezhirov, Alexander Shen, Nikolai K. Vereshchagin. "Game interpretation of Kolmogorov complexity". CoRR abs/1003.4712: (2010)
• N.K. Vereshchagin. P.M.B. Vitanyi, " Rate Distortion and Denoising of Individual Data Using Kolmogorov Complexity". IEEE Transactions on Information Theory, vol. 56, N 7, 2010, pages 3438--3454.
• Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolay Vereshchagin. " Limit complexities revisited. " Theory of Computing Systems, 2010, v.47,no.3, p.720-736. Preliminary version: 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008), pages 73--84
• Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolay Vereshchagin. "Sparse Selfreducible Sets and Nonuniform Lower Bounds". ECCC Report TR10-163.
• Harry Buhrman, Lance Fortnow, Michal Koucky, John D. Rogers, Nikolai K. Vereshchagin, Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible? Theory Comput. Syst. 46(1): 143-156 (2010). Conference version appeared under the title " Inverting onto functions might not be hard." in: Computer Science - Theory and Applications, Second International Symposium on Computer Science in Russia, CSR 2007, Ekaterinburg, Russia, September 3-7, 2007, Proceedings. Lecture Notes in Computer Science 4649 Springer 2007, ISBN 978-3-540-74509-9. Pages 92-103
• Ilya Mezhirov, Nikolay Vereshchagin, On abstract resource semantics and computabilty logic. PDF. Journal of Computer and System Sciences, Volume 76, Issue 5, August 2010, Pages 356-372 http://dx.doi.org/10.1016/j.jcss.2009.10.008 Conference version: " On game semantics of the affine and intuitionistic logics (Extended abstract)". Proceedings of Workshop on Language, Logic, Information and Computation (WoLLIC 2008), Edinburgh, 1--4 July 2008. Pages 28-42.
• Nikolay Vereshchagin. "Encoding Invariance in Average Case Complexity". PDF. This is the full version of the paper "An Encoding Invariant Version of Polynomial Time Computable Distributions'' appeared in Proceedings of the 5th International Computer Science Symposium in Russia, CSR 2010, Kazan, Russia, June 16-20, 2010. Lecture Notes in Computer Science v. 6072, p. 371--383.
• Nikolay Vereshchagin, "Kolmogorov Complexity and Model Selection". PDF. Computer Science - Theory and Applications, Fourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18-23, 2009. Proceedings. LNCS 5675, pages 19-24
• Nikolay Vereshchagin, "Algorithmic Minimal Sufficient Statistics: a New Definition". PDF. Submitted to TOCS. A preliminary version, under the title "Algorithmic Minimal Sufficient Statistic Revisited" appeared in: Mathematical Theory and Computational Practice, 5th Conference on Computability in Europe, CiE 2009, Heidelberg, Germany, July 19-24, 2009. Proceedings. LNCS 5635. DOI: 10.1007/978-3-642-03073-4_49
• Harry Buhrman, Michal Koucky, Nikolai K. Vereshchagin. "Randomised Individual Communication Complexity". IEEE Conference on Computational Complexity 2008: 321-331 PDF.
• Alexey Chernov, Alexander Shen, Nikolai Vereshchagin, and Vladimir Vovk. " On-line Probability, Complexity and Randomness". Proc. 19th International Conference on Algorithmic Learning Theory (ALT 2008). Pages 138-153.
• H. Buhrman, N. Vereshchagin, and R. de Wolf. " On Computation and Communication with Small Bias.". In 22nd IEEE Annual Conference on Computational Complexity (CCC'07), June 12th to June 16th, 2007, San Diego, California, pp.24-32.
• H. Buhrman, M. Cristandl, M. Koucky, Z. Lotker, B. Patt-Shamir, N. Vereshchagin. " High Entropy Random Selection Protocols. " Proceedings of 10th International Workshop, APPROX 2007, and 11th International Workshop, RANDOM 2007, Princeton, NJ, USA, August 20-22, 2007. Proceedings. Lecture Notes in Computer Science, volume 4627/2007 pages 366-379
• L. Fortnow, T. Lee, N. Vereshchagin, "Kolmogorov Complexity with Error". Proc. Symposium Theoretical Aspects of Comput. Science 2006, Lecture Notes in Computer Science, vol. 3884 (2006) 137--148
• Andrej Muchnik, Alexander Shen, Mikhail Ustinov, Nikolai Vereshchagin, Michael Vyugin. " Non-reducible descriptions for conditional Kolmogorov complexity". Theory and Applications of Models of Computation, Third International Conference, TAMC 2006, Beijing, China, May 15-20, 2006, Proceedings. Lecture Notes in Computer Science 3959 Springer 2006, pages 308--317.
• An. Muchnik and N. Vereshchagin. "Shannon Entropy vs. Kolmogorov Complexity''. Computer Science --- Theory and Applications: First International Computer Science Symposium in Russia, CSR 2006, St. Petersburg, Russia, June 8-12. 2006. Proceedings. Editors: Dima Grigoriev, John Harrison, Edward A. Hirsch Lecture Notes in Computer Science, vol. 3967 / 2006, pages 281--291.
• Ilja Mezhirov, Nikolay Vereshchagin. "A game interpretation of Affine Logic and Intutionistic Propositional Calculus (in Russian)".
• Noga Alon, Ilan Newman, Alexander Shen, Gabor Tardos, Nikolai Vereshchagin. Partitioning multi-dimensional sets in a small number of ``uniform'' parts. European Journal of Combinatorics 28 (2007) 134-144. Available online via ScienceDirect.
• Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai Vereshchagin. Increasing Kolmogorov Complexity. In Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science, number 3404 in Lecture Notes in Computer Science, pages 412-421. Springer, Berlin, 2005.
• Paul Vitanyi, Nikolai Vereshchagin. " On Algorithmic Rate-Distortion Function". Proc. of 2006 IEEE International Symposium on Information Theory Sunday, July 9 -Friday, July 14, 2006 Seattle, Washington.
• H. Buhrman, H. Klauck, N. Vereshchagin, P. Vitanyi." Individual Communication Complexity". J. Comput. Syst. Sci. (JCSS) 73(6):973-985 (2007). Preliminary version in: 21st Annual Symposium on Theoretical Aspects of Computer Science, STACS 2004, Montpelier, France, March 25-27, 2004, Proceedings. Series : Lecture Notes in Computer Science , Vol. 2996, pages 19-30.
• N. Vereshchagin "Kolmogorov complexity of enumerating finite sets" Information Processing Letters 103 (2007) 34-39.
• N. Vereshchagin and P. Vitanyi."Kolmogorov's Structure Functions with an Application to the Foundations of Model Selection" . IEEE Transactions on Information Theory 50:12 (2004) 3265-3290. Preliminary version: Proc. 47th IEEE Symp. Found. Comput. Sci., 2002, 751--760.

• A.V. Chernov, D.P. Skvortsov, E.Z. Skvortsova, N.K. Vereshchagin. "Variants of Realizability for Propositional Formulas and the Logic of the Weak Law of Excluded Middle". Proceedings of Computer Science Logic'02, Lecture Notes in Computer Science, 2002, v.~2471, pp.~74--88. Н.К. Верещагин, Д.П. Скворцов, Е.З. Скворцова, А.В. Чернов. " Варианты понятия реализуемости для пропозициональных формул, приводящие к логике слабого закона исключенного третьего " Математическая логика и алгебра, Труды Математического института им. В.А. Стеклова, 2003, т. 242, стр 77--97. (English translation - N.K. Vereshchagin, D.P. Skvortsov, E.Z. Skvortsova, A.V. Chernov. Variants of Realizability for Propositional Formulas and the Logic of the Weak Law of Excluded Middle. Proceedings of Steklov Institute of Mathematics 242 (2003) 67-85)

• K. Makarychev, Yu. Makarychev, A. Romashchenko, N. Vereshchagin. "A New class of non Shannon type inequalities for entropies " Communications in Information and Systems, 2:2 (2002) 147-166.

• B.Durand, N.K. Vereshchagin, M.A. Ushakov. ""Ecological" Computations". 31st International Colloquium on Automata, Languages and Programming, ICALP 2004, Turku, Finland, July 12-16, 2004, Proceedings Series : Lecture Notes in Computer Science , Vol. 3142 Diaz, J.; Karhumaki, J.; Lepista, A.; Sannella, D. (Eds.) pages 457-468. B. Durand, Н.К. Верещагин, М.А. Ушаков. ""Экологические" вычисления".

• B. Durand, N. Vereshchagin. "Kolmogorov-Loveland stochasticity for finite strings". Information Processing Letters, 91 (2004) 263-269.

• N.K. Vereshchagin. "A new proof Ahlswede-Gacs-Koerner theorem on common information".

• B. Durand, V. Kanovei, V. Uspensky, N. Vereshchagin. "Do stronger definitions of randomness exist?" Theoretical Computer Science 290:3 (2003) 1987-1996.

• N. Vereshchagin. "An enumerable undecidable set with low prefix complexity: a simplified proof ".

• A. Shen and N. Vereshchagin. "Logical operations and Kolmogorov complexity". Theoretical Computer Science 271 (2002) 125--129.

• A. Muchnik and N. Vereshchagin. "Logical operations and Kolmogorov complexity. II". Proc. of 16th Annual IEEE Conference on Computational Complexity, Chicago, June 2001, pp. 256--265.

• N. Vereshchagin. "Kolmogorov Complexity Conditional to Large Integers". Theoretical Computer Science 271 (2002) 59--67.

• N. Vereshchagin and M. Vyugin. Independent minimum length programs to translate between given strings. Theoretical Computer Science 271 (2002) 131--143. Preliminary version in: Proc. of 15th Annual IEEE Conference on Computational Complexity, July 2000, 138--144. ECCC TR00-035. See also a related paper by M. Vyugin On strong definition of information distance.

• A. Romashchenko, A. Shen, and N. Vereshchagin "Combinatorial interpretation of Kolmogorov complexity", Theoretical Computer Science 271 (2002) 111--123. Preliminary version in: Proc. of 15th Annual IEEE Conference on Computational Complexity, July 2000, 131--137.

• B. Durand, A. Shen, and N. Vereshchagin. Descriptive Complexity of Computable Sequences. Theoretical Computer Science 171 (2001), p. 47--58; Proc. of 16th Ann. Symp. on Theoretical Aspects of Computer Science, Trier, Germany, March 1999, LNCS 1563, pp. 153--162.

• Верещагин Н.К., Любецкий В.А. Алгоритм определения вторичной структуры РНК. В сб.: Труды научно-исследовательского семинара логического центра ИФ РАН. М.: Изд-во РАН, 2000, вып. 14, стр. 99-109.
• A. Razborov and N. Vereshchagin. "One Property of Cross-Intersecting Families", Proc. of Erdosh memorial Conference, Hungary 1999. ECCC, TR99-014

• A. Chernov, An. Muchnik, A. Romashchenko, A. Shen, and N. Vereshchagin. Upper semi-lattice of binary strings with the relation ``x is simple conditional to y''. Theoretical Computer Science 271 (2002) 69--95.

• R. Raz, G. Tardos, O. Verbitsky, and N. Vereshchagin. Arthur-Merlin Games in Boolean Decision Trees. Journal of Computer Systems Sciences 59 (1999) 346-372, ECCC, TR97-054

• B. Durand, M. Dauchet, S. Porrot, and N. Vereshchagin. ``Deterministic rational transducers and random sequences''. Proc. of Symp. Fondations of Software Systems and Computation Structures (FOSSACS), Lisbon, March-April 1998, LNCS 1378, pp. 258--272.

• N. Vereshchagin. ``Randomized boolean decision trees: Several remarks.'' Theoretical Computer Sciences 207 (1998) 329-342.

• D. Hammer, A. Romashchenko, A. Shen, and N. Vereshchagin. Inequalities for Shannon entropy and Kolmogorov complexity. Journal of Computer and Systems Sciences 60 (2000) 442-464. Preliminary version appeared in Proc. Twelfth Annual IEEE Conference on Computational Complexity, Ulm, Germany June 1997, 13-23.

• An. Muchnik and N. Vereshchagin. A General Method to Construct Oracles Realizing Given Relationships between Complexity Classes. Theoretical computer science 157 (1996) 227-258. Extended version: TR-500, University of Rochester.

• N.K. Vereshchagin. Lower Bounds for Perceptrons Solving some Separation Problems and Oracle Separation of AM from PP. Proc. Third Israel Symposium on Theory of Computing and Systems, Tel-Aviv, Jan. 1995, 46--51.

• N. Vereshchagin. NP-sets are Co-NP-immune Relative to a Random Oracle. Third Israel Symposium on Theory of Computing and Systems, Tel-Aviv, Jan. 1995, 40--45.

• O. Mitina and N. Vereshchagin. "How to Use Several Noisy Channels with Unknown Error Probabilities" Information and Computation 182 (2003) 229-241. Preliminary version appeared under the title "How to use expert advice in the case when actual values of estimated events remain unknown." Proc. Eighth Annual Conference on Computational Learning Theory (July 5th--8th), 1995, Santa Cruz, California, 91--97.

• Н. Верещагин. "Оракульное отделение некоторых сложностных классов и нижние оценки сложности персептронов, решающих некоторые проблемы отделения". Известия РАН. Серия математическая. 59 (1995), N 6, с. 3--31. English translation: N. Vereshchagin. ``Oracle Separation of Complexity Classes and Lower Bounds for Perceptrons Solving Separation Problems''. Izvestiya: Mathematics 59 (1995), No. 6, 1103--1122.

• Н.К. Верещагин. "Релятивизуемые и нерелятивизуемые теоремы полиномиальной теории алгоритмов". Известия РАН, Сер. матем. 57 (1993), No. 2, 51-90. English transaltion: N. Vereshchagin. "Relativizable and Non-Relativizable Theorems in Polynomial Theory of Algorithms". Russian Acad. Sci. Izv. Math., 42 (1994), No. 2, 261--298.

• N. Vereshchagin. "Relationships between NP-sets, coNP-sets and P-sets relative to random oracles". Proc. 8th Conference on Structure in Complexity Theory, 1993, 132--138.

• N. Vereshchagin. "Relationships between NP-sets, coNP-sets and P-sets relative to random oracles". Izvestija Vysshyh Uchebnykh Zavedenij. Seria Matematika, 1993, No. 3, pp. 31--39. (Russian)

• Lane A. Hemaspaandra, Sanjay Jain, Nikolai K. Vereshchagin. "Banishing Robust Turing Completeness". Intern. J. on Found. of Comp. Science, 1993, v. 3--4, pp. 245--265. Conference version appeared in: Logical Foundations of Computer Science. 1992. Proceedings. (Lecture notes in Computer Science, 620, 186--197)

• N. Vereshchagin. On the Power of PP. Proc. 7th Annual IEEE Conference on Structure in Complexity Theory, Boston, MA, 1992, 138--143.

• Н.К. Верещагин. "Новое доказательство разрешимости элементарной теории линейно упорядоченных множеств" Математические заметки, 47 (1990), No. 5, 21--38. English translation: N. Vereshchagin. "A New Proof of the Decidability of the Elementary Theory of the Linearly Ordered Sets". Mathematical Notes, 47 (1990), 444--449.

• Н.К. Верещагин. "О проблеме появления нуля в линейной рекуррентной последовательности". Математические заметки 38 (1985), No. 2, 177--189. English translation: N. Vereshchagin. "The problem of appearance of a zero in a linear recurrence sequence", Mathematical Notes, 38 (1985), Nos. 1--2, 609--615.

• Н.К. Верещагин. "Эффективные верхние оценки числа нулей линейной рекуррентной последовательности". Вестник МГУ, 1986, No 1, 25--30. N. Vereshchagin. "The effective upper bounds for the number of zeros in linear recurrence sequences". Vestnik MGU, 1986, No. 1, 25--30 (Russian)

• Н.К. Верещагин. "О нулях линейных рекуррентных последовательностей". Доклады АН СССР 278 (1984), No.5, 1036--1039. English translation: N. Vereshchagin. ``On the zeros of linear recurrence sequences," Soviet Math. Dokl., 30 (1984), No. 2, 502--505.

• Н.К. Верещагин. "Об одной алгоритмической проблеме для линейных рекруррентных последовательностей". Тезисы Шестой Всесоюзной конференции по математической логике. Тбилиси, 1982, стр. 32. N. Vereshchagin. "On an algorithmic problem concerning linear recursive sequences". In.: 6th All-Union Conference on Mathematical Logic, Tbilisi, Georgia 1982, p.32 (Russian)

• Н.К. Верещагин. "Игры по угадыванию битов конечных последовательностей". Тезисы Девятой Всесоюзной конференции по математической логике. Ленинград, 1988, стр. 28. N. Vereshchagin. "Bit guessing in a finite sequence". Abstracts of 9th All-Union Conference on Mathematical Logic, Leningrad, Russia 1988, p.28. (Russian)

• Н.К. Верещагин. "Алгоритмы над алгебраическими числами". Тезисы 17-ой Всесоюзной алгебраической конференции. Кишинев, 1985, стр. 89. N. Vereshchagin. "Algorithms dealing with algebraic numbers". Abstracts of 17th All-Union Algebraic Conference, Kishinev, Moldova 1985, p. 89. (Russian)