Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDBibTeX records: Nikolai K. Vereshchagin
@article{DBLP:journals/tcs/Vereshchagin23,
author = {Nikolay K. Vereshchagin},
title = {Information disclosure in the framework of Kolmogorov complexity},
journal = {Theor. Comput. Sci.},
volume = {940},
number = {Part},
pages = {108--122},
year = {2023},
url = {https://doi.org/10.1016/j.tcs.2022.10.001},
doi = {10.1016/J.TCS.2022.10.001},
timestamp = {Mon, 05 Dec 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/Vereshchagin23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2307-04530,
author = {Nikolay K. Vereshchagin},
title = {On information content in certain objects},
journal = {CoRR},
volume = {abs/2307.04530},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2307.04530},
doi = {10.48550/ARXIV.2307.04530},
eprinttype = {arXiv},
eprint = {2307.04530},
timestamp = {Mon, 24 Jul 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2307-04530.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/DektiarevV23,
author = {Mikhail Dektiarev and
Nikolai K. Vereshchagin},
title = {Half-duplex communication complexity with adversary? can be less than
the classical communication complexity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR23-011}},
year = {2023},
url = {https://eccc.weizmann.ac.il/report/2023/011},
eprinttype = {ECCC},
eprint = {TR23-011},
timestamp = {Mon, 06 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/eccc/DektiarevV23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/dcg/Vereshchagin22,
author = {Nikolay K. Vereshchagin},
title = {A Family of Non-Periodic Tilings of the Plane by Right Golden Triangles},
journal = {Discret. Comput. Geom.},
volume = {68},
number = {1},
pages = {188--217},
year = {2022},
url = {https://doi.org/10.1007/s00454-021-00367-4},
doi = {10.1007/S00454-021-00367-4},
timestamp = {Mon, 13 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/dcg/Vereshchagin22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/csr/Vereshchagin22,
author = {Nikolai K. Vereshchagin},
editor = {Alexander S. Kulikov and
Sofya Raskhodnikova},
title = {How Much Randomness is Needed to Convert {MA} Protocols to {AM} Protocols?},
booktitle = {Computer Science - Theory and Applications - 17th International Computer
Science Symposium in Russia, {CSR} 2022, Virtual Event, June 29 -
July 1, 2022, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {13296},
pages = {338--349},
publisher = {Springer},
year = {2022},
url = {https://doi.org/10.1007/978-3-031-09574-0\_21},
doi = {10.1007/978-3-031-09574-0\_21},
timestamp = {Mon, 05 Dec 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/csr/Vereshchagin22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Vereshchagin22,
author = {Nikolay K. Vereshchagin},
title = {How much randomness is needed to convert {MA} protocols to {AM} protocols?},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR22-060}},
year = {2022},
url = {https://eccc.weizmann.ac.il/report/2022/060},
eprinttype = {ECCC},
eprint = {TR22-060},
timestamp = {Mon, 11 Jul 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Vereshchagin22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/BuhrmanCKLPV21,
author = {Harry Buhrman and
Matthias Christandl and
Michal Kouck{\'{y}} and
Zvi Lotker and
Boaz Patt{-}Shamir and
Nikolai K. Vereshchagin},
title = {High Entropy Random Selection Protocols},
journal = {Algorithmica},
volume = {83},
number = {2},
pages = {667--694},
year = {2021},
url = {https://doi.org/10.1007/s00453-020-00770-y},
doi = {10.1007/S00453-020-00770-Y},
timestamp = {Wed, 07 Dec 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/algorithmica/BuhrmanCKLPV21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/Vereshchagin21,
author = {Nikolai K. Vereshchagin},
title = {Proofs of conservation inequalities for Levin's notion of mutual information
of 1974},
journal = {Theor. Comput. Sci.},
volume = {856},
pages = {14--20},
year = {2021},
url = {https://doi.org/10.1016/j.tcs.2020.12.003},
doi = {10.1016/J.TCS.2020.12.003},
timestamp = {Mon, 28 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/tcs/Vereshchagin21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2108-01685,
author = {Nikolay K. Vereshchagin},
title = {Information disclosure in the framework of Kolmogorov complexity},
journal = {CoRR},
volume = {abs/2108.01685},
year = {2021},
url = {https://arxiv.org/abs/2108.01685},
eprinttype = {arXiv},
eprint = {2108.01685},
timestamp = {Thu, 09 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2108-01685.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/dcg/DurandSV20,
author = {Bruno Durand and
Alexander Shen and
Nikolai K. Vereshchagin},
title = {On the Structure of Ammann {A2} Tilings},
journal = {Discret. Comput. Geom.},
volume = {63},
number = {3},
pages = {577--606},
year = {2020},
url = {https://doi.org/10.1007/s00454-019-00074-1},
doi = {10.1007/S00454-019-00074-1},
timestamp = {Wed, 19 May 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/dcg/DurandSV20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/Vereshchagin20,
author = {Nikolay K. Vereshchagin},
title = {Descriptive complexity of computable sequences revisited},
journal = {Theor. Comput. Sci.},
volume = {809},
pages = {531--537},
year = {2020},
url = {https://doi.org/10.1016/j.tcs.2020.01.013},
doi = {10.1016/J.TCS.2020.01.013},
timestamp = {Fri, 31 Jan 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/Vereshchagin20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2007-10658,
author = {Nikolay K. Vereshchagin},
title = {A family of non-periodic tilings of the plane by right golden triangles},
journal = {CoRR},
volume = {abs/2007.10658},
year = {2020},
url = {https://arxiv.org/abs/2007.10658},
eprinttype = {arXiv},
eprint = {2007.10658},
timestamp = {Wed, 29 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2007-10658.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/BuhrmanTUV19,
author = {Harry Buhrman and
Leen Torenvliet and
Falk Unger and
Nikolai K. Vereshchagin},
title = {Sparse Selfreducible Sets and Nonuniform Lower Bounds},
journal = {Algorithmica},
volume = {81},
number = {1},
pages = {179--200},
year = {2019},
url = {https://doi.org/10.1007/s00453-018-0439-0},
doi = {10.1007/S00453-018-0439-0},
timestamp = {Fri, 18 Jan 2019 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/algorithmica/BuhrmanTUV19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1911-05447,
author = {Nikolay K. Vereshchagin},
title = {Proofs of conservation inequalities for Levin's notion of mutual information
of 1974},
journal = {CoRR},
volume = {abs/1911.05447},
year = {2019},
url = {http://arxiv.org/abs/1911.05447},
eprinttype = {arXiv},
eprint = {1911.05447},
timestamp = {Mon, 02 Dec 2019 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1911-05447.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/BauwensMVZ18,
author = {Bruno Bauwens and
Anton Makhlin and
Nikolai K. Vereshchagin and
Marius Zimand},
title = {Short lists with short programs in short time},
journal = {Comput. Complex.},
volume = {27},
number = {1},
pages = {31--61},
year = {2018},
url = {https://doi.org/10.1007/s00037-017-0154-2},
doi = {10.1007/S00037-017-0154-2},
timestamp = {Mon, 26 Oct 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cc/BauwensMVZ18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tit/KacedRV18,
author = {Tarik Kaced and
Andrei E. Romashchenko and
Nikolai K. Vereshchagin},
title = {A Conditional Information Inequality and Its Combinatorial Applications},
journal = {{IEEE} Trans. Inf. Theory},
volume = {64},
number = {5},
pages = {3610--3615},
year = {2018},
url = {https://doi.org/10.1109/TIT.2018.2806486},
doi = {10.1109/TIT.2018.2806486},
timestamp = {Tue, 10 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tit/KacedRV18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mst/Vereshchagin17,
author = {Nikolai K. Vereshchagin},
title = {Short lists with short programs from programs of functions and strings},
journal = {Theory Comput. Syst.},
volume = {61},
number = {4},
pages = {1440--1450},
year = {2017},
url = {https://doi.org/10.1007/s00224-017-9773-x},
doi = {10.1007/S00224-017-9773-X},
timestamp = {Tue, 07 Nov 2017 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/mst/Vereshchagin17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/birthday/VereshchaginS17,
author = {Nikolay K. Vereshchagin and
Alexander Shen},
editor = {Adam R. Day and
Michael R. Fellows and
Noam Greenberg and
Bakhadyr Khoussainov and
Alexander G. Melnikov and
Frances A. Rosamond},
title = {Algorithmic Statistics: Forty Years Later},
booktitle = {Computability and Complexity - Essays Dedicated to Rodney G. Downey
on the Occasion of His 60th Birthday},
series = {Lecture Notes in Computer Science},
volume = {10010},
pages = {669--737},
publisher = {Springer},
year = {2017},
url = {https://doi.org/10.1007/978-3-319-50062-1\_41},
doi = {10.1007/978-3-319-50062-1\_41},
timestamp = {Sun, 25 Oct 2020 23:08:30 +0100},
biburl = {https://dblp.org/rec/conf/birthday/VereshchaginS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/MilovanovV17,
author = {Alexey Milovanov and
Nikolay K. Vereshchagin},
editor = {Ryan O'Donnell},
title = {Stochasticity in Algorithmic Statistics for Polynomial Time},
booktitle = {32nd Computational Complexity Conference, {CCC} 2017, July 6-9, 2017,
Riga, Latvia},
series = {LIPIcs},
volume = {79},
pages = {17:1--17:18},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017},
url = {https://doi.org/10.4230/LIPIcs.CCC.2017.17},
doi = {10.4230/LIPICS.CCC.2017.17},
timestamp = {Thu, 02 Feb 2023 13:27:05 +0100},
biburl = {https://dblp.org/rec/conf/coco/MilovanovV17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/MilovanovV17,
author = {Alexey Milovanov and
Nikolai K. Vereshchagin},
title = {Stochasticity in Algorithmic Statistics for Polynomial Time},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR17-043}},
year = {2017},
url = {https://eccc.weizmann.ac.il/report/2017/043},
eprinttype = {ECCC},
eprint = {TR17-043},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/MilovanovV17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/BrodyBKLSV16,
author = {Joshua Brody and
Harry Buhrman and
Michal Kouck{\'{y}} and
Bruno Loff and
Florian Speelman and
Nikolai K. Vereshchagin},
title = {Towards a Reverse Newman's Theorem in Interactive Information Complexity},
journal = {Algorithmica},
volume = {76},
number = {3},
pages = {749--781},
year = {2016},
url = {https://doi.org/10.1007/s00453-015-0112-9},
doi = {10.1007/S00453-015-0112-9},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/algorithmica/BrodyBKLSV16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mst/Vereshchagin16,
author = {Nikolay K. Vereshchagin},
title = {Algorithmic Minimal Sufficient Statistics: a New Approach},
journal = {Theory Comput. Syst.},
volume = {58},
number = {3},
pages = {463--481},
year = {2016},
url = {https://doi.org/10.1007/s00224-014-9605-1},
doi = {10.1007/S00224-014-9605-1},
timestamp = {Fri, 30 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/mst/Vereshchagin16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/VereshchaginS16,
author = {Nikolai K. Vereshchagin and
Alexander Shen},
title = {Algorithmic statistics: forty years later},
journal = {CoRR},
volume = {abs/1607.08077},
year = {2016},
url = {http://arxiv.org/abs/1607.08077},
eprinttype = {arXiv},
eprint = {1607.08077},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/VereshchaginS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/KacedRV15,
author = {Tarik Kaced and
Andrei E. Romashchenko and
Nikolay K. Vereshchagin},
title = {Conditional Information Inequalities and Combinatorial Applications},
journal = {CoRR},
volume = {abs/1501.04867},
year = {2015},
url = {http://arxiv.org/abs/1501.04867},
eprinttype = {arXiv},
eprint = {1501.04867},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/KacedRV15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/VereshchaginS15,
author = {Nikolai K. Vereshchagin and
Alexander Shen},
title = {Algorithmic statistics revisited},
journal = {CoRR},
volume = {abs/1504.04950},
year = {2015},
url = {http://arxiv.org/abs/1504.04950},
eprinttype = {arXiv},
eprint = {1504.04950},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/VereshchaginS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mst/Vereshchagin14,
author = {Nikolay K. Vereshchagin},
title = {Encoding Invariance in Average Case Complexity},
journal = {Theory Comput. Syst.},
volume = {54},
number = {2},
pages = {305--317},
year = {2014},
url = {https://doi.org/10.1007/s00224-013-9517-5},
doi = {10.1007/S00224-013-9517-5},
timestamp = {Fri, 30 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/mst/Vereshchagin14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mst/Vereshchagin14a,
author = {Nikolay K. Vereshchagin},
title = {Editorial},
journal = {Theory Comput. Syst.},
volume = {55},
number = {2},
pages = {279--280},
year = {2014},
url = {https://doi.org/10.1007/s00224-013-9521-9},
doi = {10.1007/S00224-013-9521-9},
timestamp = {Fri, 30 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/mst/Vereshchagin14a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/csr/Vereshchagin14,
author = {Nikolay K. Vereshchagin},
editor = {Edward A. Hirsch and
Sergei O. Kuznetsov and
Jean{-}{\'{E}}ric Pin and
Nikolay K. Vereshchagin},
title = {Randomized Communication Complexity of Approximating Kolmogorov Complexity},
booktitle = {Computer Science - Theory and Applications - 9th International Computer
Science Symposium in Russia, {CSR} 2014, Moscow, Russia, June 7-11,
2014. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {8476},
pages = {365--374},
publisher = {Springer},
year = {2014},
url = {https://doi.org/10.1007/978-3-319-06686-8\_28},
doi = {10.1007/978-3-319-06686-8\_28},
timestamp = {Tue, 14 May 2019 10:00:51 +0200},
biburl = {https://dblp.org/rec/conf/csr/Vereshchagin14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dcfs/Vereshchagin14,
author = {Nikolay K. Vereshchagin},
editor = {Helmut J{\"{u}}rgensen and
Juhani Karhum{\"{a}}ki and
Alexander Okhotin},
title = {Aperiodic Tilings by Right Triangles},
booktitle = {Descriptional Complexity of Formal Systems - 16th International Workshop,
{DCFS} 2014, Turku, Finland, August 5-8, 2014. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {8614},
pages = {29--41},
publisher = {Springer},
year = {2014},
url = {https://doi.org/10.1007/978-3-319-09704-6\_4},
doi = {10.1007/978-3-319-09704-6\_4},
timestamp = {Tue, 14 May 2019 10:00:55 +0200},
biburl = {https://dblp.org/rec/conf/dcfs/Vereshchagin14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/csr/2014,
editor = {Edward A. Hirsch and
Sergei O. Kuznetsov and
Jean{-}{\'{E}}ric Pin and
Nikolay K. Vereshchagin},
title = {Computer Science - Theory and Applications - 9th International Computer
Science Symposium in Russia, {CSR} 2014, Moscow, Russia, June 7-11,
2014. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {8476},
publisher = {Springer},
year = {2014},
url = {https://doi.org/10.1007/978-3-319-06686-8},
doi = {10.1007/978-3-319-06686-8},
isbn = {978-3-319-06685-1},
timestamp = {Tue, 14 May 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/csr/2014.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cie/Vereshchagin13,
author = {Nikolay K. Vereshchagin},
editor = {Paola Bonizzoni and
Vasco Brattka and
Benedikt L{\"{o}}we},
title = {On Algorithmic Strong Sufficient Statistics},
booktitle = {The Nature of Computation. Logic, Algorithms, Applications - 9th Conference
on Computability in Europe, CiE 2013, Milan, Italy, July 1-5, 2013.
Proceedings},
series = {Lecture Notes in Computer Science},
volume = {7921},
pages = {424--433},
publisher = {Springer},
year = {2013},
url = {https://doi.org/10.1007/978-3-642-39053-1\_50},
doi = {10.1007/978-3-642-39053-1\_50},
timestamp = {Tue, 14 May 2019 10:00:41 +0200},
biburl = {https://dblp.org/rec/conf/cie/Vereshchagin13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/BrodyBKLSV13,
author = {Joshua Brody and
Harry Buhrman and
Michal Kouck{\'{y}} and
Bruno Loff and
Florian Speelman and
Nikolay K. Vereshchagin},
title = {Towards a Reverse Newman's Theorem in Interactive Information Complexity},
booktitle = {Proceedings of the 28th Conference on Computational Complexity, {CCC}
2013, K.lo Alto, California, USA, 5-7 June, 2013},
pages = {24--33},
publisher = {{IEEE} Computer Society},
year = {2013},
url = {https://doi.org/10.1109/CCC.2013.12},
doi = {10.1109/CCC.2013.12},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/BrodyBKLSV13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/BauwensMVZ13,
author = {Bruno Bauwens and
Anton Makhlin and
Nikolay K. Vereshchagin and
Marius Zimand},
title = {Short Lists with Short Programs in Short Time},
booktitle = {Proceedings of the 28th Conference on Computational Complexity, {CCC}
2013, K.lo Alto, California, USA, 5-7 June, 2013},
pages = {98--108},
publisher = {{IEEE} Computer Society},
year = {2013},
url = {https://doi.org/10.1109/CCC.2013.19},
doi = {10.1109/CCC.2013.19},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/BauwensMVZ13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/csr/Vereshchagin13,
author = {Nikolay K. Vereshchagin},
editor = {Andrei A. Bulatov and
Arseny M. Shur},
title = {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"},
booktitle = {Computer Science - Theory and Applications - 8th International Computer
Science Symposium in Russia, {CSR} 2013, Ekaterinburg, Russia, June
25-29, 2013. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {7913},
pages = {203--211},
publisher = {Springer},
year = {2013},
url = {https://doi.org/10.1007/978-3-642-38536-0\_18},
doi = {10.1007/978-3-642-38536-0\_18},
timestamp = {Tue, 14 May 2019 10:00:51 +0200},
biburl = {https://dblp.org/rec/conf/csr/Vereshchagin13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1301-1547,
author = {Bruno Bauwens and
Anton Makhlin and
Nikolay K. Vereshchagin and
Marius Zimand},
title = {Short lists with short programs in short time},
journal = {CoRR},
volume = {abs/1301.1547},
year = {2013},
url = {http://arxiv.org/abs/1301.1547},
eprinttype = {arXiv},
eprint = {1301.1547},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1301-1547.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BauwensMVZ13,
author = {Bruno Bauwens and
Anton Makhlin and
Nikolay K. Vereshchagin and
Marius Zimand},
title = {Short lists with short programs in short time},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR13-007}},
year = {2013},
url = {https://eccc.weizmann.ac.il/report/2013/007},
eprinttype = {ECCC},
eprint = {TR13-007},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BauwensMVZ13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Vereshchagin13,
author = {Nikolay K. Vereshchagin},
title = {Randomized communication complexity of appropximating Kolmogorov complexity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR13-178}},
year = {2013},
url = {https://eccc.weizmann.ac.il/report/2013/178},
eprinttype = {ECCC},
eprint = {TR13-178},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Vereshchagin13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1204-0201,
author = {Laurent Bienvenu and
Andrej Muchnik and
Alexander Shen and
Nikolai K. Vereshchagin},
title = {Limit complexities revisited [once more]},
journal = {CoRR},
volume = {abs/1204.0201},
year = {2012},
url = {http://arxiv.org/abs/1204.0201},
eprinttype = {arXiv},
eprint = {1204.0201},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1204-0201.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/csr/2011,
editor = {Alexander S. Kulikov and
Nikolay K. Vereshchagin},
title = {Computer Science - Theory and Applications - 6th International Computer
Science Symposium in Russia, {CSR} 2011, St. Petersburg, Russia, June
14-18, 2011. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {6651},
publisher = {Springer},
year = {2011},
url = {https://doi.org/10.1007/978-3-642-20712-9},
doi = {10.1007/978-3-642-20712-9},
isbn = {978-3-642-20711-2},
timestamp = {Tue, 14 May 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/csr/2011.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Vereshchagin11,
author = {Nikolay K. Vereshchagin},
title = {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"},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR11-167}},
year = {2011},
url = {https://eccc.weizmann.ac.il/report/2011/167},
eprinttype = {ECCC},
eprint = {TR11-167},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Vereshchagin11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/MezhirovV10,
author = {Ilya Mezhirov and
Nikolay K. Vereshchagin},
title = {On abstract resource semantics and computability logic},
journal = {J. Comput. Syst. Sci.},
volume = {76},
number = {5},
pages = {356--372},
year = {2010},
url = {https://doi.org/10.1016/j.jcss.2009.10.008},
doi = {10.1016/J.JCSS.2009.10.008},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/MezhirovV10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mst/BuhrmanFKRV10,
author = {Harry Buhrman and
Lance Fortnow and
Michal Kouck{\'{y}} and
John D. Rogers and
Nikolai K. Vereshchagin},
title = {Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible?},
journal = {Theory Comput. Syst.},
volume = {46},
number = {1},
pages = {143--156},
year = {2010},
url = {https://doi.org/10.1007/s00224-008-9160-8},
doi = {10.1007/S00224-008-9160-8},
timestamp = {Thu, 02 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mst/BuhrmanFKRV10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mst/BienvenuMSV10,
author = {Laurent Bienvenu and
Andrej Muchnik and
Alexander Shen and
Nikolai K. Vereshchagin},
title = {Limit Complexities Revisited},
journal = {Theory Comput. Syst.},
volume = {47},
number = {3},
pages = {720--736},
year = {2010},
url = {https://doi.org/10.1007/s00224-009-9203-9},
doi = {10.1007/S00224-009-9203-9},
timestamp = {Fri, 30 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/mst/BienvenuMSV10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tit/VereshchaginV10,
author = {Nikolai K. Vereshchagin and
Paul M. B. Vit{\'{a}}nyi},
title = {Rate distortion and denoising of individual data using Kolmogorov
complexity},
journal = {{IEEE} Trans. Inf. Theory},
volume = {56},
number = {7},
pages = {3438--3454},
year = {2010},
url = {https://doi.org/10.1109/TIT.2010.2048491},
doi = {10.1109/TIT.2010.2048491},
timestamp = {Tue, 10 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tit/VereshchaginV10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/csr/Vereshchagin10,
author = {Nikolay K. Vereshchagin},
editor = {Farid M. Ablayev and
Ernst W. Mayr},
title = {An Encoding Invariant Version of Polynomial Time Computable Distributions},
booktitle = {Computer Science - Theory and Applications, 5th International Computer
Science Symposium in Russia, {CSR} 2010, Kazan, Russia, June 16-20,
2010. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {6072},
pages = {371--383},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-13182-0\_37},
doi = {10.1007/978-3-642-13182-0\_37},
timestamp = {Tue, 14 May 2019 10:00:51 +0200},
biburl = {https://dblp.org/rec/conf/csr/Vereshchagin10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1003-4712,
author = {Andrej Muchnik and
Ilya Mezhirov and
Alexander Shen and
Nikolai K. Vereshchagin},
title = {Game interpretation of Kolmogorov complexity},
journal = {CoRR},
volume = {abs/1003.4712},
year = {2010},
url = {http://arxiv.org/abs/1003.4712},
eprinttype = {arXiv},
eprint = {1003.4712},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1003-4712.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BuhrmanTUV10,
author = {Harry Buhrman and
Leen Torenvliet and
Falk Unger and
Nikolai K. Vereshchagin},
title = {Sparse Selfreducible Sets and Nonuniform Lower Bounds},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR10-163}},
year = {2010},
url = {https://eccc.weizmann.ac.il/report/2010/163},
eprinttype = {ECCC},
eprint = {TR10-163},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BuhrmanTUV10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Vereshchagin10,
author = {Nikolay K. Vereshchagin},
title = {Algorithmic Minimal Sufficient Statistics: a New Definition},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR10-090}},
year = {2010},
url = {https://eccc.weizmann.ac.il/report/2010/090},
eprinttype = {ECCC},
eprint = {TR10-090},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Vereshchagin10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Vereshchagin10a,
author = {Nikolay K. Vereshchagin},
title = {An Encoding Invariant Version of Polynomial Time Computable Distributions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR10-091}},
year = {2010},
url = {https://eccc.weizmann.ac.il/report/2010/091},
eprinttype = {ECCC},
eprint = {TR10-091},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Vereshchagin10a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cie/Vereshchagin09,
author = {Nikolay K. Vereshchagin},
editor = {Klaus Ambos{-}Spies and
Benedikt L{\"{o}}we and
Wolfgang Merkle},
title = {Algorithmic Minimal Sufficient Statistic Revisited},
booktitle = {Mathematical Theory and Computational Practice, 5th Conference on
Computability in Europe, CiE 2009, Heidelberg, Germany, July 19-24,
2009. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {5635},
pages = {478--487},
publisher = {Springer},
year = {2009},
url = {https://doi.org/10.1007/978-3-642-03073-4\_49},
doi = {10.1007/978-3-642-03073-4\_49},
timestamp = {Sun, 02 Jun 2019 21:17:54 +0200},
biburl = {https://dblp.org/rec/conf/cie/Vereshchagin09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/csr/Vereshchagin09,
author = {Nikolay K. Vereshchagin},
editor = {Anna E. Frid and
Andrey Morozov and
Andrey Rybalchenko and
Klaus W. Wagner},
title = {Kolmogorov Complexity and Model Selection},
booktitle = {Computer Science - Theory and Applications, Fourth International Computer
Science Symposium in Russia, {CSR} 2009, Novosibirsk, Russia, August
18-23, 2009. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {5675},
pages = {19--24},
publisher = {Springer},
year = {2009},
url = {https://doi.org/10.1007/978-3-642-03351-3\_3},
doi = {10.1007/978-3-642-03351-3\_3},
timestamp = {Mon, 01 Mar 2021 13:46:21 +0100},
biburl = {https://dblp.org/rec/conf/csr/Vereshchagin09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eatcs/Vereshchagin08,
author = {Nikolay K. Vereshchagin},
title = {Kolmogorov Complexity and Games},
journal = {Bull. {EATCS}},
volume = {94},
pages = {43--75},
year = {2008},
timestamp = {Thu, 18 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eatcs/Vereshchagin08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/alt/ChernovSVV08,
author = {Alexey V. Chernov and
Alexander Shen and
Nikolai K. Vereshchagin and
Vladimir Vovk},
editor = {Yoav Freund and
L{\'{a}}szl{\'{o}} Gy{\"{o}}rfi and
Gy{\"{o}}rgy Tur{\'{a}}n and
Thomas Zeugmann},
title = {On-Line Probability, Complexity and Randomness},
booktitle = {Algorithmic Learning Theory, 19th International Conference, {ALT}
2008, Budapest, Hungary, October 13-16, 2008. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {5254},
pages = {138--153},
publisher = {Springer},
year = {2008},
url = {https://doi.org/10.1007/978-3-540-87987-9\_15},
doi = {10.1007/978-3-540-87987-9\_15},
timestamp = {Sun, 25 Oct 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/alt/ChernovSVV08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/BuhrmanKV08,
author = {Harry Buhrman and
Michal Kouck{\'{y}} and
Nikolai K. Vereshchagin},
title = {Randomised Individual Communication Complexity},
booktitle = {Proceedings of the 23rd Annual {IEEE} Conference on Computational
Complexity, {CCC} 2008, 23-26 June 2008, College Park, Maryland, {USA}},
pages = {321--331},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/CCC.2008.33},
doi = {10.1109/CCC.2008.33},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/BuhrmanKV08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/wollic/MezhirovV08,
author = {Ilya Mezhirov and
Nikolai K. Vereshchagin},
editor = {Wilfrid Hodges and
Ruy J. G. B. de Queiroz},
title = {On Game Semantics of the Affine and Intuitionistic Logics},
booktitle = {Logic, Language, Information and Computation, 15th International Workshop,
WoLLIC 2008, Edinburgh, UK, July 1-4, 2008, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {5110},
pages = {28--42},
publisher = {Springer},
year = {2008},
url = {https://doi.org/10.1007/978-3-540-69937-8\_4},
doi = {10.1007/978-3-540-69937-8\_4},
timestamp = {Tue, 14 May 2019 10:00:40 +0200},
biburl = {https://dblp.org/rec/conf/wollic/MezhirovV08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-0802-2833,
author = {Laurent Bienvenu and
Andrej Muchnik and
Alexander Shen and
Nikolai K. Vereshchagin},
title = {Limit complexities revisited},
journal = {CoRR},
volume = {abs/0802.2833},
year = {2008},
url = {http://arxiv.org/abs/0802.2833},
eprinttype = {arXiv},
eprint = {0802.2833},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0802-2833.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ejc/AlonNSTV07,
author = {Noga Alon and
Ilan Newman and
Alexander Shen and
G{\'{a}}bor Tardos and
Nikolai K. Vereshchagin},
title = {Partitioning multi-dimensional sets in a small number of "uniform"
parts},
journal = {Eur. J. Comb.},
volume = {28},
number = {1},
pages = {134--144},
year = {2007},
url = {https://doi.org/10.1016/j.ejc.2005.08.002},
doi = {10.1016/J.EJC.2005.08.002},
timestamp = {Fri, 12 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/ejc/AlonNSTV07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ipl/Vereshchagin07,
author = {Nikolai K. Vereshchagin},
title = {Kolmogorov complexity of enumerating finite sets},
journal = {Inf. Process. Lett.},
volume = {103},
number = {1},
pages = {34--39},
year = {2007},
url = {https://doi.org/10.1016/j.ipl.2007.01.006},
doi = {10.1016/J.IPL.2007.01.006},
timestamp = {Fri, 30 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/ipl/Vereshchagin07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/BuhrmanKVV07,
author = {Harry Buhrman and
Hartmut Klauck and
Nikolai K. Vereshchagin and
Paul M. B. Vit{\'{a}}nyi},
title = {Individual communication complexity},
journal = {J. Comput. Syst. Sci.},
volume = {73},
number = {6},
pages = {973--985},
year = {2007},
url = {https://doi.org/10.1016/j.jcss.2007.03.015},
doi = {10.1016/J.JCSS.2007.03.015},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/BuhrmanKVV07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/MuchnikSUVV07,
author = {Andrej Muchnik and
Alexander Shen and
Mikhail Ustinov and
Nikolai K. Vereshchagin and
Michael V. Vyugin},
title = {Non-reducible descriptions for conditional Kolmogorov complexity},
journal = {Theor. Comput. Sci.},
volume = {384},
number = {1},
pages = {77--86},
year = {2007},
url = {https://doi.org/10.1016/j.tcs.2007.05.019},
doi = {10.1016/J.TCS.2007.05.019},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/MuchnikSUVV07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/BuhrmanCKLPV07,
author = {Harry Buhrman and
Matthias Christandl and
Michal Kouck{\'{y}} and
Zvi Lotker and
Boaz Patt{-}Shamir and
Nikolai K. Vereshchagin},
editor = {Moses Charikar and
Klaus Jansen and
Omer Reingold and
Jos{\'{e}} D. P. Rolim},
title = {High Entropy Random Selection Protocols},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, 10th International Workshop, {APPROX} 2007, and 11th
International Workshop, {RANDOM} 2007, Princeton, NJ, USA, August
20-22, 2007, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4627},
pages = {366--379},
publisher = {Springer},
year = {2007},
url = {https://doi.org/10.1007/978-3-540-74208-1\_27},
doi = {10.1007/978-3-540-74208-1\_27},
timestamp = {Sat, 30 Sep 2023 09:34:32 +0200},
biburl = {https://dblp.org/rec/conf/approx/BuhrmanCKLPV07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/BuhrmanVW07,
author = {Harry Buhrman and
Nikolai K. Vereshchagin and
Ronald de Wolf},
title = {On Computation and Communication with Small Bias},
booktitle = {22nd Annual {IEEE} Conference on Computational Complexity {(CCC} 2007),
13-16 June 2007, San Diego, California, {USA}},
pages = {24--32},
publisher = {{IEEE} Computer Society},
year = {2007},
url = {https://doi.org/10.1109/CCC.2007.18},
doi = {10.1109/CCC.2007.18},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/BuhrmanVW07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/csr/BuhrmanFKRV07,
author = {Harry Buhrman and
Lance Fortnow and
Michal Kouck{\'{y}} and
John D. Rogers and
Nikolai K. Vereshchagin},
editor = {Volker Diekert and
Mikhail V. Volkov and
Andrei Voronkov},
title = {Inverting Onto Functions and Polynomial Hierarchy},
booktitle = {Computer Science - Theory and Applications, Second International Symposium
on Computer Science in Russia, {CSR} 2007, Ekaterinburg, Russia, September
3-7, 2007, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4649},
pages = {92--103},
publisher = {Springer},
year = {2007},
url = {https://doi.org/10.1007/978-3-540-74510-5\_12},
doi = {10.1007/978-3-540-74510-5\_12},
timestamp = {Thu, 09 Nov 2023 20:20:35 +0100},
biburl = {https://dblp.org/rec/conf/csr/BuhrmanFKRV07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dagstuhl/VereshchaginBCKLP07,
author = {Nikolai K. Vereshchagin and
Harry Buhrman and
Matthias Christandl and
Michal Kouck{\'{y}} and
Zvi Lotker and
Boaz Patt{-}Shamir},
editor = {Manindra Agrawal and
Harry Buhrman and
Lance Fortnow and
Thomas Thierauf},
title = {High Entropy Random Selection Protocols},
booktitle = {Algebraic Methods in Computational Complexity, 07.10. - 12.10.2007},
series = {Dagstuhl Seminar Proceedings},
volume = {07411},
publisher = {Internationales Begegnungs- und Forschungszentrum fuer Informatik
(IBFI), Schloss Dagstuhl, Germany},
year = {2007},
url = {http://drops.dagstuhl.de/opus/volltexte/2008/1309},
timestamp = {Thu, 10 Jun 2021 13:02:08 +0200},
biburl = {https://dblp.org/rec/conf/dagstuhl/VereshchaginBCKLP07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/csr/MuchnikV06,
author = {Andrei A. Muchnik and
Nikolai K. Vereshchagin},
editor = {Dima Grigoriev and
John Harrison and
Edward A. Hirsch},
title = {Shannon Entropy vs. Kolmogorov Complexity},
booktitle = {Computer Science - Theory and Applications, First International Symposium
on Computer Science in Russia, {CSR} 2006, St. Petersburg, Russia,
June 8-12, 2006, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3967},
pages = {281--291},
publisher = {Springer},
year = {2006},
url = {https://doi.org/10.1007/11753728\_29},
doi = {10.1007/11753728\_29},
timestamp = {Tue, 29 Nov 2022 13:36:56 +0100},
biburl = {https://dblp.org/rec/conf/csr/MuchnikV06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/isit/VereshchaginV06,
author = {Nikolai K. Vereshchagin and
Paul M. B. Vit{\'{a}}nyi},
title = {On Algorithmic Rate-Distortion Function},
booktitle = {Proceedings 2006 {IEEE} International Symposium on Information Theory,
{ISIT} 2006, The Westin Seattle, Seattle, Washington, USA, July 9-14,
2006},
pages = {798--802},
publisher = {{IEEE}},
year = {2006},
url = {https://doi.org/10.1109/ISIT.2006.261723},
doi = {10.1109/ISIT.2006.261723},
timestamp = {Wed, 16 Oct 2019 14:14:48 +0200},
biburl = {https://dblp.org/rec/conf/isit/VereshchaginV06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/FortnowLV06,
author = {Lance Fortnow and
Troy Lee and
Nikolai K. Vereshchagin},
editor = {Bruno Durand and
Wolfgang Thomas},
title = {Kolmogorov Complexity with Error},
booktitle = {{STACS} 2006, 23rd Annual Symposium on Theoretical Aspects of Computer
Science, Marseille, France, February 23-25, 2006, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3884},
pages = {137--148},
publisher = {Springer},
year = {2006},
url = {https://doi.org/10.1007/11672142\_10},
doi = {10.1007/11672142\_10},
timestamp = {Wed, 19 May 2021 12:05:43 +0200},
biburl = {https://dblp.org/rec/conf/stacs/FortnowLV06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/tamc/MuchnikSVV06,
author = {Andrej Muchnik and
Alexander Shen and
Nikolai K. Vereshchagin and
Michael V. Vyugin},
editor = {Jin{-}yi Cai and
S. Barry Cooper and
Angsheng Li},
title = {Non-reducible Descriptions for Conditional Kolmogorov Complexity},
booktitle = {Theory and Applications of Models of Computation, Third International
Conference, {TAMC} 2006, Beijing, China, May 15-20, 2006, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3959},
pages = {308--317},
publisher = {Springer},
year = {2006},
url = {https://doi.org/10.1007/11750321\_29},
doi = {10.1007/11750321\_29},
timestamp = {Tue, 14 May 2019 10:00:46 +0200},
biburl = {https://dblp.org/rec/conf/tamc/MuchnikSVV06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BuhrmanFKRV06,
author = {Harry Buhrman and
Lance Fortnow and
Michal Kouck{\'{y}} and
John D. Rogers and
Nikolai K. Vereshchagin},
title = {Inverting onto functions might not be hard},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR06-024}},
year = {2006},
url = {https://eccc.weizmann.ac.il/eccc-reports/2006/TR06-024/index.html},
eprinttype = {ECCC},
eprint = {TR06-024},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BuhrmanFKRV06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/BuhrmanFNV05,
author = {Harry Buhrman and
Lance Fortnow and
Ilan Newman and
Nikolai K. Vereshchagin},
editor = {Volker Diekert and
Bruno Durand},
title = {Increasing Kolmogorov Complexity},
booktitle = {{STACS} 2005, 22nd Annual Symposium on Theoretical Aspects of Computer
Science, Stuttgart, Germany, February 24-26, 2005, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3404},
pages = {412--421},
publisher = {Springer},
year = {2005},
url = {https://doi.org/10.1007/978-3-540-31856-9\_34},
doi = {10.1007/978-3-540-31856-9\_34},
timestamp = {Wed, 19 May 2021 12:05:43 +0200},
biburl = {https://dblp.org/rec/conf/stacs/BuhrmanFNV05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR05-095,
author = {Noga Alon and
Ilan Newman and
Alexander Shen and
G{\'{a}}bor Tardos and
Nikolai K. Vereshchagin},
title = {Partitioning multi-dimensional sets in a small number of "uniform"
parts},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR05-095}},
year = {2005},
url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-095/index.html},
eprinttype = {ECCC},
eprint = {TR05-095},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-095.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ipl/DurandV04,
author = {Bruno Durand and
Nikolai K. Vereshchagin},
title = {Kolmogorov-Loveland stochasticity for finite strings},
journal = {Inf. Process. Lett.},
volume = {91},
number = {6},
pages = {263--269},
year = {2004},
url = {https://doi.org/10.1016/j.ipl.2004.05.014},
doi = {10.1016/J.IPL.2004.05.014},
timestamp = {Wed, 19 May 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ipl/DurandV04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tit/VereshchaginV04,
author = {Nikolai K. Vereshchagin and
Paul M. B. Vit{\'{a}}nyi},
title = {Kolmogorov's structure functions and model selection},
journal = {{IEEE} Trans. Inf. Theory},
volume = {50},
number = {12},
pages = {3265--3290},
year = {2004},
url = {https://doi.org/10.1109/TIT.2004.838346},
doi = {10.1109/TIT.2004.838346},
timestamp = {Tue, 10 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tit/VereshchaginV04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/DurandMUV04,
author = {Bruno Durand and
Andrei A. Muchnik and
Maxim Ushakov and
Nikolai K. Vereshchagin},
editor = {Josep D{\'{\i}}az and
Juhani Karhum{\"{a}}ki and
Arto Lepist{\"{o}} and
Donald Sannella},
title = {Ecological Turing Machines},
booktitle = {Automata, Languages and Programming: 31st International Colloquium,
{ICALP} 2004, Turku, Finland, July 12-16, 2004. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3142},
pages = {457--468},
publisher = {Springer},
year = {2004},
url = {https://doi.org/10.1007/978-3-540-27836-8\_40},
doi = {10.1007/978-3-540-27836-8\_40},
timestamp = {Wed, 19 May 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/icalp/DurandMUV04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/BuhrmanKVV04,
author = {Harry Buhrman and
Hartmut Klauck and
Nikolai K. Vereshchagin and
Paul M. B. Vit{\'{a}}nyi},
editor = {Volker Diekert and
Michel Habib},
title = {Individual Communication Complexity: Extended Abstract},
booktitle = {{STACS} 2004, 21st Annual Symposium on Theoretical Aspects of Computer
Science, Montpellier, France, March 25-27, 2004, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {2996},
pages = {19--30},
publisher = {Springer},
year = {2004},
url = {https://doi.org/10.1007/978-3-540-24749-4\_3},
doi = {10.1007/978-3-540-24749-4\_3},
timestamp = {Tue, 14 May 2019 10:00:48 +0200},
biburl = {https://dblp.org/rec/conf/stacs/BuhrmanKVV04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/cs-IT-0411014,
author = {Nikolai K. Vereshchagin and
Paul M. B. Vit{\'{a}}nyi},
title = {A Theory of Lossy Compression for Individual Data},
journal = {CoRR},
volume = {cs.IT/0411014},
year = {2004},
url = {http://arxiv.org/abs/cs.IT/0411014},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/cs-IT-0411014.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-030,
author = {Nikolai K. Vereshchagin},
title = {Kolmogorov complexity of enumerating finite sets},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-030}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-030/index.html},
eprinttype = {ECCC},
eprint = {TR04-030},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-030.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-054,
author = {Andrei A. Muchnik and
Alexander Shen and
Nikolai K. Vereshchagin and
Michael V. Vyugin},
title = {Non-reducible descriptions for conditional Kolmogorov complexity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-054}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-054/index.html},
eprinttype = {ECCC},
eprint = {TR04-054},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-054.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-080,
author = {Lance Fortnow and
Troy Lee and
Nikolai K. Vereshchagin},
title = {Kolmogorov Complexity with Error},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-080}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-080/index.html},
eprinttype = {ECCC},
eprint = {TR04-080},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-080.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-081,
author = {Harry Buhrman and
Lance Fortnow and
Ilan Newman and
Nikolai K. Vereshchagin},
title = {Increasing Kolmogorov Complexity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-081}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-081/index.html},
eprinttype = {ECCC},
eprint = {TR04-081},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-081.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/iandc/MitinaV03,
author = {Olga Mitina and
Nikolai K. Vereshchagin},
title = {How to use several noisy channels with unknown error probabilities},
journal = {Inf. Comput.},
volume = {184},
number = {2},
pages = {229--241},
year = {2003},
url = {https://doi.org/10.1016/S0890-5401(03)00063-4},
doi = {10.1016/S0890-5401(03)00063-4},
timestamp = {Fri, 12 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/iandc/MitinaV03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/DurandKUV03,
author = {Bruno Durand and
Vladimir Kanovei and
Vladimir A. Uspensky and
Nikolai K. Vereshchagin},
title = {Do stronger definitions of randomness exist?},
journal = {Theor. Comput. Sci.},
volume = {290},
number = {3},
pages = {1987--1996},
year = {2003},
url = {https://doi.org/10.1016/S0304-3975(02)00040-3},
doi = {10.1016/S0304-3975(02)00040-3},
timestamp = {Wed, 19 May 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/tcs/DurandKUV03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/cs-CC-0304012,
author = {Harry Buhrman and
Hartmut Klauck and
Nikolai K. Vereshchagin and
Paul M. B. Vit{\'{a}}nyi},
title = {Individual Communication Complexity},
journal = {CoRR},
volume = {cs.CC/0304012},
year = {2003},
url = {http://arxiv.org/abs/cs/0304012},
timestamp = {Fri, 10 Jan 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/cs-CC-0304012.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@book{DBLP:books/daglib/0014725,
author = {Alexander Shen and
Nikolai K. Vereshchagin},
title = {Basic set theory},
series = {Student mathematical library},
volume = {17},
publisher = {American Mathematical Society},
year = {2002},
isbn = {978-0-8218-2731-4},
timestamp = {Mon, 15 Jul 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/books/daglib/0014725.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cominfsys/MakarychevMRV02,
author = {Konstantin Makarychev and
Yury Makarychev and
Andrei E. Romashchenko and
Nikolai K. Vereshchagin},
title = {A new class of non-Shannon-type inequalities for entropies},
journal = {Commun. Inf. Syst.},
volume = {2},
number = {2},
pages = {147--166},
year = {2002},
url = {https://doi.org/10.4310/cis.2002.v2.n2.a3},
doi = {10.4310/CIS.2002.V2.N2.A3},
timestamp = {Fri, 18 Sep 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/cominfsys/MakarychevMRV02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/DurandSV02,
author = {Bruno Durand and
Alexander Shen and
Nikolai K. Vereshchagin},
title = {Descriptive complexity of computable sequences},
journal = {Theor. Comput. Sci.},
volume = {271},
number = {1-2},
pages = {47--58},
year = {2002},
url = {https://doi.org/10.1016/S0304-3975(01)00030-5},
doi = {10.1016/S0304-3975(01)00030-5},
timestamp = {Wed, 19 May 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/tcs/DurandSV02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/Vereshchagin02,
author = {Nikolai K. Vereshchagin},
title = {Kolmogorov complexity conditional to large integers},
journal = {Theor. Comput. Sci.},
volume = {271},
number = {1-2},
pages = {59--67},
year = {2002},
url = {https://doi.org/10.1016/S0304-3975(01)00031-7},
doi = {10.1016/S0304-3975(01)00031-7},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/Vereshchagin02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/ChernovMRSV02,
author = {Alexey V. Chernov and
Andrei A. Muchnik and
Andrei E. Romashchenko and
Alexander Shen and
Nikolai K. Vereshchagin},
title = {Upper semi-lattice of binary strings with the relation "x is
simple conditional to y"},
journal = {Theor. Comput. Sci.},
volume = {271},
number = {1-2},
pages = {69--95},
year = {2002},
url = {https://doi.org/10.1016/S0304-3975(01)00032-9},
doi = {10.1016/S0304-3975(01)00032-9},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/ChernovMRSV02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/RomashchenkoSV02,
author = {Andrei E. Romashchenko and
Alexander Shen and
Nikolai K. Vereshchagin},
title = {Combinatorial interpretation of Kolmogorov complexity},
journal = {Theor. Comput. Sci.},
volume = {271},
number = {1-2},
pages = {111--123},
year = {2002},
url = {https://doi.org/10.1016/S0304-3975(01)00034-2},
doi = {10.1016/S0304-3975(01)00034-2},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/RomashchenkoSV02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/ShenV02,
author = {Alexander Shen and
Nikolai K. Vereshchagin},
title = {Logical operations and Kolmogorov complexity},
journal = {Theor. Comput. Sci.},
volume = {271},
number = {1-2},
pages = {125--129},
year = {2002},
url = {https://doi.org/10.1016/S0304-3975(01)00035-4},
doi = {10.1016/S0304-3975(01)00035-4},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/ShenV02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/VereshchaginV02,
author = {Nikolai K. Vereshchagin and
Michael V. Vyugin},
title = {Independent minimum length programs to translate between given strings},
journal = {Theor. Comput. Sci.},
volume = {271},
number = {1-2},
pages = {131--143},
year = {2002},
url = {https://doi.org/10.1016/S0304-3975(01)00036-6},
doi = {10.1016/S0304-3975(01)00036-6},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/VereshchaginV02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/csl/ChernovSSV02,
author = {Alexey V. Chernov and
Dmitrij P. Skvortsov and
Elena Z. Skvortsova and
Nikolai K. Vereshchagin},
editor = {Julian C. Bradfield},
title = {Variants of Realizability for Propositional Formulas and the Logic
of the Weak Law of Excluded Middle},
booktitle = {Computer Science Logic, 16th International Workshop, {CSL} 2002, 11th
Annual Conference of the EACSL, Edinburgh, Scotland, UK, September
22-25, 2002, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {2471},
pages = {74--88},
publisher = {Springer},
year = {2002},
url = {https://doi.org/10.1007/3-540-45793-3\_6},
doi = {10.1007/3-540-45793-3\_6},
timestamp = {Tue, 14 May 2019 10:00:42 +0200},
biburl = {https://dblp.org/rec/conf/csl/ChernovSSV02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/VereshchaginV02,
author = {Nikolai K. Vereshchagin and
Paul M. B. Vit{\'{a}}nyi},
title = {Kolmogorov's Structure Functions with an Application to the Foundations
of Model Selection},
booktitle = {43rd Symposium on Foundations of Computer Science {(FOCS} 2002), 16-19
November 2002, Vancouver, BC, Canada, Proceedings},
pages = {751--760},
publisher = {{IEEE} Computer Society},
year = {2002},
url = {https://doi.org/10.1109/SFCS.2002.1182000},
doi = {10.1109/SFCS.2002.1182000},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/VereshchaginV02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/cs-CC-0204037,
author = {Nikolai K. Vereshchagin and
Paul M. B. Vit{\'{a}}nyi},
title = {Kolmogorov's Structure Functions with an Application to the Foundations
of Model Selection},
journal = {CoRR},
volume = {cs.CC/0204037},
year = {2002},
url = {http://arxiv.org/abs/cs.CC/0204037},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/cs-CC-0204037.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/MuchnikV01,
author = {Andrei A. Muchnik and
Nikolai K. Vereshchagin},
title = {Logical Operations and Kolmogorov Complexity {II}},
booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational
Complexity, Chicago, Illinois, USA, June 18-21, 2001},
pages = {256--265},
publisher = {{IEEE} Computer Society},
year = {2001},
url = {https://doi.org/10.1109/CCC.2001.933892},
doi = {10.1109/CCC.2001.933892},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/MuchnikV01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR01-083,
author = {Nikolai K. Vereshchagin},
title = {An enumerable undecidable set with low prefix complexity: a simplified
proof},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR01-083}},
year = {2001},
url = {https://eccc.weizmann.ac.il/eccc-reports/2001/TR01-083/index.html},
eprinttype = {ECCC},
eprint = {TR01-083},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR01-083.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR01-086,
author = {Nikolai K. Vereshchagin},
title = {Kolmogorov Complexity Conditional to Large Integers},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR01-086}},
year = {2001},
url = {https://eccc.weizmann.ac.il/eccc-reports/2001/TR01-086/index.html},
eprinttype = {ECCC},
eprint = {TR01-086},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR01-086.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR01-087,
author = {Bruno Durand and
Alexander Shen and
Nikolai K. Vereshchagin},
title = {Descriptive complexity of computable sequences},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR01-087}},
year = {2001},
url = {https://eccc.weizmann.ac.il/eccc-reports/2001/TR01-087/index.html},
eprinttype = {ECCC},
eprint = {TR01-087},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR01-087.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR01-088,
author = {Alexander Shen and
Nikolai K. Vereshchagin},
title = {Logical operations and Kolmogorov complexity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR01-088}},
year = {2001},
url = {https://eccc.weizmann.ac.il/eccc-reports/2001/TR01-088/index.html},
eprinttype = {ECCC},
eprint = {TR01-088},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR01-088.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR01-089,
author = {Andrei A. Muchnik and
Nikolai K. Vereshchagin},
title = {Logical operations and Kolmogorov complexity. {II}},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR01-089}},
year = {2001},
url = {https://eccc.weizmann.ac.il/eccc-reports/2001/TR01-089/index.html},
eprinttype = {ECCC},
eprint = {TR01-089},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR01-089.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/HammerRSV00,
author = {Daniel Hammer and
Andrei E. Romashchenko and
Alexander Shen and
Nikolai K. Vereshchagin},
title = {Inequalities for Shannon Entropy and Kolmogorov Complexity},
journal = {J. Comput. Syst. Sci.},
volume = {60},
number = {2},
pages = {442--464},
year = {2000},
url = {https://doi.org/10.1006/jcss.1999.1677},
doi = {10.1006/JCSS.1999.1677},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/HammerRSV00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/RomashchenkoSV00,
author = {Andrei E. Romashchenko and
Alexander Shen and
Nikolai K. Vereshchagin},
title = {Combinatorial Interpretation of Kolmogorov Complexity},
booktitle = {Proceedings of the 15th Annual {IEEE} Conference on Computational
Complexity, Florence, Italy, July 4-7, 2000},
pages = {131--137},
publisher = {{IEEE} Computer Society},
year = {2000},
url = {https://doi.org/10.1109/CCC.2000.856743},
doi = {10.1109/CCC.2000.856743},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/RomashchenkoSV00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/VereshchaginV00,
author = {Nikolai K. Vereshchagin and
Michael V. Vyugin},
title = {Independent Minimum Length Programs to Translate between Given Strings},
booktitle = {Proceedings of the 15th Annual {IEEE} Conference on Computational
Complexity, Florence, Italy, July 4-7, 2000},
pages = {138},
publisher = {{IEEE} Computer Society},
year = {2000},
url = {https://doi.org/10.1109/CCC.2000.856744},
doi = {10.1109/CCC.2000.856744},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/VereshchaginV00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR00-026,
author = {Andrei E. Romashchenko and
Alexander Shen and
Nikolai K. Vereshchagin},
title = {Combinatorial Interpretation of Kolmogorov Complexity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR00-026}},
year = {2000},
url = {https://eccc.weizmann.ac.il/eccc-reports/2000/TR00-026/index.html},
eprinttype = {ECCC},
eprint = {TR00-026},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR00-026.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR00-035,
author = {Nikolai K. Vereshchagin and
Michael V. Vyugin},
title = {Independent minimum length programs to translate between given strings},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR00-035}},
year = {2000},
url = {https://eccc.weizmann.ac.il/eccc-reports/2000/TR00-035/index.html},
eprinttype = {ECCC},
eprint = {TR00-035},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR00-035.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@book{DBLP:books/daglib/0014723,
author = {Lev D. Beklemishev and
Mati Pentus and
Nikolai K. Vereshchagin},
title = {Provability, complexity, grammars},
series = {American Mathematical Society translations series 2},
volume = {192},
publisher = {American Mathematical Society},
year = {1999},
isbn = {978-0-8218-1078-1},
timestamp = {Mon, 22 Jul 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/books/daglib/0014723.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/RazTVV99,
author = {Ran Raz and
G{\'{a}}bor Tardos and
Oleg Verbitsky and
Nikolai K. Vereshchagin},
title = {Arthur-Merlin Games in Boolean Decision Trees},
journal = {J. Comput. Syst. Sci.},
volume = {59},
number = {2},
pages = {346--372},
year = {1999},
url = {https://doi.org/10.1006/jcss.1999.1654},
doi = {10.1006/JCSS.1999.1654},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jcss/RazTVV99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/MuchnikRSV99,
author = {Andrei A. Muchnik and
Andrei E. Romashchenko and
Alexander Shen and
Nikolai K. Vereshchagin},
title = {Upper Semilattice of Binary Strings with the Relation "x is Simple
Conditional to y"},
booktitle = {Proceedings of the 14th Annual {IEEE} Conference on Computational
Complexity, Atlanta, Georgia, USA, May 4-6, 1999},
pages = {114},
publisher = {{IEEE} Computer Society},
year = {1999},
url = {https://doi.org/10.1109/CCC.1999.766270},
doi = {10.1109/CCC.1999.766270},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/MuchnikRSV99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/DurandSV99,
author = {Bruno Durand and
Alexander Shen and
Nikolai K. Vereshchagin},
editor = {Christoph Meinel and
Sophie Tison},
title = {Descriptive Complexity of Computable Sequences},
booktitle = {{STACS} 99, 16th Annual Symposium on Theoretical Aspects of Computer
Science, Trier, Germany, March 4-6, 1999, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {1563},
pages = {153--162},
publisher = {Springer},
year = {1999},
url = {https://doi.org/10.1007/3-540-49116-3\_14},
doi = {10.1007/3-540-49116-3\_14},
timestamp = {Wed, 19 May 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stacs/DurandSV99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR99-014,
author = {Alexander A. Razborov and
Nikolai K. Vereshchagin},
title = {One Property of Cross-Intersecting Families},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR99-014}},
year = {1999},
url = {https://eccc.weizmann.ac.il/eccc-reports/1999/TR99-014/index.html},
eprinttype = {ECCC},
eprint = {TR99-014},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR99-014.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/Vereshchagin98,
author = {Nikolai K. Vereshchagin},
title = {Randomized Boolean Decision Trees: Several Remarks},
journal = {Theor. Comput. Sci.},
volume = {207},
number = {2},
pages = {329--342},
year = {1998},
url = {https://doi.org/10.1016/S0304-3975(98)00071-1},
doi = {10.1016/S0304-3975(98)00071-1},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/Vereshchagin98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/RazTVV98,
author = {Ran Raz and
G{\'{a}}bor Tardos and
Oleg Verbitsky and
Nikolai K. Vereshchagin},
title = {Arthur-Merlin Games in Boolean Decision Trees},
booktitle = {Proceedings of the 13th Annual {IEEE} Conference on Computational
Complexity, Buffalo, New York, USA, June 15-18, 1998},
pages = {58--67},
publisher = {{IEEE} Computer Society},
year = {1998},
url = {https://doi.org/10.1109/CCC.1998.694591},
doi = {10.1109/CCC.1998.694591},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/coco/RazTVV98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/fossacs/PorrotDDV98,
author = {Sylvain Porrot and
Max Dauchet and
Bruno Durand and
Nikolai K. Vereshchagin},
editor = {Maurice Nivat},
title = {Deterministic Rational Transducers and Random Sequences},
booktitle = {Foundations of Software Science and Computation Structure, First International
Conference, FoSSaCS'98, Held as Part of the European Joint Conferences
on the Theory and Practice of Software, ETAPS'98, Lisbon, Portugal,
March 28 - April 4, 1998, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {1378},
pages = {258--272},
publisher = {Springer},
year = {1998},
url = {https://doi.org/10.1007/BFb0053555},
doi = {10.1007/BFB0053555},
timestamp = {Wed, 19 May 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/fossacs/PorrotDDV98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/HammerRSV97,
author = {Daniel Hammer and
Andrei E. Romashchenko and
Alexander Shen and
Nikolai K. Vereshchagin},
title = {Inequalities for Shannon entropies and Kolmogorov complexities},
booktitle = {Proceedings of the Twelfth Annual {IEEE} Conference on Computational
Complexity, Ulm, Germany, June 24-27, 1997},
pages = {13--23},
publisher = {{IEEE} Computer Society},
year = {1997},
url = {https://doi.org/10.1109/CCC.1997.612296},
doi = {10.1109/CCC.1997.612296},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/HammerRSV97.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR97-054,
author = {Ran Raz and
G{\'{a}}bor Tardos and
Oleg Verbitsky and
Nikolai K. Vereshchagin},
title = {Arthur-Merlin Games in Boolean Decision Trees},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR97-054}},
year = {1997},
url = {https://eccc.weizmann.ac.il/eccc-reports/1997/TR97-054/index.html},
eprinttype = {ECCC},
eprint = {TR97-054},
timestamp = {Thu, 13 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR97-054.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/MuchnikV96,
author = {Andrei A. Muchnik and
Nikolai K. Vereshchagin},
title = {A General Method to Construct Oracles Realizing Given Relationships
Between Complexity Classes},
journal = {Theor. Comput. Sci.},
volume = {157},
number = {2},
pages = {227--258},
year = {1996},
url = {https://doi.org/10.1016/0304-3975(95)00161-1},
doi = {10.1016/0304-3975(95)00161-1},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/MuchnikV96.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/MitinaV95,
author = {Olga Mitina and
Nikolai K. Vereshchagin},
editor = {Wolfgang Maass},
title = {How to Use Expert Advice in the Case when Actual Values of Estimated
Events Remain Unknown},
booktitle = {Proceedings of the Eigth Annual Conference on Computational Learning
Theory, {COLT} 1995, Santa Cruz, California, USA, July 5-8, 1995},
pages = {91--97},
publisher = {{ACM}},
year = {1995},
url = {https://doi.org/10.1145/225298.225309},
doi = {10.1145/225298.225309},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/colt/MitinaV95.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/istcs/Vereshchagin95,
author = {Nikolai K. Vereshchagin},
title = {NP-sets are Co-NP-immune Relative to a Random Oracle},
booktitle = {Third Israel Symposium on Theory of Computing and Systems, {ISTCS}
1995, Tel Aviv, Israel, January 4-6, 1995, Proceedings},
pages = {40--45},
publisher = {{IEEE} Computer Society},
year = {1995},
url = {https://doi.org/10.1109/ISTCS.1995.377048},
doi = {10.1109/ISTCS.1995.377048},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/istcs/Vereshchagin95.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/istcs/Vereshchagin95a,
author = {Nikolai K. Vereshchagin},
title = {Lower Bounds for Perceptrons Solving some Separation Problems and
Oracle Separation of {AM} from {PP}},
booktitle = {Third Israel Symposium on Theory of Computing and Systems, {ISTCS}
1995, Tel Aviv, Israel, January 4-6, 1995, Proceedings},
pages = {46--51},
publisher = {{IEEE} Computer Society},
year = {1995},
url = {https://doi.org/10.1109/ISTCS.1995.377047},
doi = {10.1109/ISTCS.1995.377047},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/istcs/Vereshchagin95a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ijfcs/HemaspaandraJV93,
author = {Lane A. Hemaspaandra and
Sanjay Jain and
Nikolai K. Vereshchagin},
title = {Banishing Robust Turing Completeness},
journal = {Int. J. Found. Comput. Sci.},
volume = {4},
number = {3},
pages = {245--265},
year = {1993},
url = {https://doi.org/10.1142/S012905419300016X},
doi = {10.1142/S012905419300016X},
timestamp = {Mon, 16 Sep 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ijfcs/HemaspaandraJV93.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/Vereshchagin93,
author = {Nikolai K. Vereshchagin},
title = {Relationships between NP-sets, Co-NP-sets, and P-sets relative to
random oracles},
booktitle = {Proceedings of the Eigth Annual Structure in Complexity Theory Conference,
San Diego, CA, USA, May 18-21, 1993},
pages = {132--138},
publisher = {{IEEE} Computer Society},
year = {1993},
url = {https://doi.org/10.1109/SCT.1993.336533},
doi = {10.1109/SCT.1993.336533},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/Vereshchagin93.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/Vereshchagin92,
author = {Nikolai K. Vereshchagin},
title = {On The Power of {PP}},
booktitle = {Proceedings of the Seventh Annual Structure in Complexity Theory Conference,
Boston, Massachusetts, USA, June 22-25, 1992},
pages = {138--143},
publisher = {{IEEE} Computer Society},
year = {1992},
url = {https://doi.org/10.1109/SCT.1992.215389},
doi = {10.1109/SCT.1992.215389},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/Vereshchagin92.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/lfcs/HemachandraJV92,
author = {Lane A. Hemachandra and
Sanjay Jain and
Nikolai K. Vereshchagin},
editor = {Anil Nerode and
Michael A. Taitslin},
title = {Banishing Robust Turing Completeness},
booktitle = {Logical Foundations of Computer Science - Tver '92, Second International
Symposium, Tver, Russia, July 20-24, 1992, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {620},
pages = {186--197},
publisher = {Springer},
year = {1992},
url = {https://doi.org/10.1007/BFb0023873},
doi = {10.1007/BFB0023873},
timestamp = {Mon, 16 Sep 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/lfcs/HemachandraJV92.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
a service of 
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2023-10-02 01:00 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
