| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin |
Limit complexities revisited [once more]  |
CoRR  |
2012 |
DBLP BibTeX RDF |
|
| 1 | 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". |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Alexander S. Kulikov, Nikolay K. Vereshchagin (eds.) |
Computer Science - Theory and Applications - 6th International Computer Science Symposium in Russia, CSR 2011, St. Petersburg, Russia, June 14-18, 2011. Proceedings |
CSR |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolai K. Vereshchagin |
Sparse Selfreducible Sets and Nonuniform Lower Bounds. |
Electronic Colloquium on Computational Complexity (ECCC) |
2010 |
DBLP BibTeX RDF |
|
| 1 | Andrej Muchnik, Ilya Mezhirov, Alexander Shen, Nikolai K. Vereshchagin |
Game interpretation of Kolmogorov complexity |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin |
Limit Complexities Revisited. |
Theory Comput. Syst. |
2010 |
DBLP BibTeX RDF |
|
| 1 | 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. |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikolai K. Vereshchagin, Paul M. B. Vitányi |
Rate distortion and denoising of individual data using Kolmogorov complexity. |
IEEE Transactions on Information Theory |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikolay K. Vereshchagin |
{Algorithmic Minimal Sufficient Statistics: a New Definition. |
Electronic Colloquium on Computational Complexity (ECCC) |
2010 |
DBLP BibTeX RDF |
|
| 1 | Nikolay K. Vereshchagin |
An Encoding Invariant Version of Polynomial Time Computable Distributions. |
Electronic Colloquium on Computational Complexity (ECCC) |
2010 |
DBLP BibTeX RDF |
|
| 1 | Ilya Mezhirov, Nikolay K. Vereshchagin |
On abstract resource semantics and computability logic. |
J. Comput. Syst. Sci. |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikolay K. Vereshchagin |
An Encoding Invariant Version of Polynomial Time Computable Distributions. |
CSR |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikolay K. Vereshchagin |
Kolmogorov Complexity and Model Selection. |
CSR |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikolay K. Vereshchagin |
Algorithmic Minimal Sufficient Statistic Revisited. |
CiE |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin |
Limit complexities revisited |
CoRR |
2008 |
DBLP BibTeX RDF |
|
| 1 | Ilya Mezhirov, Nikolai K. Vereshchagin |
On Game Semantics of the Affine and Intuitionistic Logics. |
WoLLIC |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexey V. Chernov, Alexander Shen, Nikolai K. Vereshchagin, Vladimir Vovk |
On-Line Probability, Complexity and Randomness. |
ALT |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Harry Buhrman, Michal Koucký, Nikolai K. Vereshchagin |
Randomised Individual Communication Complexity. |
IEEE Conference on Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
individual communication complexity, Kolmogorov complexity, rounds, randomized protocols |
| 1 | Nikolay K. Vereshchagin |
Kolmogorov Complexity and Games. |
Bulletin of the EATCS |
2008 |
DBLP BibTeX RDF |
|
| 1 | Nikolai K. Vereshchagin |
Kolmogorov complexity of enumerating finite sets. |
Inf. Process. Lett. |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrej Muchnik, Alexander Shen, Mikhail Ustinov, Nikolai K. Vereshchagin, Michael V. Vyugin |
Non-reducible descriptions for conditional Kolmogorov complexity. |
Theor. Comput. Sci. |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | 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. |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi |
Individual communication complexity. |
J. Comput. Syst. Sci. |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin |
Inverting Onto Functions and Polynomial Hierarchy. |
CSR |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | 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 |
DBLP BibTeX RDF |
|
| 1 | Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir, Nikolai K. Vereshchagin |
High Entropy Random Selection Protocols. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Harry Buhrman, Nikolai K. Vereshchagin, Ronald de Wolf |
On Computation and Communication with Small Bias. |
IEEE Conference on Computational Complexity |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin |
Inverting onto functions might not be hard. |
Electronic Colloquium on Computational Complexity (ECCC) |
2006 |
DBLP BibTeX RDF |
|
| 1 | Andrei A. Muchnik, Nikolai K. Vereshchagin |
Shannon Entropy vs. Kolmogorov Complexity. |
CSR |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin, Michael V. Vyugin |
Non-reducible Descriptions for Conditional Kolmogorov Complexity. |
TAMC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin |
Kolmogorov Complexity with Error. |
STACS |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai K. Vereshchagin |
Partitioning multi-dimensional sets in a small number of ``uniform'' parts |
Electronic Colloquium on Computational Complexity (ECCC) |
2005 |
DBLP BibTeX RDF |
|
| 1 | Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin |
Increasing Kolmogorov Complexity. |
STACS |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Bruno Durand, Nikolai K. Vereshchagin |
Kolmogorov-Loveland stochasticity for finite strings. |
Inf. Process. Lett. |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrei A. Muchnik, Alexander Shen, Nikolai K. Vereshchagin, Michael V. Vyugin |
Non-reducible descriptions for conditional Kolmogorov complexity |
Electronic Colloquium on Computational Complexity (ECCC) |
2004 |
DBLP BibTeX RDF |
|
| 1 | Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin |
Increasing Kolmogorov Complexity |
Electronic Colloquium on Computational Complexity (ECCC) |
2004 |
DBLP BibTeX RDF |
|
| 1 | Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin |
Kolmogorov Complexity with Error |
Electronic Colloquium on Computational Complexity (ECCC) |
2004 |
DBLP BibTeX RDF |
|
| 1 | Nikolai K. Vereshchagin |
Kolmogorov complexity of enumerating finite sets |
Electronic Colloquium on Computational Complexity (ECCC) |
2004 |
DBLP BibTeX RDF |
|
| 1 | Nikolai K. Vereshchagin, Paul M. B. Vitányi |
A Theory of Lossy Compression for Individual Data |
CoRR |
2004 |
DBLP BibTeX RDF |
|
| 1 | Nikolai K. Vereshchagin, Paul M. B. Vitányi |
Kolmogorov's structure functions and model selection. |
IEEE Transactions on Information Theory |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Bruno Durand, Andrei A. Muchnik, Maxim Ushakov, Nikolai K. Vereshchagin |
Ecological Turing Machines. |
ICALP |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi |
Individual Communication Complexity: Extended Abstract. |
STACS |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Bruno Durand, Vladimir Kanovei, Vladimir A. Uspensky, Nikolai K. Vereshchagin |
Do stronger definitions of randomness exist? |
Theor. Comput. Sci. |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Olga Mitina, Nikolai K. Vereshchagin |
How to use several noisy channels with unknown error probabilities. |
Inf. Comput. |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi |
Individual Communication Complexity |
CoRR |
2003 |
DBLP BibTeX RDF |
|
| 1 | Nikolai K. Vereshchagin, Michael V. Vyugin |
Independent minimum length programs to translate between given strings. |
Theor. Comput. Sci. |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin |
Combinatorial interpretation of Kolmogorov complexity. |
Theor. Comput. Sci. |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin |
Descriptive complexity of computable sequences. |
Theor. Comput. Sci. |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | 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. |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexander Shen, Nikolai K. Vereshchagin |
Logical operations and Kolmogorov complexity. |
Theor. Comput. Sci. |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikolai K. Vereshchagin |
Kolmogorov complexity conditional to large integers. |
Theor. Comput. Sci. |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikolai K. Vereshchagin, Paul M. B. Vitányi |
Kolmogorov's Structure Functions with an Application to the Foundations of Model Selection |
CoRR |
2002 |
DBLP BibTeX RDF |
|
| 1 | Nikolai K. Vereshchagin, Paul M. B. Vitányi |
Kolmogorov's Structure Functions with an Application to the Foundations of Model Selection. (PDF / PS) |
FOCS |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | 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 |
DBLP DOI BibTeX RDF |
superintuitionistic logics, Kolmogorov complexity, realizability |
| 1 | Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin |
Descriptive complexity of computable sequences |
Electronic Colloquium on Computational Complexity (ECCC) |
2001 |
DBLP BibTeX RDF |
|
| 1 | Andrei A. Muchnik, Nikolai K. Vereshchagin |
Logical operations and Kolmogorov complexity. II |
Electronic Colloquium on Computational Complexity (ECCC) |
2001 |
DBLP BibTeX RDF |
|
| 1 | Nikolai K. Vereshchagin |
Kolmogorov Complexity Conditional to Large Integers |
Electronic Colloquium on Computational Complexity (ECCC) |
2001 |
DBLP BibTeX RDF |
|
| 1 | Nikolai K. Vereshchagin |
An enumerable undecidable set with low prefix complexity: a simplified proof |
Electronic Colloquium on Computational Complexity (ECCC) |
2001 |
DBLP BibTeX RDF |
|
| 1 | Alexander Shen, Nikolai K. Vereshchagin |
Logical operations and Kolmogorov complexity |
Electronic Colloquium on Computational Complexity (ECCC) |
2001 |
DBLP BibTeX RDF |
|
| 1 | Andrei A. Muchnik, Nikolai K. Vereshchagin |
Logical Operations and Kolmogorov Complexity II. (PDF / PS) |
IEEE Conference on Computational Complexity |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikolai K. Vereshchagin, Michael V. Vyugin |
Independent minimum length programs to translate between given strings |
Electronic Colloquium on Computational Complexity (ECCC) |
2000 |
DBLP BibTeX RDF |
|
| 1 | Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin |
Combinatorial Interpretation of Kolmogorov Complexity |
Electronic Colloquium on Computational Complexity (ECCC) |
2000 |
DBLP BibTeX RDF |
|
| 1 | Daniel Hammer, Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin |
Inequalities for Shannon Entropy and Kolmogorov Complexity. |
J. Comput. Syst. Sci. |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikolai K. Vereshchagin, Michael V. Vyugin |
Independent Minimum Length Programs to Translate between Given Strings. (PDF / PS) |
IEEE Conference on Computational Complexity |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin |
Combinatorial Interpretation of Kolmogorov Complexity. (PDF / PS) |
IEEE Conference on Computational Complexity |
2000 |
DBLP DOI BibTeX RDF |
algorithmic information theory, combinatorial inequalities, Kolmogorov complexity |
| 1 | Alexander A. Razborov, Nikolai K. Vereshchagin |
One Property of Cross-Intersecting Families |
Electronic Colloquium on Computational Complexity (ECCC) |
1999 |
DBLP BibTeX RDF |
|
| 1 | Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin |
Arthur-Merlin Games in Boolean Decision Trees. |
J. Comput. Syst. Sci. |
1999 |
DBLP DOI BibTeX RDF |
|
| 1 | Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin |
Descriptive Complexity of Computable Sequences. |
STACS |
1999 |
DBLP DOI BibTeX RDF |
|
| 1 | 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". (PDF / PS) |
IEEE Conference on Computational Complexity |
1999 |
DBLP DOI BibTeX RDF |
Turing degrees, mutual information, Kolmogorov complexity |
| 1 | Nikolai K. Vereshchagin |
Randomized Boolean Decision Trees: Several Remarks. |
Theor. Comput. Sci. |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Sylvain Porrot, Max Dauchet, Bruno Durand, Nikolai K. Vereshchagin |
Deterministic Rational Transducers and Random Sequences. |
FoSSaCS |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin |
Arthur-Merlin Games in Boolean Decision Trees. (PDF / PS) |
IEEE Conference on Computational Complexity |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin |
Arthur-Merlin Games in Boolean Decision Trees |
Electronic Colloquium on Computational Complexity (ECCC) |
1997 |
DBLP BibTeX RDF |
|
| 1 | Daniel Hammer, Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin |
Inequalities for Shannon entropies and Kolmogorov complexities. (PDF / PS) |
IEEE Conference on Computational Complexity |
1997 |
DBLP DOI BibTeX RDF |
finite objects, Ingleton's inequality, Gacs-Korner's results, computational complexity, Kolmogorov complexities, Shannon entropies, linear inequalities |
| 1 | Andrei A. Muchnik, Nikolai K. Vereshchagin |
A General Method to Construct Oracles Realizing Given Relationships Between Complexity Classes. |
Theor. Comput. Sci. |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikolai K. Vereshchagin |
Lower Bounds for Perceptrons Solving some Separation Problems and Oracle Separation of AM from PP. |
ISTCS |
1995 |
DBLP BibTeX RDF |
|
| 1 | Nikolai K. Vereshchagin |
NP-sets are Co-NP-immune Relative to a Random Oracle. |
ISTCS |
1995 |
DBLP BibTeX RDF |
|
| 1 | Olga Mitina, Nikolai K. Vereshchagin |
How to Use Expert Advice in the Case when Actual Values of Estimated Events Remain Unknown. |
COLT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Lane A. Hemaspaandra, Sanjay Jain, Nikolai K. Vereshchagin |
Banishing Robust Turing Completeness. |
Int. J. Found. Comput. Sci. |
1993 |
DBLP BibTeX RDF |
|
| 1 | Nikolai K. Vereshchagin |
Relationships between NP-sets, Co-NP-sets, and P-sets relative to random oracles. |
Structure in Complexity Theory Conference |
1993 |
DBLP BibTeX RDF |
|
| 1 | Lane A. Hemachandra, Sanjay Jain, Nikolai K. Vereshchagin |
Banishing Robust Turing Completeness. |
LFCS |
1992 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikolai K. Vereshchagin |
On The Power of PP. |
Structure in Complexity Theory Conference |
1992 |
DBLP BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")