Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDNikolai K. Vereshchagin
Nikolay K. Vereshchagin
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2023
[j39]Nikolay K. Vereshchagin
:
Information disclosure in the framework of Kolmogorov complexity. Theor. Comput. Sci. 940(Part): 108-122 (2023)- 2022
- [j38]Nikolay K. Vereshchagin:
A Family of Non-Periodic Tilings of the Plane by Right Golden Triangles. Discret. Comput. Geom. 68(1): 188-217 (2022) - [c41]Nikolai K. Vereshchagin:
How Much Randomness is Needed to Convert MA Protocols to AM Protocols? CSR 2022: 338-349 - [i37]Nikolay K. Vereshchagin:
How much randomness is needed to convert MA protocols to AM protocols? Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [j37]Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir, Nikolai K. Vereshchagin:
High Entropy Random Selection Protocols. Algorithmica 83(2): 667-694 (2021) - [j36]Nikolai K. Vereshchagin:
Proofs of conservation inequalities for Levin's notion of mutual information of 1974. Theor. Comput. Sci. 856: 14-20 (2021) - [i36]Nikolay K. Vereshchagin:
Information disclosure in the framework of Kolmogorov complexity. CoRR abs/2108.01685 (2021) - 2020
- [j35]Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin:
On the Structure of Ammann A2 Tilings. Discret. Comput. Geom. 63(3): 577-606 (2020) - [j34]Nikolay K. Vereshchagin:
Descriptive complexity of computable sequences revisited. Theor. Comput. Sci. 809: 531-537 (2020) - [i35]Nikolay K. Vereshchagin:
A family of non-periodic tilings of the plane by right golden triangles. CoRR abs/2007.10658 (2020)
2010 – 2019
- 2019
- [j33]Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolai K. Vereshchagin:
Sparse Selfreducible Sets and Nonuniform Lower Bounds. Algorithmica 81(1): 179-200 (2019) - [i34]Nikolay K. Vereshchagin:
Proofs of conservation inequalities for Levin's notion of mutual information of 1974. CoRR abs/1911.05447 (2019) - 2018
- [j32]Bruno Bauwens, Anton Makhlin, Nikolai K. Vereshchagin, Marius Zimand:
Short lists with short programs in short time. Comput. Complex. 27(1): 31-61 (2018) - [j31]Tarik Kaced, Andrei E. Romashchenko, Nikolai K. Vereshchagin:
A Conditional Information Inequality and Its Combinatorial Applications. IEEE Trans. Inf. Theory 64(5): 3610-3615 (2018) - 2017
- [j30]Nikolai K. Vereshchagin:
Short lists with short programs from programs of functions and strings. Theory Comput. Syst. 61(4): 1440-1450 (2017) - [c40]Nikolay K. Vereshchagin, Alexander Shen:
Algorithmic Statistics: Forty Years Later. Computability and Complexity 2017: 669-737 - [c39]Alexey Milovanov, Nikolay K. Vereshchagin:
Stochasticity in Algorithmic Statistics for Polynomial Time. Computational Complexity Conference 2017: 17:1-17:18 - [i33]Alexey Milovanov, Nikolai K. Vereshchagin:
Stochasticity in Algorithmic Statistics for Polynomial Time. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j29]Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman, Nikolai K. Vereshchagin:
Towards a Reverse Newman's Theorem in Interactive Information Complexity. Algorithmica 76(3): 749-781 (2016) - [j28]Nikolay K. Vereshchagin:
Algorithmic Minimal Sufficient Statistics: a New Approach. Theory Comput. Syst. 58(3): 463-481 (2016) - [i32]Nikolai K. Vereshchagin, Alexander Shen:
Algorithmic statistics: forty years later. CoRR abs/1607.08077 (2016) - 2015
- [i31]Tarik Kaced, Andrei E. Romashchenko, Nikolay K. Vereshchagin:
Conditional Information Inequalities and Combinatorial Applications. CoRR abs/1501.04867 (2015) - [i30]Nikolai K. Vereshchagin, Alexander Shen:
Algorithmic statistics revisited. CoRR abs/1504.04950 (2015) - 2014
- [j27]Nikolay K. Vereshchagin:
Encoding Invariance in Average Case Complexity. Theory Comput. Syst. 54(2): 305-317 (2014) - [j26]Nikolay K. Vereshchagin:
Editorial. Theory Comput. Syst. 55(2): 279-280 (2014) - [c38]Nikolay K. Vereshchagin:
Randomized Communication Complexity of Approximating Kolmogorov Complexity. CSR 2014: 365-374 - [c37]Nikolay K. Vereshchagin:
Aperiodic Tilings by Right Triangles. DCFS 2014: 29-41 - [e2]Edward A. Hirsch, Sergei O. Kuznetsov, Jean-Éric Pin, Nikolay K. Vereshchagin:
Computer Science - Theory and Applications - 9th International Computer Science Symposium in Russia, CSR 2014, Moscow, Russia, June 7-11, 2014. Proceedings. Lecture Notes in Computer Science 8476, Springer 2014, ISBN 978-3-319-06685-1 [contents] - 2013
- [c36]Nikolay K. Vereshchagin:
On Algorithmic Strong Sufficient Statistics. CiE 2013: 424-433 - [c35]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: 24-33 - [c34]Bruno Bauwens, Anton Makhlin, Nikolay K. Vereshchagin, Marius Zimand:
Short Lists with Short Programs in Short Time. Computational Complexity Conference 2013: 98-108 - [c33]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: 203-211 - [i29]Bruno Bauwens, Anton Makhlin, Nikolay K. Vereshchagin, Marius Zimand:
Short lists with short programs in short time. CoRR abs/1301.1547 (2013) - [i28]Bruno Bauwens, Anton Makhlin, Nikolay K. Vereshchagin, Marius Zimand:
Short lists with short programs in short time. Electron. Colloquium Comput. Complex. TR13 (2013) - [i27]Nikolay K. Vereshchagin:
Randomized communication complexity of appropximating Kolmogorov complexity. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [i26]Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin:
Limit complexities revisited [once more]. CoRR abs/1204.0201 (2012) - 2011
- [e1]Alexander S. Kulikov, Nikolay K. Vereshchagin:
Computer Science - Theory and Applications - 6th International Computer Science Symposium in Russia, CSR 2011, St. Petersburg, Russia, June 14-18, 2011. Proceedings. Lecture Notes in Computer Science 6651, Springer 2011, ISBN 978-3-642-20711-2 [contents] - [i25]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. TR11 (2011) - 2010
- [j25]Ilya Mezhirov, Nikolay K. Vereshchagin:
On abstract resource semantics and computability logic. J. Comput. Syst. Sci. 76(5): 356-372 (2010) - [j24]Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin:
Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible? Theory Comput. Syst. 46(1): 143-156 (2010) - [j23]Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin:
Limit Complexities Revisited. Theory Comput. Syst. 47(3): 720-736 (2010) - [j22]Nikolai K. Vereshchagin, Paul M. B. Vitányi:
Rate distortion and denoising of individual data using Kolmogorov complexity. IEEE Trans. Inf. Theory 56(7): 3438-3454 (2010) - [c32]Nikolay K. Vereshchagin:
An Encoding Invariant Version of Polynomial Time Computable Distributions. CSR 2010: 371-383 - [i24]Andrej Muchnik, Ilya Mezhirov, Alexander Shen, Nikolai K. Vereshchagin:
Game interpretation of Kolmogorov complexity. CoRR abs/1003.4712 (2010) - [i23]Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolai K. Vereshchagin:
Sparse Selfreducible Sets and Nonuniform Lower Bounds. Electron. Colloquium Comput. Complex. TR10 (2010) - [i22]Nikolay K. Vereshchagin:
Algorithmic Minimal Sufficient Statistics: a New Definition. Electron. Colloquium Comput. Complex. TR10 (2010) - [i21]Nikolay K. Vereshchagin:
An Encoding Invariant Version of Polynomial Time Computable Distributions. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [c31]Nikolay K. Vereshchagin:
Algorithmic Minimal Sufficient Statistic Revisited. CiE 2009: 478-487 - [c30]Nikolay K. Vereshchagin:
Kolmogorov Complexity and Model Selection. CSR 2009: 19-24 - 2008
- [j21]Nikolay K. Vereshchagin:
Kolmogorov Complexity and Games. Bull. EATCS 94: 43-75 (2008) - [c29]Alexey V. Chernov, Alexander Shen, Nikolai K. Vereshchagin, Vladimir Vovk:
On-Line Probability, Complexity and Randomness. ALT 2008: 138-153 - [c28]Harry Buhrman, Michal Koucký, Nikolai K. Vereshchagin:
Randomised Individual Communication Complexity. Computational Complexity Conference 2008: 321-331 - [c27]Ilya Mezhirov, Nikolai K. Vereshchagin:
On Game Semantics of the Affine and Intuitionistic Logics. WoLLIC 2008: 28-42 - [i20]Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin:
Limit complexities revisited. CoRR abs/0802.2833 (2008) - 2007
- [j20]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) - [j19]Nikolai K. Vereshchagin:
Kolmogorov complexity of enumerating finite sets. Inf. Process. Lett. 103(1): 34-39 (2007) - [j18]Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi:
Individual communication complexity. J. Comput. Syst. Sci. 73(6): 973-985 (2007) - [j17]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) - [c26]Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir, Nikolai K. Vereshchagin:
High Entropy Random Selection Protocols. APPROX-RANDOM 2007: 366-379 - [c25]Harry Buhrman, Nikolai K. Vereshchagin, Ronald de Wolf:
On Computation and Communication with Small Bias. Computational Complexity Conference 2007: 24-32 - [c24]Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin:
Inverting Onto Functions and Polynomial Hierarchy. CSR 2007: 92-103 - [i19]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 - 2006
- [c23]Andrei A. Muchnik, Nikolai K. Vereshchagin:
Shannon Entropy vs. Kolmogorov Complexity. CSR 2006: 281-291 - [c22]Nikolai K. Vereshchagin, Paul M. B. Vitányi:
On Algorithmic Rate-Distortion Function. ISIT 2006: 798-802 - [c21]Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin:
Kolmogorov Complexity with Error. STACS 2006: 137-148 - [c20]Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin, Michael V. Vyugin:
Non-reducible Descriptions for Conditional Kolmogorov Complexity. TAMC 2006: 308-317 - [i18]Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin:
Inverting onto functions might not be hard. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [c19]Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin:
Increasing Kolmogorov Complexity. STACS 2005: 412-421 - [i17]Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai K. Vereshchagin:
Partitioning multi-dimensional sets in a small number of "uniform" parts. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [j16]Bruno Durand, Nikolai K. Vereshchagin:
Kolmogorov-Loveland stochasticity for finite strings. Inf. Process. Lett. 91(6): 263-269 (2004) - [j15]Nikolai K. Vereshchagin, Paul M. B. Vitányi:
Kolmogorov's structure functions and model selection. IEEE Trans. Inf. Theory 50(12): 3265-3290 (2004) - [c18]Bruno Durand, Andrei A. Muchnik, Maxim Ushakov, Nikolai K. Vereshchagin:
Ecological Turing Machines. ICALP 2004: 457-468 - [c17]Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi:
Individual Communication Complexity: Extended Abstract. STACS 2004: 19-30 - [i16]Nikolai K. Vereshchagin, Paul M. B. Vitányi:
A Theory of Lossy Compression for Individual Data. CoRR cs.IT/0411014 (2004) - [i15]Nikolai K. Vereshchagin:
Kolmogorov complexity of enumerating finite sets. Electron. Colloquium Comput. Complex. TR04 (2004) - [i14]Andrei A. Muchnik, Alexander Shen, Nikolai K. Vereshchagin, Michael V. Vyugin:
Non-reducible descriptions for conditional Kolmogorov complexity. Electron. Colloquium Comput. Complex. TR04 (2004) - [i13]Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin:
Kolmogorov Complexity with Error. Electron. Colloquium Comput. Complex. TR04 (2004) - [i12]Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin:
Increasing Kolmogorov Complexity. Electron. Colloquium Comput. Complex. TR04 (2004) - 2003
- [j14]Olga Mitina, Nikolai K. Vereshchagin:
How to use several noisy channels with unknown error probabilities. Inf. Comput. 184(2): 229-241 (2003) - [j13]Bruno Durand, Vladimir Kanovei, Vladimir A. Uspensky, Nikolai K. Vereshchagin:
Do stronger definitions of randomness exist? Theor. Comput. Sci. 290(3): 1987-1996 (2003) - [i11]Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi:
Individual Communication Complexity. CoRR cs.CC/0304012 (2003) - 2002
- [b2]Alexander Shen, Nikolai K. Vereshchagin:
Basic set theory. Student mathematical library 17, American Mathematical Society 2002, ISBN 978-0-8218-2731-4, pp. I-VIII, 1-116 - [j12]Konstantin Makarychev, Yury Makarychev, Andrei E. Romashchenko, Nikolai K. Vereshchagin:
A new class of non-Shannon-type inequalities for entropies. Commun. Inf. Syst. 2(2): 147-166 (2002) - [j11]Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin:
Descriptive complexity of computable sequences. Theor. Comput. Sci. 271(1-2): 47-58 (2002) - [j10]Nikolai K. Vereshchagin:
Kolmogorov complexity conditional to large integers. Theor. Comput. Sci. 271(1-2): 59-67 (2002) - [j9]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) - [j8]Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin:
Combinatorial interpretation of Kolmogorov complexity. Theor. Comput. Sci. 271(1-2): 111-123 (2002) - [j7]Alexander Shen, Nikolai K. Vereshchagin:
Logical operations and Kolmogorov complexity. Theor. Comput. Sci. 271(1-2): 125-129 (2002) - [j6]Nikolai K. Vereshchagin, Michael V. Vyugin:
Independent minimum length programs to translate between given strings. Theor. Comput. Sci. 271(1-2): 131-143 (2002) - [c16]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 - [c15]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 - [i10]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) - 2001
- [c14]Andrei A. Muchnik, Nikolai K. Vereshchagin:
Logical Operations and Kolmogorov Complexity II. Computational Complexity Conference 2001: 256-265 - [i9]Nikolai K. Vereshchagin:
An enumerable undecidable set with low prefix complexity: a simplified proof. Electron. Colloquium Comput. Complex. TR01 (2001) - [i8]Nikolai K. Vereshchagin:
Kolmogorov Complexity Conditional to Large Integers. Electron. Colloquium Comput. Complex. TR01 (2001) - [i7]Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin:
Descriptive complexity of computable sequences. Electron. Colloquium Comput. Complex. TR01 (2001) - [i6]Alexander Shen, Nikolai K. Vereshchagin:
Logical operations and Kolmogorov complexity. Electron. Colloquium Comput. Complex. TR01 (2001) - [i5]Andrei A. Muchnik, Nikolai K. Vereshchagin:
Logical operations and Kolmogorov complexity. II. Electron. Colloquium Comput. Complex. TR01 (2001) - 2000
- [j5]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) - [c13]Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin:
Combinatorial Interpretation of Kolmogorov Complexity. Computational Complexity Conference 2000: 131-137 - [c12]Nikolai K. Vereshchagin, Michael V. Vyugin:
Independent Minimum Length Programs to Translate between Given Strings. Computational Complexity Conference 2000: 138- - [i4]Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin:
Combinatorial Interpretation of Kolmogorov Complexity. Electron. Colloquium Comput. Complex. TR00 (2000) - [i3]Nikolai K. Vereshchagin, Michael V. Vyugin:
Independent minimum length programs to translate between given strings. Electron. Colloquium Comput. Complex. TR00 (2000)
1990 – 1999
- 1999
- [b1]Lev D. Beklemishev, Mati Pentus, Nikolai K. Vereshchagin:
Provability, complexity, grammars. American Mathematical Society translations series 2 192, American Mathematical Society 1999, ISBN 978-0-8218-1078-1, pp. I-VIII, 1-172 - [j4]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) - [c11]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". Computational Complexity Conference 1999: 114- - [c10]Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin:
Descriptive Complexity of Computable Sequences. STACS 1999: 153-162 - [i2]Alexander A. Razborov, Nikolai K. Vereshchagin:
One Property of Cross-Intersecting Families. Electron. Colloquium Comput. Complex. TR99 (1999) - 1998
- [j3]Nikolai K. Vereshchagin:
Randomized Boolean Decision Trees: Several Remarks. Theor. Comput. Sci. 207(2): 329-342 (1998) - [c9]Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin:
Arthur-Merlin Games in Boolean Decision Trees. Computational Complexity Conference 1998: 58-67 - [c8]Sylvain Porrot, Max Dauchet, Bruno Durand, Nikolai K. Vereshchagin:
Deterministic Rational Transducers and Random Sequences. FoSSaCS 1998: 258-272 - 1997
- [c7]Daniel Hammer, Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin:
Inequalities for Shannon entropies and Kolmogorov complexities. Computational Complexity Conference 1997: 13-23 - [i1]Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin:
Arthur-Merlin Games in Boolean Decision Trees. Electron. Colloquium Comput. Complex. TR97 (1997) - 1996
- [j2]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
- [c6]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 - [c5]Nikolai K. Vereshchagin:
NP-sets are Co-NP-immune Relative to a Random Oracle. ISTCS 1995: 40-45 - [c4]Nikolai K. Vereshchagin:
Lower Bounds for Perceptrons Solving some Separation Problems and Oracle Separation of AM from PP. ISTCS 1995: 46-51 - 1993
- [j1]Lane A. Hemaspaandra, Sanjay Jain, Nikolai K. Vereshchagin:
Banishing Robust Turing Completeness. Int. J. Found. Comput. Sci. 4(3): 245-265 (1993) - [c3]Nikolai K. Vereshchagin:
Relationships between NP-sets, Co-NP-sets, and P-sets relative to random oracles. Computational Complexity Conference 1993: 132-138 - 1992
- [c2]Nikolai K. Vereshchagin:
On The Power of PP. Computational Complexity Conference 1992: 138-143 - [c1]Lane A. Hemachandra, Sanjay Jain, Nikolai K. Vereshchagin:
Banishing Robust Turing Completeness. LFCS 1992: 186-197