Nikolay K. Vereshchagin

34 papers A 3C 2Misc 6Journal 21Unranked 2
YearRankTypeTitle / Venue / Authors
2024 J jnl
Half-duplex communication complexity with adversary can be less than the classical communication complexity.
CoRR
Mikhail Dektiarev, Nikolay K. Vereshchagin
2023 J jnl
Information disclosure in the framework of Kolmogorov complexity.
Theor. Comput. Sci.
Nikolay K. Vereshchagin
2023 J jnl
On information content in certain objects.
CoRR
Nikolay K. Vereshchagin
2022 J jnl
A Family of Non-Periodic Tilings of the Plane by Right Golden Triangles.
Discret. Comput. Geom.
Nikolay K. Vereshchagin
2022 J jnl
How much randomness is needed to convert MA protocols to AM protocols?
Electron. Colloquium Comput. Complex.
Nikolay K. Vereshchagin
2021 J jnl
Information disclosure in the framework of Kolmogorov complexity.
CoRR
Nikolay K. Vereshchagin
2020 J jnl
A family of non-periodic tilings of the plane by right golden triangles.
CoRR
Nikolay K. Vereshchagin
2020 J jnl
Descriptive complexity of computable sequences revisited.
Theor. Comput. Sci.
Nikolay K. Vereshchagin
2019 J jnl
Proofs of conservation inequalities for Levin's notion of mutual information of 1974.
CoRR
Nikolay K. Vereshchagin
2017 — conf
Algorithmic Statistics: Forty Years Later.
Computability and Complexity
Nikolay K. Vereshchagin, Alexander Shen
2017 A conf
Stochasticity in Algorithmic Statistics for Polynomial Time.
CCC
Alexey Milovanov, Nikolay K. Vereshchagin
2016 J jnl
Algorithmic Minimal Sufficient Statistics: a New Approach.
Theory Comput. Syst.
Nikolay K. Vereshchagin
2015 J jnl
Conditional Information Inequalities and Combinatorial Applications.
CoRR
Tarik Kaced, Andrei Romashchenko, Nikolay K. Vereshchagin
2014 — conf
Aperiodic Tilings by Right Triangles.
DCFS
Nikolay K. Vereshchagin
2014 Misc ed.
Computer Science - Theory and Applications - 9th International Computer Science Symposium in Russia, CSR 2014, Moscow, Russia, June 7-11, 2014. Proceedings
CSR
Edward A. Hirsch, Sergei O. Kuznetsov, Jean-Éric Pin, Nikolay K. Vereshchagin
2014 J jnl
Editorial.
Theory Comput. Syst.
Nikolay K. Vereshchagin
2014 J jnl
Encoding Invariance in Average Case Complexity.
Theory Comput. Syst.
Nikolay K. Vereshchagin
2014 Misc conf
Randomized Communication Complexity of Approximating Kolmogorov Complexity.
CSR
Nikolay K. Vereshchagin
2013 Misc conf
Improving on Gutfreund, Shaltiel, and Ta-Shma's Paper "If NP Languages Are Hard on the Worst-Case, Then It Is Easy to Find Their Hard Instances".
CSR
Nikolay K. Vereshchagin
2013 C conf
On Algorithmic Strong Sufficient Statistics.
CiE
Nikolay K. Vereshchagin
2013 J jnl
Randomized communication complexity of appropximating Kolmogorov complexity.
Electron. Colloquium Comput. Complex.
Nikolay K. Vereshchagin
2013 A conf
Short Lists with Short Programs in Short Time.
CCC
Bruno Bauwens, Anton Makhlin, Nikolay K. Vereshchagin, Marius Zimand
2013 J jnl
Short lists with short programs in short time
CoRR
Bruno Bauwens, Anton Makhlin, Nikolay K. Vereshchagin, Marius Zimand
2013 J jnl
Short lists with short programs in short time.
Electron. Colloquium Comput. Complex.
Bruno Bauwens, Anton Makhlin, Nikolay K. Vereshchagin, Marius Zimand
2013 A conf
Towards a Reverse Newman's Theorem in Interactive Information Complexity.
CCC
Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman, Nikolay K. Vereshchagin
2011 Misc ed.
Computer Science - Theory and Applications - 6th International Computer Science Symposium in Russia, CSR 2011, St. Petersburg, Russia, June 14-18, 2011. Proceedings
CSR
Alexander S. Kulikov, Nikolay K. Vereshchagin
2011 J jnl
Improving on Gutfreund, Shaltiel, and Ta-Shma's paper "If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances".
Electron. Colloquium Comput. Complex.
Nikolay K. Vereshchagin
2010 J jnl
Algorithmic Minimal Sufficient Statistics: a New Definition.
Electron. Colloquium Comput. Complex.
Nikolay K. Vereshchagin
2010 Misc conf
An Encoding Invariant Version of Polynomial Time Computable Distributions.
CSR
Nikolay K. Vereshchagin
2010 J jnl
An Encoding Invariant Version of Polynomial Time Computable Distributions.
Electron. Colloquium Comput. Complex.
Nikolay K. Vereshchagin
2010 J jnl
On abstract resource semantics and computability logic.
J. Comput. Syst. Sci.
Ilya Mezhirov, Nikolay K. Vereshchagin
2009 C conf
Algorithmic Minimal Sufficient Statistic Revisited.
CiE
Nikolay K. Vereshchagin
2009 Misc conf
Kolmogorov Complexity and Model Selection.
CSR
Nikolay K. Vereshchagin
2008 J jnl
Kolmogorov Complexity and Games.
Bull. EATCS
Nikolay K. Vereshchagin