Nikolay K. Vereshchagin

Publication Activity (10 Years)

Years Active: 2008-2024
Publications (10 Years): 11

Top Topics

Delaunay Triangulation

Kolmogorov Complexity

Top Venues

Theory Comput. Syst.

Theor. Comput. Sci.

Discret. Comput. Geom.

Publications

Mikhail Dektiarev, Nikolay K. Vereshchagin
Half-duplex communication complexity with adversary can be less than the classical communication complexity. CoRR (2024)
Nikolay K. Vereshchagin
On information content in certain objects. CoRR (2023)
Nikolay K. Vereshchagin
Information disclosure in the framework of Kolmogorov complexity. Theor. Comput. Sci. 940 (Part) (2023)
Nikolay K. Vereshchagin
How much randomness is needed to convert MA protocols to AM protocols? Electron. Colloquium Comput. Complex. (2022)
Nikolay K. Vereshchagin
A Family of Non-Periodic Tilings of the Plane by Right Golden Triangles. Discret. Comput. Geom. 68 (1) (2022)
Nikolay K. Vereshchagin
Descriptive complexity of computable sequences revisited. Theor. Comput. Sci. 809 (2020)
Nikolay K. Vereshchagin
A family of non-periodic tilings of the plane by right golden triangles. CoRR (2020)
Nikolay K. Vereshchagin
Proofs of conservation inequalities for Levin's notion of mutual information of 1974. CoRR (2019)
Nikolay K. Vereshchagin, Alexander Shen
Algorithmic Statistics: Forty Years Later. Computability and Complexity (2017)
Alexey Milovanov, Nikolay K. Vereshchagin
Stochasticity in Algorithmic Statistics for Polynomial Time. Computational Complexity Conference (2017)
Nikolay K. Vereshchagin
Algorithmic Minimal Sufficient Statistics: a New Approach. Theory Comput. Syst. 58 (3) (2016)
Tarik Kaced, Andrei E. Romashchenko, Nikolay K. Vereshchagin
Conditional Information Inequalities and Combinatorial Applications. CoRR (2015)
Nikolay K. Vereshchagin
Editorial. Theory Comput. Syst. 55 (2) (2014)
Nikolay K. Vereshchagin
Randomized Communication Complexity of Approximating Kolmogorov Complexity. CSR (2014)
Nikolay K. Vereshchagin
Aperiodic Tilings by Right Triangles. DCFS (2014)
Nikolay K. Vereshchagin
Encoding Invariance in Average Case Complexity. Theory Comput. Syst. 54 (2) (2014)
Bruno Bauwens, Anton Makhlin, Nikolay K. Vereshchagin, Marius Zimand
Short lists with short programs in short time CoRR (2013)
Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman, Nikolay K. Vereshchagin
Towards a Reverse Newman's Theorem in Interactive Information Complexity. Computational Complexity Conference (2013)
Nikolay K. Vereshchagin
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 (2013)
Bruno Bauwens, Anton Makhlin, Nikolay K. Vereshchagin, Marius Zimand
Short lists with short programs in short time. Electron. Colloquium Comput. Complex. 20 (2013)
Nikolay K. Vereshchagin
Randomized communication complexity of appropximating Kolmogorov complexity. Electron. Colloquium Comput. Complex. 20 (2013)
Bruno Bauwens, Anton Makhlin, Nikolay K. Vereshchagin, Marius Zimand
Short Lists with Short Programs in Short Time. Computational Complexity Conference (2013)
Nikolay K. Vereshchagin
On Algorithmic Strong Sufficient Statistics. CiE (2013)
Nikolay K. Vereshchagin
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. 18 (2011)
Ilya Mezhirov, Nikolay K. Vereshchagin
On abstract resource semantics and computability logic. J. Comput. Syst. Sci. 76 (5) (2010)
Nikolay K. Vereshchagin
An Encoding Invariant Version of Polynomial Time Computable Distributions. CSR (2010)
Nikolay K. Vereshchagin
An Encoding Invariant Version of Polynomial Time Computable Distributions. Electron. Colloquium Comput. Complex. 17 (2010)
Nikolay K. Vereshchagin
Algorithmic Minimal Sufficient Statistics: a New Definition. Electron. Colloquium Comput. Complex. 17 (2010)
Nikolay K. Vereshchagin
Kolmogorov Complexity and Model Selection. CSR (2009)
Nikolay K. Vereshchagin
Algorithmic Minimal Sufficient Statistic Revisited. CiE (2009)
Nikolay K. Vereshchagin
Kolmogorov Complexity and Games. Bull. EATCS 94 (2008)