Alexander A Rubtsov

Research Fellow:Faculty of Computer Science / Big Data and Information Retrieval School / Laboratory of Theoretical Computer Science

Alexander A Rubtsov has been at HSE University since 2014.

Education and Degrees

2016
Candidate of Sciences* (PhD)
2016
Doctoral programme in Discrete mathematics and mathematical cybernetics
Moscow Institute of Physics and Technology, Department of control and applied mathematics
2011
Bachelor's in Applied Mathematics and Physics
Moscow Institute of Physics and Technology

* Candidate of Sciences
According to the International Standard Classification of Education (ISCED) 2011, Candidate of Sciences belongs to ISCED level 8 - "doctoral or equivalent", together with PhD, DPhil, D.Lit, D.Sc, LL.D, Doctorate or similar. Candidate of Sciences allows its holders to reach the level of the Associate Professor.

Professional Interests

Computational Complexity Formal languages automata theory Kolmogorov complexity

Young Faculty Support Program (Group of Young Academic Professionals)
Category "New Researchers" (2017-2018)

Student Term / Thesis Papers

Bachelor
N. Chudinov, Investigation of Parsing Expression Grammars. Faculty of Computer Science, 2019

Full list of of student term / thesis papers

Courses (2019/2020)

Discrete Mathematics (Bachelor’s programme; Faculty of Computer Science; 1 year, 1-3 module)Rus
Past Courses

Courses (2018/2019)

Additional Chapters of Linear Algebra (Optional course (faculty); Faculty of Computer Science; 3, 4 module)Rus
Discrete Mathematics (Bachelor’s programme; Faculty of Computer Science; 1 year, 1-3 module)Eng
Discrete Mathematics (Bachelor’s programme; Faculty of Computer Science; 1 year, 1-3 module)Rus

Courses (2017/2018)

Discrete Mathematics (Bachelor’s programme; Faculty of Computer Science; 1 year, 1-3 module)Rus

Grants

RFBR grant 17–51-10005 (joint project with Royal society)
RFBR grant 16–01–00362
RFBR grant 14–01–00641

Conferences

2018
The 13th International Computer Science Symposium in Russia (Москва). Presentation: On Emptiness and Membership Problems for Set Automata
The 22nd International Conference on Developments in Language Theory (Токио). Presentation: A Structural Lemma for Deterministic Context-Free Languages
2017
21st International Conference on Developments in Language Theory (Льеж). Presentation: On computational complexity of Set Automata
2015
Descriptional Complexity of Formal Systems (Waterloo). Presentation: Regular realizability problems and context-free languages

Publications

2021¹

Chapter Rubtsov A. A. A Linear-Time Simulation of Deterministic d-Limited Automata, in: Developments in Language Theory: 25th International Conference, DLT 2021, Porto, Portugal, August 16–20, 2021, Proceedings. Switzerland : Springer, 2021. doi P. 342-354. doi

2018²

Chapter Rubtsov A. A. A Structural Lemma for Deterministic Context-Free Languages, in: Developments in Language Theory 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings. Cham : Springer, 2018. doi P. 553-565. doi
Chapter Rubtsov A. A., Vyalyi M. On Emptiness and Membership Problems for Set Automata, in: Computer Science – Theory and Applications 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018, Proceedings / Ed. by F. V. Fomin, V. V. Podolskii. Vol. 10846. Springer, 2018. doi P. 295-307. doi

2017¹

Chapter Rubtsov A. A., Vyalyi M. On Computational Complexity of Set Automata, in: Developments in Language Theory 21st International Conference, DLT 2017, Liège, Belgium, August 7-11, 2017, Proceedings. Cham : Springer, 2017. doi P. 332-344. doi

2015¹

Chapter Rubtsov A. A., Vyalyi M. Regular Realizability Problems and Context- Free Languages, in: Descriptional Complexity of Formal Systems Vol. 9118. Switzerland : Springer, 2015. doi P. 256-267.

2014¹

Chapter Рубцов А. А. Исследование задачи регулярной реализуемости для контекстно-свободных языков. // В кн.: Проблемы теоретической кибернетики. Материалы XVII международной конференции. Каз. : Отечество, 2014. С. 246-248.

2012¹

Article Вялый М. Н., Рубцов А. А. Алгоритмическая разрешимость задач о поведении автоматов на сверхсловах // Дискретный анализ и исследование операций. 2012

Feb

2018

Laboratory of Theoretical Computer Science Researchers Get Grant from RFBR and Royal Society

Researchers from the HSE Laboratory of Theoretical Computer Science have won a competition organized by the Russian Foundation for Basic Research (RFBR) and the Royal Society of London for Improving Natural Knowledge.

Jun

2016

Computer Science Faculty Staff Attend Symposium in Russia

On June 9-13, the international conference ‘Computer Science Symposium in Russia 2016’ was held in St. Petersburg as part of the Special Semester on Computational and Proof Complexity.