• 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
  • 2028
  • 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
October 1, 2026
HSE Researchers Show How Congenital Motor Disorders Affect Brain Development
Researchers from HSE University’s Institute for Cognitive Neuroscience have synthesised the findings of their previous studies on brain development in children with obstetric brachial plexus palsy and arthrogryposis. Their analysis shows that impaired motor function in early childhood not only limits children’s motor experience but also affects memory, categorical thinking, and information processing. The study has been published in Frontiers in Psychology.
October 1, 2026
Window into the Body: Scientists Develop Neural Network to Detect Risk of 15 Diseases from Retinal Images
Russian universities, with the participation of HSE University, Sber, and Z-union, have developed a neural network that can simultaneously assess the risk of 15 types of pathology from retinal photographs, including not only eye diseases but also cardiovascular conditions. The AI system can help clinicians detect potentially concerning changes at an early stage, identify signs reflecting the condition of retinal blood vessels, and determine whether a patient may need further examination. The paper has been published in Frontiers in Medicine.
September 30, 2026
'We Did Not Limit the Time for Questions'
The International Laboratory for Supercomputer Atomistic Modelling and Multi-Scale Analysis at HSE University held a major conference on molecular dynamics. Participants had the opportunity to attend all the presentations, while speakers were given as much time as they needed to answer questions. The HSE News Service interviewed Grigory Smirnov, Head of the Laboratory, and Genri Norman, Chief Research Fellow, about the conference preparations and the discussions it generated.

 

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