Surveys, reviews, lecture scripts etc.

This page basically consists of various writings without original research contributions.

He who loves practice without theory is like the sailor who boards ship without a rudder and compass and never knows where he may cast.

Leonardo da Vinci (1452-1519)

Propositional Proof Complexity, in Proceedings of the 8th European Congress of Mathematics, 439-464, 2023.

On the work by Lovasz and Wigderson (in Russian), 2021.

Questions in algebra and mathematical logic. Scientific heritage of S. I. Adian, joint with V. S. Atabekyan, L. D. Beklemishev, V. S. Guba, I. G. Lysionok, A. L Semenov, in Uspekhi Matematicheskikh nauk, 76(1):3-30, 2021. English translation.

Sensitivity of Boolean Functions (in Russian), in Kvant, 2020, No 10, pages 7-16.

Proof Complexity and Beyond, SIGACT News , 47(2):66-86, 2016.

Complexity Theory (in Russian), in the book "Mathematical Component", 2020.

Algebraic Complexity (in Russian), in the series "Modern mathematics: summer school", 2016.

On the reform of the Russian Academy of Sciences (in Russian).

What is a Flag Algebra?, Notices of the AMS, 60(10): 1324-1327, 2013.

Flag Algebras: an Interim Report, in the volume Mathematics of Paul Erdos II, 2013.

Lecture notes of the Course on Quantum Computing.

A foreword to the special issue of Computational Complexity devoted to the memory of Misha Alekhnovich, joint with Allan Borodin and Toniann Pitassi.

Communication Complexity, in the book An Invitation to Mathematics: from Competitions to Research, 2011.

A report on Jakob Nordstrom's work, written with Johann Makowsky in connection with the EACSL Ackermann Award 2009.

Lecture notes of the Course on Propositional Proof Complexity.

Michael Alekhnovich, obituary, SIGACT News, 38(1):70-71, 2007.

Sergei Ivanovich Adian (on his 75th birthday), joint with L. D. Beklemishev, I. G. Lysionok, S. P. Novikov, M. R. Pentus, A. L. Semenov, V. A. Uspenskii, in Uspekhi Matematicheskikh nauk, 61(3):179–191, 2006. English translation in Russian Mathematical Surveys, 61(3):575-588, 2006.

On the scientific contributions of B.A. Subbotovskaya (Russian), Matematicheskoe Prosveshchenie, ser. 3, Vol. 9, 2005, pages 12-15.

Feasible Proofs and Computations: Partnership and Fusion, in Proceedings of the 31st ICALP, Lecture Notes in Computer Science, vol. 3142, 2004, pages 8-14 and Proceedings of the 19th LICS, 2004, pages 134-138.

Propositional Proof Complexity, in Journal of the ACM, Vol. 50, No 1, 2003, pages 80-82. © Association for Computing Machinery

Proof Complexity of Pigeonhole Principles, in Proceedings of the 5th DLT, Lecture Notes in Computer Science, vol. 2295, 2002, pages 100-116. © Springer-Verlag

Complexity of Propositional Proofs, extended abstract of the talk given at the 5th Developments In Language Theory Conference (Vienna, 2001).

Theoretical Computer Science: a mathematician's look (Russian), full version of an essay written for Computerra.

P vs. NP or Perebor Problem: look from 90th (Russian), in the collection Mathematical Events of the XXth Century, 2003, pages 399-418.

Review on the book Proof Complexity and Feasible Arithmetics, Journal of Symbolic Logic.

On Computational Complexity (Russian), script of a highly introductory lecture, Matematicheskoe Prosveshchenie, ser. 3, volume 3, pages 127-141.
English translation is available in Surveys in Modern Mathematics, London Mathematical Society Lecture Note Series, No. 321, pages 186-202.

A brief commentary to A.A.Markov's work on the complexity of Boolean functions (Russian), written for the collection of Markov's selected papers.

Contribution to the Complexity column in the 100th issue of SIGACT News.

Lower bounds for propositional proofs and independence results in Bounded Arithmetic, in Proceedings of the 23rd ICALP, Lecture Notes in Computer Science, vol. 1099, 1996, 48-62.

On Systems of Equations in Free Groups, in Combinatorial and Geometric Group Theory, Edinburgh 1993. London Mathematical Society Lecture Note Series, 204, Cambridge University Press, 1994, 269-283.

On Small Depth Threshold Circuits, in Proceedings of the SWAT 92, Lecture Notes in Computer Science, vol. 621, 1992, 42-52.

Lower Bounds for Deterministic and Nondeterministic Branching Programs, in Proceedings of the 8th FCT, Lecture Notes in Computer Science, vol. 529, 1991, 47-60.

Kolmogorov and the Complexity of Algorithms (contribution to A.N.Kolmogorov's obituary), in Bull. of the London Math. Soc., 22:79-82, 1990. Chiwriter source in Russian (with this, and some good luck, you can at least view it on the screen).

Upper and lower bounds for nilpotency classes of Lie algebras with Engel conditions, joint with S. I. Adian and N. N. Repin, in Group Theory, Proceedings of the Singapore Group Theory Conference held at the National University of Singapore on June 8-19,1987, Walter de Gruyter, 1989, 57-75. Chiwriter source.

Lower Bounds for Monotone Complexity of Boolean Functions, in Proceedings of the International Congress of Mathematicians, 1986, Berkeley, California, USA, vol. 2, 1478-1487. English translation in Amer. Math. Soc. Transl., 147(2):75-84, 1990.