Researcher profile

Vladimir Gurvich

Vladimir Gurvich contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate

Trust snapshot

Quick read

Trust 17 - UnverifiedVerification L1Unclaimed author
4works
0followers
5topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

4 published item(s)

preprint2022arXiv

Supercentenarian paradox

Consider the following statement: $B(t, Δt)$: a $t$ years old person NN will survive another $Δt$ years, where $t, Δt\in \mathbb{R}$ are nonnegative real numbers. We know only that NN is $t$ years old and nothing about the health conditions, gender, race, nationality, etc. We bet that $B(t, Δt)$ holds. It seems that our odds are very good, for any $t$ provided $Δt$ is small enough, say, $1 / 365$ (that is, one day). However, this is not that obvious and depends on the life-time probabilistic distribution. Let $F(t)$ denote the probability to live at most $t$ years and set $Φ(t) = 1 - F(t)$. Clearly, $Φ(t) \rightarrow 0$ as $t \rightarrow \infty$. It is not difficult to verify that $Pr(B(t, Δt)) \rightarrow 0$ as $t \rightarrow \infty$, for any fixed $Δt$, whenever the convergence of $Φ$ is fast enough (say, super-exponential). Statistics provide arguments (based on an extrapolation yet) that this is the case. Hence, for an arbitrarily small positive $Δt $ and $ε$ there exists a sufficiently large $t$ such that $Pr(B(t, Δt)) < ε$, which means that we should not bet... in theory. However, in practice we can bet safely, because for the inequality $Pr(B(t, Δt)) < 1/2$ a very large $t$ is required. For example, $Δt = 1/365$ may require $t > 125$ years for some typical distributions $F$ considered in the literature. Yet, on Earth there is no person of such age. Thus, our odds are good, either because the chosen testee NN is not old enough, or for technical (or, more precisely, statistical) reasons -- absence of a testee. This situation is similar to the famous St.Petersburg Paradox.

preprint2021arXiv

More about Exact Slow $k$-Nim

Given $n$ piles of tokens and a positive integer $k \leq n$, the game Nim$^1_{n, =k}$ of exact slow $k$-Nim is played as follows. Two players move alternately. In each move, a player chooses exactly $k$ non-empty piles and removes one token from each of them. A player whose turn it is to move but has no move loses (if the normal version of the game is played, and wins if it is the misére version). In Integers 20 (2020) 1-19, Gurvich et al gave an explicit formula for the Sprague-Grundy function of Nim$^1_{4, =2}$, for both its normal and misére version. Here we extend this result and obtain an explicit formula for the P-positions of the normal version of Nim$^1_{5, =2}$ and Nim$^1_{6, =2}$.

preprint2020arXiv

Computational Hardness of Multidimensional Subtraction Games

We study 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 any algorithm solving the game runs in exponential time. Also we prove an existence of a game in this class such that solving the game is PSPACE-hard. The results are based on the construction introduced by Larsson and Wästlund. It relates subtraction games and cellular automata.

preprint2020arXiv

On the degree sequences of dual graphs on surfaces

Given two graphs $G$ and $G^*$ with a one-to-one correspondence between their edges, when do $G$ and $G^*$ form a pair of dual graphs realizing the vertices and countries of a map embedded in a surface? A criterion was obtained by Jack Edmonds in 1965. Furthermore, let $\boldsymbol{d}=(d_1,\ldots,d_n)$ and $\boldsymbol{t}=(t_1,\ldots,t_m)$ be their degree sequences. Then, clearly, $\sum_{i=1}^n d_i = \sum_{j=1}^m t_j = 2\ell$, where $\ell$ is the number of edges in each of the two graphs, and $χ= n - \ell + m$ is the Euler characteristic of the surface. Which sequences $\boldsymbol{d}$ and $\boldsymbol{t}$ satisfying these conditions still cannot be realized as the degree sequences? We make use of Edmonds&#39; criterion to obtain several infinite series of exceptions for the sphere, $χ= 2$, and projective plane, $χ= 1$. We conjecture that there exist no exceptions for $χ\leq 0$.