Nikolai K. Vereshchagin

90 papers A* 3A 12B 4C 2Misc 4Journal 57Unranked 6

Year	Rank	Type	Title / Venue / Authors
2023	J	`jnl`	Half-duplex communication complexity with adversary? can be less than the classical communication complexity. Electron. Colloquium Comput. Complex. Mikhail Dektiarev, Nikolai K. Vereshchagin
2022	Misc	`conf`	How Much Randomness is Needed to Convert MA Protocols to AM Protocols? CSR Nikolai K. Vereshchagin
2021	J	`jnl`	High Entropy Random Selection Protocols. Algorithmica Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir, Nikolai K. Vereshchagin
2021	J	`jnl`	Proofs of conservation inequalities for Levin's notion of mutual information of 1974. Theor. Comput. Sci. Nikolai K. Vereshchagin
2020	J	`jnl`	On the Structure of Ammann A2 Tilings. Discret. Comput. Geom. Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin
2019	J	`jnl`	Sparse Selfreducible Sets and Nonuniform Lower Bounds. Algorithmica Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolai K. Vereshchagin
2018	J	`jnl`	A Conditional Information Inequality and Its Combinatorial Applications. IEEE Trans. Inf. Theory Tarik Kaced, Andrei Romashchenko, Nikolai K. Vereshchagin
2018	J	`jnl`	Short lists with short programs in short time. Comput. Complex. Bruno Bauwens, Anton Makhlin, Nikolai K. Vereshchagin, Marius Zimand
2017	J	`jnl`	Short lists with short programs from programs of functions and strings. Theory Comput. Syst. Nikolai K. Vereshchagin
2017	J	`jnl`	Stochasticity in Algorithmic Statistics for Polynomial Time. Electron. Colloquium Comput. Complex. Alexey Milovanov, Nikolai K. Vereshchagin
2016	J	`jnl`	Algorithmic statistics: forty years later. CoRR Nikolai K. Vereshchagin, Alexander Shen
2016	J	`jnl`	Towards a Reverse Newman's Theorem in Interactive Information Complexity. Algorithmica Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman, Nikolai K. Vereshchagin
2015	J	`jnl`	Algorithmic statistics revisited. CoRR Nikolai K. Vereshchagin, Alexander Shen
2012	J	`jnl`	Limit complexities revisited [once more] CoRR Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin
2010	J	`jnl`	Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible? Theory Comput. Syst. Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin
2010	J	`jnl`	Game interpretation of Kolmogorov complexity CoRR Andrej Muchnik, Ilya Mezhirov, Alexander Shen, Nikolai K. Vereshchagin
2010	J	`jnl`	Limit Complexities Revisited. Theory Comput. Syst. Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin
2010	J	`jnl`	Rate distortion and denoising of individual data using Kolmogorov complexity. IEEE Trans. Inf. Theory Nikolai K. Vereshchagin, Paul M. B. Vitányi
2010	J	`jnl`	Sparse Selfreducible Sets and Nonuniform Lower Bounds. Electron. Colloquium Comput. Complex. Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolai K. Vereshchagin
2008	J	`jnl`	Limit complexities revisited CoRR Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin
2008	C	`conf`	On Game Semantics of the Affine and Intuitionistic Logics. WoLLIC Ilya Mezhirov, Nikolai K. Vereshchagin
2008	B	`conf`	On-Line Probability, Complexity and Randomness. ALT Alexey V. Chernov, Alexander Shen, Nikolai K. Vereshchagin, Vladimir Vovk
2008	A	`conf`	Randomised Individual Communication Complexity. CCC Harry Buhrman, Michal Koucký, Nikolai K. Vereshchagin
2007	—	`conf`	High Entropy Random Selection Protocols. APPROX-RANDOM Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir, Nikolai K. Vereshchagin
2007	—	`conf`	High Entropy Random Selection Protocols. Algebraic Methods in Computational Complexity Nikolai K. Vereshchagin, Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir
2007	J	`jnl`	Individual communication complexity. J. Comput. Syst. Sci. Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi
2007	Misc	`conf`	Inverting Onto Functions and Polynomial Hierarchy. CSR Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin
2007	J	`jnl`	Kolmogorov complexity of enumerating finite sets. Inf. Process. Lett. Nikolai K. Vereshchagin
2007	J	`jnl`	Non-reducible descriptions for conditional Kolmogorov complexity. Theor. Comput. Sci. Andrej Muchnik, Alexander Shen, Mikhail Ustinov, Nikolai K. Vereshchagin, Michael V. Vyugin
2007	A	`conf`	On Computation and Communication with Small Bias. CCC Harry Buhrman, Nikolai K. Vereshchagin, Ronald de Wolf
2007	J	`jnl`	Partitioning multi-dimensional sets in a small number of "uniform" parts. Eur. J. Comb. Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai K. Vereshchagin
2006	J	`jnl`	Inverting onto functions might not be hard. Electron. Colloquium Comput. Complex. Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin
2006	A	`conf`	Kolmogorov Complexity with Error. STACS Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin
2006	C	`conf`	Non-reducible Descriptions for Conditional Kolmogorov Complexity. TAMC Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin, Michael V. Vyugin
2006	B	`conf`	On Algorithmic Rate-Distortion Function. ISIT Nikolai K. Vereshchagin, Paul M. B. Vitányi
2006	Misc	`conf`	Shannon Entropy vs. Kolmogorov Complexity. CSR Andrei A. Muchnik, Nikolai K. Vereshchagin
2005	A	`conf`	Increasing Kolmogorov Complexity. STACS Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin
2005	J	`jnl`	Partitioning multi-dimensional sets in a small number of "uniform" parts Electron. Colloquium Comput. Complex. Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai K. Vereshchagin
2004	J	`jnl`	A Theory of Lossy Compression for Individual Data CoRR Nikolai K. Vereshchagin, Paul M. B. Vitányi
2004	A*	`conf`	Ecological Turing Machines. ICALP Bruno Durand, Andrei A. Muchnik, Maxim Ushakov, Nikolai K. Vereshchagin
2004	J	`jnl`	Increasing Kolmogorov Complexity Electron. Colloquium Comput. Complex. Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin
2004	A	`conf`	Individual Communication Complexity: Extended Abstract. STACS Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi
2004	J	`jnl`	Kolmogorov Complexity with Error Electron. Colloquium Comput. Complex. Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin
2004	J	`jnl`	Kolmogorov complexity of enumerating finite sets Electron. Colloquium Comput. Complex. Nikolai K. Vereshchagin
2004	J	`jnl`	Kolmogorov's structure functions and model selection. IEEE Trans. Inf. Theory Nikolai K. Vereshchagin, Paul M. B. Vitányi
2004	J	`jnl`	Kolmogorov-Loveland stochasticity for finite strings. Inf. Process. Lett. Bruno Durand, Nikolai K. Vereshchagin
2004	J	`jnl`	Non-reducible descriptions for conditional Kolmogorov complexity Electron. Colloquium Comput. Complex. Andrei A. Muchnik, Alexander Shen, Nikolai K. Vereshchagin, Michael V. Vyugin
2003	J	`jnl`	Do stronger definitions of randomness exist? Theor. Comput. Sci. Bruno Durand, Vladimir Kanovei, Vladimir A. Uspensky, Nikolai K. Vereshchagin
2003	J	`jnl`	How to use several noisy channels with unknown error probabilities. Inf. Comput. Olga Mitina, Nikolai K. Vereshchagin
2003	J	`jnl`	Individual Communication Complexity CoRR Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi
2002	J	`jnl`	A new class of non-Shannon-type inequalities for entropies. Commun. Inf. Syst. Konstantin Makarychev, Yury Makarychev, Andrei Romashchenko, Nikolai K. Vereshchagin
2002	—	`book`	Basic set theory. Alexander Shen, Nikolai K. Vereshchagin
2002	J	`jnl`	Combinatorial interpretation of Kolmogorov complexity. Theor. Comput. Sci. Andrei Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
2002	J	`jnl`	Descriptive complexity of computable sequences. Theor. Comput. Sci. Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin
2002	J	`jnl`	Independent minimum length programs to translate between given strings. Theor. Comput. Sci. Nikolai K. Vereshchagin, Michael V. Vyugin
2002	J	`jnl`	Kolmogorov complexity conditional to large integers. Theor. Comput. Sci. Nikolai K. Vereshchagin
2002	J	`jnl`	Kolmogorov's Structure Functions with an Application to the Foundations of Model Selection CoRR Nikolai K. Vereshchagin, Paul M. B. Vitányi
2002	A*	`conf`	Kolmogorov's Structure Functions with an Application to the Foundations of Model Selection. FOCS Nikolai K. Vereshchagin, Paul M. B. Vitányi
2002	J	`jnl`	Logical operations and Kolmogorov complexity. Theor. Comput. Sci. Alexander Shen, Nikolai K. Vereshchagin
2002	J	`jnl`	Upper semi-lattice of binary strings with the relation "x is simple conditional to y". Theor. Comput. Sci. Alexey V. Chernov, Andrei A. Muchnik, Andrei Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
2002	B	`conf`	Variants of Realizability for Propositional Formulas and the Logic of the Weak Law of Excluded Middle. CSL Alexey V. Chernov, Dmitrij P. Skvortsov, Elena Z. Skvortsova, Nikolai K. Vereshchagin
2001	J	`jnl`	An enumerable undecidable set with low prefix complexity: a simplified proof Electron. Colloquium Comput. Complex. Nikolai K. Vereshchagin
2001	J	`jnl`	Descriptive complexity of computable sequences Electron. Colloquium Comput. Complex. Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin
2001	J	`jnl`	Kolmogorov Complexity Conditional to Large Integers Electron. Colloquium Comput. Complex. Nikolai K. Vereshchagin
2001	A	`conf`	Logical Operations and Kolmogorov Complexity II. CCC Andrei A. Muchnik, Nikolai K. Vereshchagin
2001	J	`jnl`	Logical operations and Kolmogorov complexity Electron. Colloquium Comput. Complex. Alexander Shen, Nikolai K. Vereshchagin
2001	J	`jnl`	Logical operations and Kolmogorov complexity. II Electron. Colloquium Comput. Complex. Andrei A. Muchnik, Nikolai K. Vereshchagin
2000	J	`jnl`	Combinatorial Interpretation of Kolmogorov Complexity Electron. Colloquium Comput. Complex. Andrei Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
2000	A	`conf`	Combinatorial Interpretation of Kolmogorov Complexity. CCC Andrei Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
2000	A	`conf`	Independent Minimum Length Programs to Translate between Given Strings. CCC Nikolai K. Vereshchagin, Michael V. Vyugin
2000	J	`jnl`	Independent minimum length programs to translate between given strings Electron. Colloquium Comput. Complex. Nikolai K. Vereshchagin, Michael V. Vyugin
2000	J	`jnl`	Inequalities for Shannon Entropy and Kolmogorov Complexity. J. Comput. Syst. Sci. Daniel Hammer, Andrei Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
1999	J	`jnl`	Arthur-Merlin Games in Boolean Decision Trees. J. Comput. Syst. Sci. Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin
1999	A	`conf`	Descriptive Complexity of Computable Sequences. STACS Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin
1999	J	`jnl`	One Property of Cross-Intersecting Families Electron. Colloquium Comput. Complex. Alexander A. Razborov, Nikolai K. Vereshchagin
1999	—	`book`	Provability, complexity, grammars. Lev D. Beklemishev, Mati Pentus, Nikolai K. Vereshchagin
1999	A	`conf`	Upper Semilattice of Binary Strings with the Relation "x is Simple Conditional to y". CCC Andrei A. Muchnik, Andrei Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
1998	A	`conf`	Arthur-Merlin Games in Boolean Decision Trees. CCC Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin
1998	B	`conf`	Deterministic Rational Transducers and Random Sequences. FoSSaCS Sylvain Porrot, Max Dauchet, Bruno Durand, Nikolai K. Vereshchagin
1998	J	`jnl`	Randomized Boolean Decision Trees: Several Remarks. Theor. Comput. Sci. Nikolai K. Vereshchagin
1997	J	`jnl`	Arthur-Merlin Games in Boolean Decision Trees Electron. Colloquium Comput. Complex. Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin
1997	A	`conf`	Inequalities for Shannon entropies and Kolmogorov complexities. CCC Daniel Hammer, Andrei Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
1996	J	`jnl`	A General Method to Construct Oracles Realizing Given Relationships Between Complexity Classes. Theor. Comput. Sci. Andrei A. Muchnik, Nikolai K. Vereshchagin
1995	A*	`conf`	How to Use Expert Advice in the Case when Actual Values of Estimated Events Remain Unknown. COLT Olga Mitina, Nikolai K. Vereshchagin
1995	—	`conf`	Lower Bounds for Perceptrons Solving some Separation Problems and Oracle Separation of AM from PP. ISTCS Nikolai K. Vereshchagin
1995	—	`conf`	NP-sets are Co-NP-immune Relative to a Random Oracle. ISTCS Nikolai K. Vereshchagin
1993	J	`jnl`	Banishing Robust Turing Completeness. Int. J. Found. Comput. Sci. Lane A. Hemaspaandra, Sanjay Jain, Nikolai K. Vereshchagin
1993	—	`conf`	Relationships between NP-sets, Co-NP-sets, and P-sets relative to random oracles. SCT Nikolai K. Vereshchagin
1992	Misc	`conf`	Banishing Robust Turing Completeness. LFCS Lane A. Hemachandra, Sanjay Jain, Nikolai K. Vereshchagin
1992	—	`conf`	On The Power of PP. SCT Nikolai K. Vereshchagin