• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Book chapter
  • Computational hardness of multidimensional subtraction games
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • More
Subject
News
June 19, 2026
HSE Researchers Determine Which Internet Users Are More Likely to Fact-Check
Researchers at HSE University examined the strategies employed by Russian internet users to verify unreliable information and the factors that motivate them to do so. The study found that more than half of users who encounter potentially false information online attempt to verify it by locating the original source. The likelihood of fact-checking is influenced by several factors, including age, place of residence, social status, information literacy skills, and the use of AI. The findings have been published in Monitoring of Public Opinion: Economic and Social Changes.
June 5, 2026
'Im Used to Producing Distilled Knowledge'
Ivan Rubachev works in a HSE University laboratory established jointly with Yandex Research, where he focuses on machine learning with tabular data. In this interview with the HSE Young Scientists project, he discusses why following a vibe can be better than goal-setting, explains the concept of the Neural Turing Machine, and argues why withholding scientific knowledge is counterproductive.
June 17, 2026
Population Lifespan Is Governed by Mathematical Laws
Researchers at HSE University and MSU have established a universal law governing the time to extinction of a population in a random environment. Their analysis of the evolution of branching processes—complex probabilistic systems—shows that, regardless of the initial population size, extinction follows strict mathematical laws. The results have been published in the Journal of Applied Probability.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

Computational hardness of multidimensional subtraction games

P. 237–249.
Gurvich V., Vyalyi M.

We study the algorithmic complexity of solving subtraction games in a fixed dimension with a finite difference set. We prove that there exists a game in this class such that solving the game is (formula presented)-complete and requires time (formula presented), where n is the input size. This bound is optimal up to a polynomial speed-up. The results are based on the construction introduced by Larsson and Wästlund. It relates subtraction games and cellular automata. © Springer Nature Switzerland AG 2020.

Language: English
Full text
DOI
Text on another site
Keywords: cellular automataComputational hardnessSubtraction games
Publication based on the results of:
Mathematical methods in computational complexity theory and algorithm game theory (2020)

In book

Computer Science – Theory and Applications 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020, Proceedings
Vol. 12159. , Springer, 2020.
Similar publications
SimDB in Action: Road Traffic Simulations Completely Inside Array DBMS
Rodriges Zalipynis R. A., PROCEEDINGS OF THE VLDB ENDOWMENT 2022 Vol. 15 No. 12 P. 3742–3745
Array DBMSs operate on big N-d arrays. Cellular automata (CA) work on a discrete lattice of cells, essentially on N-d arrays. CA facilitate decision support as they realistically simulate complex phenomena including road traffic, fire spread, and urban growth. Array DBMSs can bring numerous benefits to the CA domain via a ``database approach'': powerful parallelization, ...
Added: August 30, 2022
Detection of Early Warning Signals for Self-organized Criticality in Cellular Automata
Dmitriev A., Kazmina A., Dmitriev V. et al., , in: 14th Chaotic Modeling and Simulation International Conference.: Springer, 2022. P. 121–133.
Added: July 13, 2022
Convergence of Array DBMS and Cellular Automata: A Road Traffic Simulation Case
Rodriges Zalipynis R. A., , in: SIGMOD/PODS '21: Proceedings of the 2021 International Conference on Management of Data.: NY: ACM, 2021. P. 2399–2403.
Array DBMSs manage big N-d arrays, are not yet widely known, but are experiencing an R&D surge due to the rapid growth of array volumes. Cellular automata (CA) operate on a discrete lattice of cells that can be modeled by an N-d array. CA are successfully applied to model fire spread, land cover change, road ...
Added: April 28, 2021
The Algorithm of Continuous Optimization Based on the Modified Cellular Automaton
Evsyutin O., Шелупанов А. А., Мещеряков Р. В. et al., Symmetry 2016 Vol. 8 No. 9 P. 1–18
This article is devoted to the application of the cellular automata mathematical apparatus to the problem of continuous optimization. The cellular automaton with an objective function is introduced as a new modification of the classic cellular automaton. The algorithm of continuous optimization, which is based on dynamics of the cellular automaton having the property of ...
Added: September 5, 2019
Моделирование трехуровневой системы «власть-общество» на основе клеточных автоматов
А.П.Петров, М.Е. Степанцов, Математическое моделирование 2016 Т. 28 № 3 С. 119–132
Настоящая  работа  посвящена  построению  и  первичному  исследованию  варианта  модели «власть-общество» на основе стохастического клеточного автомата, описывающего динамику распределения власти в иерархии. Сформулированы лежащие в основе модели положения, проведена алгоритмизация и построена имитационная система, позволяющая проводить  вычислительные  эксперименты  с  моделью.  Показано,  что  большая  часть  свойств детерминированной модели, имеющей вид системы дифференциальных уравнений, сохраняется в клеточно-автоматном варианте. ...
Added: October 12, 2017
Forecasting of Snow Cover Melting Rates in Perm Region Based on the Results of Satelite Monitoring Using Cellular Automata Method
Pyankov S., Shihov A., Rusakov S. V., , in: Proceeding of the 14 International Multidisciplinary Scientific Geoconference SGEM 2014, Albena,Bulgaria, 17-26 June, 2014Vol. 1.: Albena: [б.и.], 2014. P. 601–606.
The paper presents problems, which are connected with satellite monitoring of snowmelt process in the Perm region. It is represented research data of 2011, according to which almost every day only a small part of the observed territory can be identified due to the effect of clouds. It is proposed the algorithm, based on cellular ...
Added: April 8, 2015
Дискретная распределенная модификация модели «власть–общество» на основе клеточного автомата
Петров А. П., Stepantsov M. E., / Институт прикладной математики им. М.В. Келдыша Российской академии наук. 2014. № 100.
In this paper we consider construction and primary research of the stochastic cellular automaton based version of the "power-society" model, describing the dynamics of power distribution in a hierarchy. We herein formulate basic principles of the model and present a simulation system for numeric experiments. It is shown that most properties of the deterministic model ...
Added: December 17, 2014
Методы прогнозирования и модели распространения заболеваний
Kondratyev M., Компьютерные исследования и моделирование 2013 Т. 5 № 5 С. 863–882
The number of papers addressing the forecasting of the infectious disease morbidity is rapidly growing due to accumulation of available statistical data. This article surveys the major approaches for the short-term and the long-term morbidity forecasting. Their limitations and the practical application possibilities are pointed out. The paper presents the conventional time series analysis methods ...
Added: January 13, 2014
Towards Cellular Automata Football Models with Mentality Accounting
Makarenko A., Krushinsky D., Musienko A. et al., , in: Cellular Automata. 9th International Conference on Cellular Automata for Research and Industry, ACRI 2010, Ascoli Piceno, Italy, September 21-24, 2010. Proceedings.: Без места: [б.и.], 2010. P. 149–152.
In this paper we deal with mathematical modeling of team sport games based on cellular automata (CA). We describe some developments of CA models of football. Presumable learning and optimization problems in team modeling based on CA are discussed. Some general problems are discussed which are related to the accounting of mentality of game participants. ...
Added: July 27, 2012
Cellular Automata. 9th International Conference on Cellular Automata for Research and Industry, ACRI 2010, Ascoli Piceno, Italy, September 21-24, 2010. Proceedings
Без места: [б.и.], 2010.
This book constitutes the refereed proceedings of the 9th International Conference on Cellular Automata for Research and Industry, ACRI 2010, held in Ascoli Piceno, Italy, in September 2010. The first part of the volume contains 39 revised papers that were carefully reviewed and selected from the main conference; they are organized according to six main ...
Added: July 27, 2012
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit