Arrow Research search

Author name cluster

Gabriel Nivasch

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers
2 author rows

Possible papers

5

TCS Journal 2025 Journal Article

A convergence technique for the game i -MARK

  • Gabriel Nivasch
  • Oz Rubinstein

The game of i -MARK is an impartial combinatorial game introduced by Sopena (2016). The game is parametrized by two sets of positive integers S, D, where min D ≥ 2. From position n ≥ 0 one can move to any position n − s, s ∈ S, as long as n − s ≥ 0, as well as to any position n / d, d ∈ D, as long as n > 0 and d divides n. The game ends when no more moves are possible, and the last player to move is the winner. Sopena, and subsequently Friman and Nivasch (2021), characterized the Sprague–Grundy sequences of many cases of i -MARK ( S, D ) with | D | = 1. Friman and Nivasch also obtained some partial results for the case i -MARK ( { 1 }, { 2, 3 } ). In this paper we present a convergence technique that gives polynomial-time algorithms for the Sprague–Grundy sequence of many instances of i -MARK with | D | > 1. In particular, we prove our technique works for all games i -MARK ( { 1 }, { d 1, d 2 } ).

Details DOI

TCS Journal 2021 Journal Article

Some i-Mark games

  • Oren Friman
  • Gabriel Nivasch

Let S be a set of positive integers, and let D be a set of integers larger than 1. The game Image 1 is an impartial combinatorial game introduced by Sopena (2016), which is played with a single pile of tokens. In each turn, a player can subtract s ∈ S from the pile, or divide the size of the pile by d ∈ D, if the pile size is divisible by d. Sopena partially analyzed the games with S = [ 1, t − 1 ] and D = { d } for d ≢ 1 ( mod t ), but left the case d ≡ 1 ( mod t ) open. We solve this problem by calculating the Sprague–Grundy function of Image 2 for d ≡ 1 ( mod t ), for all t, d ≥ 2. We also calculate the Sprague–Grundy function of Image 3 for all k, and show that it exhibits similar behavior. Finally, following Sopena's suggestion to look at games with | D | > 1, we derive some partial results for the game Image 4, whose Sprague–Grundy function seems to behave erratically and does not show any clear pattern. We prove that each value 0, 1, 2 occurs infinitely often in its SG sequence, with a maximum gap length between consecutive appearances.

Details DOI

NeurIPS Conference 2018 Conference Paper

Learning convex polytopes with margin

  • Lee-Ad Gottlieb
  • Eran Kaufman
  • Aryeh Kontorovich
  • Gabriel Nivasch

We present improved algorithm for properly learning convex polytopes in the realizable PAC setting from data with a margin. Our learning algorithm constructs a consistent polytope as an intersection of about t log t halfspaces with margins in time polynomial in t (where t is the number of halfspaces forming an optimal polytope). We also identify distinct generalizations of the notion of margin from hyperplanes to polytopes and investigate how they relate geometrically; this result may be of interest beyond the learning setting.

PDF Details
v2026.09.13