• 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 11, 2026
Doctoral Student at HSE University Reveals Hidden Layout of Ancient Parion
İdil Malgil, a researcher at HSE University, conducted a UAV-based LiDAR survey of the ancient Roman city of Parion in present-day Turkey. The high density of the scans allowed the team to detect subtle terrain features concealed beneath the ground and vegetation. The survey revealed traces of entire neighbourhoods, terraced structures, and walls that had remained invisible during routine excavations and could not be identified through aerial photography. The findings have been published in Ancient Civilizations from Scythia to Siberia.
June 11, 2026
Mathematicians from Nizhny Novgorod and Shanghai Study System Stability
Mathematicians at HSE University–Nizhny Novgorod, in collaboration with colleagues from Tongji University in Shanghai, are investigating the fundamental causes of structural stability in systems and the mechanisms underlying its disruption. In this interview with the HSE News Service, Prof. Olga Pochinka, Head of the International Laboratory of Dynamical Systems and Applications at HSE University–Nizhny Novgorod and leader of the project ‘Qualitative Theory of Systems of Ordinary and Partial Differential Equations,’ discusses the project, which is being implemented as part of HSE University's International Academic Cooperation programme.
June 11, 2026
Neurolinguists Assist in Awake Surgery on 11-Year-Old Patient with Epilepsy
Researchers at the HSE Centre for Language and Brain took part in a rare awake neurosurgical procedure performed on an 11-year-old patient with drug-resistant epilepsy. Working alongside surgeons at the Voyno-Yasenetsky Centre of Specialised Medical Care for Children in Solntsevo, they monitored the resection of a portion of the left temporal lobe, where the epileptic focus had been identified.

 

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