Vereshchagin Nikolay Konstantinovich

Publications in Math-Net.Ru

1. Half-duplex communication complexity with adversary can be less than the classical communication complexity
   
   Mat. Sb., 216:6 (2025),  3–45
2. Chair of Mathematical Logic and Theory of Algorithms
   
   Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2025, no. 1,  23–32
3. Kolmogorov’s last discovery? (Kolmogorov and algorithmic statistics)
   
   Teor. Veroyatnost. i Primenen., 68:4 (2023),  719–750
4. On joint conditional complexity (entropy)
   
   Trudy Mat. Inst. Steklova, 274 (2011),  103–118
5. Variants of Realizability for Propositional Formulas and the Logic of Weak Excluded Middle
   
   Trudy Mat. Inst. Steklova, 242 (2003),  77–97
6. Oracle separation of complexity classes and lower bounds for perceptrons solving separation problems
   
   Izv. RAN. Ser. Mat., 59:6 (1995),  3–24
7. Relativizable and nonrelativizable theorems in the polynomial theory of algorithms
   
   Izv. RAN. Ser. Mat., 57:2 (1993),  51–90
8. The relation between $NP$ and co-$NP$ sets with respect to a random oracle
   
   Izv. Vyssh. Uchebn. Zaved. Mat., 1993, no. 3,  31–39
9. New proof of the solvability of the elementary theory of linearly ordered sets
   
   Mat. Zametki, 47:5 (1990),  31–38
10. Effective upper bounds for the number of zeros of a linear recurrence sequence
    
    Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 1986, no. 1,  25–30
11. Occurrence of zero in a linear recursive sequence
    
    Mat. Zametki, 38:2 (1985),  177–189
12. Zeros of linear recursive sequences
    
    Dokl. Akad. Nauk SSSR, 278:5 (1984),  1036–1039