![](https://dblp.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
default search action
Nikolai K. Vereshchagin
Person information
Refine list
![note](https://dblp.uni-trier.de/img/note-mark.dark.12x12.png)
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2024
- [i40]Mikhail Dektiarev, Nikolay K. Vereshchagin:
Half-duplex communication complexity with adversary can be less than the classical communication complexity. CoRR abs/2405.16881 (2024) - 2023
- [j39]Nikolay K. Vereshchagin
:
Information disclosure in the framework of Kolmogorov complexity. Theor. Comput. Sci. 940(Part): 108-122 (2023) - [i39]Nikolay K. Vereshchagin:
On information content in certain objects. CoRR abs/2307.04530 (2023) - [i38]Mikhail Dektiarev, Nikolai K. Vereshchagin:
Half-duplex communication complexity with adversary? can be less than the classical communication complexity. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [j38]Nikolay K. Vereshchagin
:
A Family of Non-Periodic Tilings of the Plane by Right Golden Triangles. Discret. Comput. Geom. 68(1): 188-217 (2022) - [c41]Nikolai K. Vereshchagin
:
How Much Randomness is Needed to Convert MA Protocols to AM Protocols? CSR 2022: 338-349 - [i37]Nikolay K. Vereshchagin:
How much randomness is needed to convert MA protocols to AM protocols? Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [j37]Harry Buhrman, Matthias Christandl, Michal Koucký
, Zvi Lotker, Boaz Patt-Shamir, Nikolai K. Vereshchagin
:
High Entropy Random Selection Protocols. Algorithmica 83(2): 667-694 (2021) - [j36]Nikolai K. Vereshchagin:
Proofs of conservation inequalities for Levin's notion of mutual information of 1974. Theor. Comput. Sci. 856: 14-20 (2021) - [i36]Nikolay K. Vereshchagin:
Information disclosure in the framework of Kolmogorov complexity. CoRR abs/2108.01685 (2021) - 2020
- [j35]Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin
:
On the Structure of Ammann A2 Tilings. Discret. Comput. Geom. 63(3): 577-606 (2020) - [j34]Nikolay K. Vereshchagin:
Descriptive complexity of computable sequences revisited. Theor. Comput. Sci. 809: 531-537 (2020) - [i35]Nikolay K. Vereshchagin:
A family of non-periodic tilings of the plane by right golden triangles. CoRR abs/2007.10658 (2020)
2010 – 2019
- 2019
- [j33]Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolai K. Vereshchagin
:
Sparse Selfreducible Sets and Nonuniform Lower Bounds. Algorithmica 81(1): 179-200 (2019) - [i34]Nikolay K. Vereshchagin:
Proofs of conservation inequalities for Levin's notion of mutual information of 1974. CoRR abs/1911.05447 (2019) - 2018
- [j32]Bruno Bauwens
, Anton Makhlin, Nikolai K. Vereshchagin, Marius Zimand
:
Short lists with short programs in short time. Comput. Complex. 27(1): 31-61 (2018) - [j31]Tarik Kaced
, Andrei E. Romashchenko
, Nikolai K. Vereshchagin
:
A Conditional Information Inequality and Its Combinatorial Applications. IEEE Trans. Inf. Theory 64(5): 3610-3615 (2018) - 2017
- [j30]Nikolai K. Vereshchagin
:
Short lists with short programs from programs of functions and strings. Theory Comput. Syst. 61(4): 1440-1450 (2017) - [c40]Nikolay K. Vereshchagin, Alexander Shen
:
Algorithmic Statistics: Forty Years Later. Computability and Complexity 2017: 669-737 - [c39]Alexey Milovanov, Nikolay K. Vereshchagin:
Stochasticity in Algorithmic Statistics for Polynomial Time. CCC 2017: 17:1-17:18 - [i33]Alexey Milovanov, Nikolai K. Vereshchagin:
Stochasticity in Algorithmic Statistics for Polynomial Time. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j29]Joshua Brody, Harry Buhrman, Michal Koucký
, Bruno Loff
, Florian Speelman
, Nikolai K. Vereshchagin
:
Towards a Reverse Newman's Theorem in Interactive Information Complexity. Algorithmica 76(3): 749-781 (2016) - [j28]Nikolay K. Vereshchagin
:
Algorithmic Minimal Sufficient Statistics: a New Approach. Theory Comput. Syst. 58(3): 463-481 (2016) - [i32]Nikolai K. Vereshchagin, Alexander Shen:
Algorithmic statistics: forty years later. CoRR abs/1607.08077 (2016) - 2015
- [i31]Tarik Kaced, Andrei E. Romashchenko, Nikolay K. Vereshchagin:
Conditional Information Inequalities and Combinatorial Applications. CoRR abs/1501.04867 (2015) - [i30]Nikolai K. Vereshchagin, Alexander Shen:
Algorithmic statistics revisited. CoRR abs/1504.04950 (2015) - 2014
- [j27]Nikolay K. Vereshchagin
:
Encoding Invariance in Average Case Complexity. Theory Comput. Syst. 54(2): 305-317 (2014) - [j26]Nikolay K. Vereshchagin
:
Editorial. Theory Comput. Syst. 55(2): 279-280 (2014) - [c38]Nikolay K. Vereshchagin:
Randomized Communication Complexity of Approximating Kolmogorov Complexity. CSR 2014: 365-374 - [c37]Nikolay K. Vereshchagin:
Aperiodic Tilings by Right Triangles. DCFS 2014: 29-41 - [e2]Edward A. Hirsch, Sergei O. Kuznetsov, Jean-Éric Pin, Nikolay K. Vereshchagin:
Computer Science - Theory and Applications - 9th International Computer Science Symposium in Russia, CSR 2014, Moscow, Russia, June 7-11, 2014. Proceedings. Lecture Notes in Computer Science 8476, Springer 2014, ISBN 978-3-319-06685-1 [contents] - 2013
- [c36]Nikolay K. Vereshchagin:
On Algorithmic Strong Sufficient Statistics. CiE 2013: 424-433 - [c35]Joshua Brody, Harry Buhrman, Michal Koucký
, Bruno Loff
, Florian Speelman
, Nikolay K. Vereshchagin
:
Towards a Reverse Newman's Theorem in Interactive Information Complexity. CCC 2013: 24-33 - [c34]Bruno Bauwens
, Anton Makhlin, Nikolay K. Vereshchagin
, Marius Zimand
:
Short Lists with Short Programs in Short Time. CCC 2013: 98-108 - [c33]Nikolay K. Vereshchagin:
Improving on Gutfreund, Shaltiel, and Ta-Shma's Paper "If NP Languages Are Hard on the Worst-Case, Then It Is Easy to Find Their Hard Instances". CSR 2013: 203-211 - [i29]Bruno Bauwens, Anton Makhlin, Nikolay K. Vereshchagin, Marius Zimand:
Short lists with short programs in short time. CoRR abs/1301.1547 (2013) - [i28]Bruno Bauwens, Anton Makhlin, Nikolay K. Vereshchagin, Marius Zimand:
Short lists with short programs in short time. Electron. Colloquium Comput. Complex. TR13 (2013) - [i27]Nikolay K. Vereshchagin:
Randomized communication complexity of appropximating Kolmogorov complexity. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [i26]Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin:
Limit complexities revisited [once more]. CoRR abs/1204.0201 (2012) - 2011
- [e1]Alexander S. Kulikov, Nikolay K. Vereshchagin:
Computer Science - Theory and Applications - 6th International Computer Science Symposium in Russia, CSR 2011, St. Petersburg, Russia, June 14-18, 2011. Proceedings. Lecture Notes in Computer Science 6651, Springer 2011, ISBN 978-3-642-20711-2 [contents] - [i25]Nikolay K. Vereshchagin:
Improving on Gutfreund, Shaltiel, and Ta-Shma's paper "If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances". Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [j25]Ilya Mezhirov, Nikolay K. Vereshchagin
:
On abstract resource semantics and computability logic. J. Comput. Syst. Sci. 76(5): 356-372 (2010) - [j24]Harry Buhrman, Lance Fortnow, Michal Koucký
, John D. Rogers, Nikolai K. Vereshchagin
:
Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible? Theory Comput. Syst. 46(1): 143-156 (2010) - [j23]Laurent Bienvenu, Andrej Muchnik, Alexander Shen
, Nikolai K. Vereshchagin
:
Limit Complexities Revisited. Theory Comput. Syst. 47(3): 720-736 (2010) - [j22]Nikolai K. Vereshchagin
, Paul M. B. Vitányi:
Rate distortion and denoising of individual data using Kolmogorov complexity. IEEE Trans. Inf. Theory 56(7): 3438-3454 (2010) - [c32]Nikolay K. Vereshchagin:
An Encoding Invariant Version of Polynomial Time Computable Distributions. CSR 2010: 371-383 - [i24]Andrej Muchnik, Ilya Mezhirov, Alexander Shen, Nikolai K. Vereshchagin:
Game interpretation of Kolmogorov complexity. CoRR abs/1003.4712 (2010) - [i23]Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolai K. Vereshchagin:
Sparse Selfreducible Sets and Nonuniform Lower Bounds. Electron. Colloquium Comput. Complex. TR10 (2010) - [i22]Nikolay K. Vereshchagin:
Algorithmic Minimal Sufficient Statistics: a New Definition. Electron. Colloquium Comput. Complex. TR10 (2010) - [i21]Nikolay K. Vereshchagin:
An Encoding Invariant Version of Polynomial Time Computable Distributions. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [c31]Nikolay K. Vereshchagin:
Algorithmic Minimal Sufficient Statistic Revisited. CiE 2009: 478-487 - [c30]Nikolay K. Vereshchagin:
Kolmogorov Complexity and Model Selection. CSR 2009: 19-24 - 2008
- [j21]Nikolay K. Vereshchagin:
Kolmogorov Complexity and Games. Bull. EATCS 94: 43-75 (2008) - [c29]Alexey V. Chernov
, Alexander Shen
, Nikolai K. Vereshchagin, Vladimir Vovk
:
On-Line Probability, Complexity and Randomness. ALT 2008: 138-153 - [c28]Harry Buhrman, Michal Koucký
, Nikolai K. Vereshchagin
:
Randomised Individual Communication Complexity. CCC 2008: 321-331 - [c27]Ilya Mezhirov, Nikolai K. Vereshchagin
:
On Game Semantics of the Affine and Intuitionistic Logics. WoLLIC 2008: 28-42 - [i20]Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin:
Limit complexities revisited. CoRR abs/0802.2833 (2008) - 2007
- [j20]Noga Alon, Ilan Newman, Alexander Shen
, Gábor Tardos
, Nikolai K. Vereshchagin
:
Partitioning multi-dimensional sets in a small number of "uniform" parts. Eur. J. Comb. 28(1): 134-144 (2007) - [j19]Nikolai K. Vereshchagin
:
Kolmogorov complexity of enumerating finite sets. Inf. Process. Lett. 103(1): 34-39 (2007) - [j18]Harry Buhrman, Hartmut Klauck
, Nikolai K. Vereshchagin
, Paul M. B. Vitányi:
Individual communication complexity. J. Comput. Syst. Sci. 73(6): 973-985 (2007) - [j17]Andrej Muchnik, Alexander Shen
, Mikhail Ustinov, Nikolai K. Vereshchagin
, Michael V. Vyugin:
Non-reducible descriptions for conditional Kolmogorov complexity. Theor. Comput. Sci. 384(1): 77-86 (2007) - [c26]Harry Buhrman, Matthias Christandl, Michal Koucký
, Zvi Lotker, Boaz Patt-Shamir, Nikolai K. Vereshchagin:
High Entropy Random Selection Protocols. APPROX-RANDOM 2007: 366-379 - [c25]Harry Buhrman, Nikolai K. Vereshchagin
, Ronald de Wolf:
On Computation and Communication with Small Bias. CCC 2007: 24-32 - [c24]Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin:
Inverting Onto Functions and Polynomial Hierarchy. CSR 2007: 92-103 - [i19]Nikolai K. Vereshchagin, Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir:
High Entropy Random Selection Protocols. Algebraic Methods in Computational Complexity 2007 - 2006
- [c23]Andrei A. Muchnik, Nikolai K. Vereshchagin:
Shannon Entropy vs. Kolmogorov Complexity. CSR 2006: 281-291 - [c22]Nikolai K. Vereshchagin
, Paul M. B. Vitányi:
On Algorithmic Rate-Distortion Function. ISIT 2006: 798-802 - [c21]Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin:
Kolmogorov Complexity with Error. STACS 2006: 137-148 - [c20]Andrej Muchnik, Alexander Shen
, Nikolai K. Vereshchagin, Michael V. Vyugin:
Non-reducible Descriptions for Conditional Kolmogorov Complexity. TAMC 2006: 308-317 - [i18]Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin:
Inverting onto functions might not be hard. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [c19]Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin:
Increasing Kolmogorov Complexity. STACS 2005: 412-421 - [i17]Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai K. Vereshchagin:
Partitioning multi-dimensional sets in a small number of "uniform" parts. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [j16]Bruno Durand, Nikolai K. Vereshchagin
:
Kolmogorov-Loveland stochasticity for finite strings. Inf. Process. Lett. 91(6): 263-269 (2004) - [j15]Nikolai K. Vereshchagin
, Paul M. B. Vitányi:
Kolmogorov's structure functions and model selection. IEEE Trans. Inf. Theory 50(12): 3265-3290 (2004) - [c18]Bruno Durand, Andrei A. Muchnik, Maxim Ushakov, Nikolai K. Vereshchagin:
Ecological Turing Machines. ICALP 2004: 457-468 - [c17]Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi:
Individual Communication Complexity: Extended Abstract. STACS 2004: 19-30 - [i16]Nikolai K. Vereshchagin, Paul M. B. Vitányi:
A Theory of Lossy Compression for Individual Data. CoRR cs.IT/0411014 (2004) - [i15]Nikolai K. Vereshchagin:
Kolmogorov complexity of enumerating finite sets. Electron. Colloquium Comput. Complex. TR04 (2004) - [i14]Andrei A. Muchnik, Alexander Shen, Nikolai K. Vereshchagin, Michael V. Vyugin:
Non-reducible descriptions for conditional Kolmogorov complexity. Electron. Colloquium Comput. Complex. TR04 (2004) - [i13]Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin:
Kolmogorov Complexity with Error. Electron. Colloquium Comput. Complex. TR04 (2004) - [i12]Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin:
Increasing Kolmogorov Complexity. Electron. Colloquium Comput. Complex. TR04 (2004) - 2003
- [j14]Olga Mitina, Nikolai K. Vereshchagin
:
How to use several noisy channels with unknown error probabilities. Inf. Comput. 184(2): 229-241 (2003) - [j13]Bruno Durand, Vladimir Kanovei
, Vladimir A. Uspensky, Nikolai K. Vereshchagin
:
Do stronger definitions of randomness exist? Theor. Comput. Sci. 290(3): 1987-1996 (2003) - [i11]Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi:
Individual Communication Complexity. CoRR cs.CC/0304012 (2003) - 2002
- [b2]Alexander Shen, Nikolai K. Vereshchagin:
Basic set theory. Student mathematical library 17, American Mathematical Society 2002, ISBN 978-0-8218-2731-4, pp. I-VIII, 1-116 - [j12]Konstantin Makarychev, Yury Makarychev, Andrei E. Romashchenko, Nikolai K. Vereshchagin:
A new class of non-Shannon-type inequalities for entropies. Commun. Inf. Syst. 2(2): 147-166 (2002) - [j11]Bruno Durand, Alexander Shen
, Nikolai K. Vereshchagin
:
Descriptive complexity of computable sequences. Theor. Comput. Sci. 271(1-2): 47-58 (2002) - [j10]Nikolai K. Vereshchagin
:
Kolmogorov complexity conditional to large integers. Theor. Comput. Sci. 271(1-2): 59-67 (2002) - [j9]Alexey V. Chernov
, Andrei A. Muchnik, Andrei E. Romashchenko
, Alexander Shen
, Nikolai K. Vereshchagin
:
Upper semi-lattice of binary strings with the relation "x is simple conditional to y". Theor. Comput. Sci. 271(1-2): 69-95 (2002) - [j8]Andrei E. Romashchenko
, Alexander Shen
, Nikolai K. Vereshchagin
:
Combinatorial interpretation of Kolmogorov complexity. Theor. Comput. Sci. 271(1-2): 111-123 (2002) - [j7]Alexander Shen
, Nikolai K. Vereshchagin
:
Logical operations and Kolmogorov complexity. Theor. Comput. Sci. 271(1-2): 125-129 (2002) - [j6]Nikolai K. Vereshchagin
, Michael V. Vyugin:
Independent minimum length programs to translate between given strings. Theor. Comput. Sci. 271(1-2): 131-143 (2002) - [c16]Alexey V. Chernov, Dmitrij P. Skvortsov, Elena Z. Skvortsova, Nikolai K. Vereshchagin:
Variants of Realizability for Propositional Formulas and the Logic of the Weak Law of Excluded Middle. CSL 2002: 74-88 - [c15]Nikolai K. Vereshchagin, Paul M. B. Vitányi:
Kolmogorov's Structure Functions with an Application to the Foundations of Model Selection. FOCS 2002: 751-760 - [i10]Nikolai K. Vereshchagin, Paul M. B. Vitányi:
Kolmogorov's Structure Functions with an Application to the Foundations of Model Selection. CoRR cs.CC/0204037 (2002) - 2001
- [c14]Andrei A. Muchnik, Nikolai K. Vereshchagin
:
Logical Operations and Kolmogorov Complexity II. CCC 2001: 256-265 - [i9]Nikolai K. Vereshchagin:
An enumerable undecidable set with low prefix complexity: a simplified proof. Electron. Colloquium Comput. Complex. TR01 (2001) - [i8]Nikolai K. Vereshchagin:
Kolmogorov Complexity Conditional to Large Integers. Electron. Colloquium Comput. Complex. TR01 (2001) - [i7]Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin:
Descriptive complexity of computable sequences. Electron. Colloquium Comput. Complex. TR01 (2001) - [i6]Alexander Shen, Nikolai K. Vereshchagin:
Logical operations and Kolmogorov complexity. Electron. Colloquium Comput. Complex. TR01 (2001) - [i5]Andrei A. Muchnik, Nikolai K. Vereshchagin:
Logical operations and Kolmogorov complexity. II. Electron. Colloquium Comput. Complex. TR01 (2001) - 2000
- [j5]Daniel Hammer, Andrei E. Romashchenko
, Alexander Shen
, Nikolai K. Vereshchagin
:
Inequalities for Shannon Entropy and Kolmogorov Complexity. J. Comput. Syst. Sci. 60(2): 442-464 (2000) - [c13]Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
:
Combinatorial Interpretation of Kolmogorov Complexity. CCC 2000: 131-137 - [c12]Nikolai K. Vereshchagin
, Michael V. Vyugin:
Independent Minimum Length Programs to Translate between Given Strings. CCC 2000: 138- - [i4]Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin:
Combinatorial Interpretation of Kolmogorov Complexity. Electron. Colloquium Comput. Complex. TR00 (2000) - [i3]Nikolai K. Vereshchagin, Michael V. Vyugin:
Independent minimum length programs to translate between given strings. Electron. Colloquium Comput. Complex. TR00 (2000)
1990 – 1999
- 1999
- [b1]Lev D. Beklemishev, Mati Pentus, Nikolai K. Vereshchagin:
Provability, complexity, grammars. American Mathematical Society translations series 2 192, American Mathematical Society 1999, ISBN 978-0-8218-1078-1, pp. I-VIII, 1-172 - [j4]Ran Raz
, Gábor Tardos
, Oleg Verbitsky
, Nikolai K. Vereshchagin
:
Arthur-Merlin Games in Boolean Decision Trees. J. Comput. Syst. Sci. 59(2): 346-372 (1999) - [c11]Andrei A. Muchnik, Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin:
Upper Semilattice of Binary Strings with the Relation "x is Simple Conditional to y". CCC 1999: 114- - [c10]Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin:
Descriptive Complexity of Computable Sequences. STACS 1999: 153-162 - [i2]Alexander A. Razborov, Nikolai K. Vereshchagin:
One Property of Cross-Intersecting Families. Electron. Colloquium Comput. Complex. TR99 (1999) - 1998
- [j3]Nikolai K. Vereshchagin
:
Randomized Boolean Decision Trees: Several Remarks. Theor. Comput. Sci. 207(2): 329-342 (1998) - [c9]Ran Raz
, Gábor Tardos
, Oleg Verbitsky, Nikolai K. Vereshchagin:
Arthur-Merlin Games in Boolean Decision Trees. CCC 1998: 58-67 - [c8]Sylvain Porrot, Max Dauchet, Bruno Durand, Nikolai K. Vereshchagin:
Deterministic Rational Transducers and Random Sequences. FoSSaCS 1998: 258-272 - 1997
- [c7]Daniel Hammer, Andrei E. Romashchenko
, Alexander Shen, Nikolai K. Vereshchagin
:
Inequalities for Shannon entropies and Kolmogorov complexities. CCC 1997: 13-23 - [i1]Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin:
Arthur-Merlin Games in Boolean Decision Trees. Electron. Colloquium Comput. Complex. TR97 (1997) - 1996
- [j2]Andrei A. Muchnik, Nikolai K. Vereshchagin
:
A General Method to Construct Oracles Realizing Given Relationships Between Complexity Classes. Theor. Comput. Sci. 157(2): 227-258 (1996) - 1995
- [c6]Olga Mitina, Nikolai K. Vereshchagin:
How to Use Expert Advice in the Case when Actual Values of Estimated Events Remain Unknown. COLT 1995: 91-97 - [c5]Nikolai K. Vereshchagin:
NP-sets are Co-NP-immune Relative to a Random Oracle. ISTCS 1995: 40-45 - [c4]Nikolai K. Vereshchagin:
Lower Bounds for Perceptrons Solving some Separation Problems and Oracle Separation of AM from PP. ISTCS 1995: 46-51 - 1993
- [j1]Lane A. Hemaspaandra
, Sanjay Jain, Nikolai K. Vereshchagin:
Banishing Robust Turing Completeness. Int. J. Found. Comput. Sci. 4(3): 245-265 (1993) - [c3]Nikolai K. Vereshchagin:
Relationships between NP-sets, Co-NP-sets, and P-sets relative to random oracles. SCT 1993: 132-138 - 1992
- [c2]Nikolai K. Vereshchagin:
On The Power of PP. SCT 1992: 138-143 - [c1]Lane A. Hemachandra
, Sanjay Jain, Nikolai K. Vereshchagin
:
Banishing Robust Turing Completeness. LFCS 1992: 186-197
Coauthor Index
![](https://dblp.uni-trier.de/img/cog.dark.24x24.png)
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.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-06-19 21:51 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint