# Publications

25. Lee-Ad Gottlieb, Eran Kaufman, Aryeh Kontorovich, Gabriel Nivasch, and Ofir Pele

**Nested barycentric coordinate system as an explicit feature map** [arXiv:2002.01999]

Preliminary version in Proc. 24th Int. Conf. on A.I. and Stat. (AISTATS), PMLR 130:766-774, 2021.

Full version submitted for publication.

We introduce a new embedding technique based on a barycentric coordinate system. Our embedding can be used to transform the problem of polytope approximation into that of finding a linear classifier in a higher (but nevertheless quite sparse) dimensional representation. It has applications to the problems of approximating separating polytopes, as well as to classification by separating polytopes and piecewise linear regression.

24. Oren Friman and Gabriel Nivasch

**Some ****i****-Mark games** [arXiv:2007.00721]

Theoretical Computer Science, 885:116-124, 2021.

The game *i*-Mark(*S*, *D*) is an impartial combinatorial game introduced by Sopena (2016), played with a pile of tokens. In each turn, a player can either subtract *s* in *S* tokens from the pile, or divide the pile size by *d* in *D* if the pile size is divisible by *d*. We calculate the Sprague-Grundy function of *i*-Mark([1, *t* – 1], {*d*}) for *d* congruent to 1 (mod *t*), solving an open problem of Sopena. We also calculate the SG function of *i*-Mark({2}, {2*k* + 1}), showing that it exhibits similar behavior. Finally, we derive some partial results on *i*-Mark({1}, {2, 3}), whose SG function seems to behave erratically.

23. Jeff Erickson, Gabriel Nivasch, and Junyan Xu

**Fusible numbers and Peano Arithmetic** [arXiv:2003.14342]

Preliminary version to appear in Proc. 36th Ann. ACM/IEEE Symp. on Logic in Comp. Sci. (LICS 2021).

Inspired by a mathematical riddle involving fuses, we define a set of rational numbers which we call *fusible numbers*. We prove that the set of fusible numbers is well-ordered in **R**, with order type *ε*_{0}. We prove that the density of the fusible numbers along the real line grows at an incredibly fast rate, namely at least like the function *F*_{ε}_{_0} of the fast-growing hierarchy. Finally, we derive some true statements that can be formulated but not proven in Peano Arithmetic, of a different flavor than previously known such statements, for example, "For every natural number *n* there exists a smallest fusible number larger than *n*."

22. Inbar Daum-Sadon and Gabriel Nivasch

**Upper bounds for stabbing simplices by a line** [arXiv:2001.00782]

Discrete Applied Mathematics, 304:248-259, 2021.

It is known that for every *d* there exists a constant *c*_{d}_{,1} > 0 such that for every *n*-point set *X* in **R**^{d} there exists a line that stabs at least *c*_{d}_{,1}*n*^{d} – o(*n*^{d}) of the (*d* – 1)-dimensional simplices spanned by *X*. In this paper we determine the upper bounds for *c*_{d}_{,1} given by the *stretched grid *and the *stretched diagonal* (see [10]) for small values of *d*, using analytical and numerical software methods. Surprisingly, for *d* > 3 the stretched grid yields better bounds than the stretched diagonal.

21. Sergey Avvakumov and Gabriel Nivasch

**Homotopic curve shortening and the affine curve-shortening flow** [arXiv:1909.00263]

Extended abstract in Proc. 36th Int. Symp. Computational Geometry (SoCG), article 12, 15 pages, 2020.

Full version submitted for publication.

We introduce *homotopic curve shortening *(HCS), a discrete process that generalizes the convex-layer decomposition of a planar point set. Under HCS, an initial closed curve (which might self-intersect) evolves in discrete steps in the presence of a fixed set of point obstacles. If the obstacles are chosen to be a regular grid or a random point set, then experimentally HCS seems to behave at the limit like the *affine curve-shortening flow*. Hence, this experimental connection between HCS and ACSF generalizes the link between *grid peeling *and the ACSF observed in our previous work [19]. We also prove that HCS satisfies some properties analogous to those of ACSF.

20. Lee-Ad Gottlieb, Eran Kaufman, Aryeh Kontorovich, and Gabriel Nivasch

**Learning convex polytopes with margin** [arXiv:1805.09719]

Preliminary version in Advances in Neural Information Processing Systems 31 (NIPS 2018), pp. 5706-5716, 2018.

Full version submitted for publication.

We present an improved algorithm for properly learning convex polytopes in the realizable PAC setting from data with a margin: We construct a consistent polytope having about *t* log *t* facets, in time polynomial in *t* (where *t* is the number of facets of the 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.

19. David Eppstein, Sariel Har-Peled, and Gabriel Nivasch

**Grid peeling and the affine curve-shortening flow** [arXiv:1710.03960]

Preliminary version in Proc. 20th Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 109-116, 2018.

Full version in Experimental Mathematics, 29(3):306-316, 2020.

We observe that, experimentally, *grid peeling* (the convex-layer decomposition of subsets of the integer grid) seems to behave at the limit like the *affine curve-shortening flow*. We offer some theoretical arguments to explain this phenomenon. We also derive some rigorous results for the special case of peeling the quarter-infinite grid.

18. Boris Bukh, Po-Shen Loh, and Gabriel Nivasch,

**Classifying unavoidable Tverberg partitions **[arXiv:1611.01078]

Journal of Computational Geometry, 8(1):174-205, 2017.

We try to determine which types of Tverberg partitions unavoidably occur in every sufficiently long point sequence. We provide partial answers in dimensions up to 4.

17. Boris Bukh and Gabriel Nivasch,

**One-sided epsilon-approximants** [arXiv:1603.05717]

A Journey through Discrete Mathematics: A Tribute to Jiří Matoušek (M. Loebl et al., editors), pp. 343-356, Springer, 2017.

Given a finite point set *P* in **R**^{d}, we call a multiset *A* a *one-sided weak ε-approximant* for *P* (with respect to convex sets) if, for every convex set *C* in **R**^{d}, if *α* is the fraction of points of *P* contained in *C*, then *C* contains at least an (*α* – *ε*)-fraction of the points of *A*.

We show that, in contrast with the usual (two-sided) weak *ε*-approximants, for every set *P* in **R**^{d} there exists a one-sided weak *ε*-approximant of size bounded by a function of *ε* and *d*.

16. Gabriel Nivasch and Eran Omri,

**Rainbow matchings and algebras of sets** [arXiv:1503.03671]

Extended abstract in EuroComb 2015 (Electronic Notes in Discrete Mathematics, 49:251-257, 2015).

Full version in Graphs and Combinatorics, 33:473-484, 2017.

What is the smallest number *v* = *v*(*n*) such that, if *A*_{1}, ..., *A*_{n} are *n* equivalence relations on a common finite ground set *X*, such that for each *i* there are at least *v* elements of *X* that belong to *A*_{i}-equivalence classes of size larger than 1, then *X* contains a rainbow matching?

Grinblat recently showed that *v*(*n*) ≤ 10*n*/3 + O(√*n*). We improve the bound to *v*(*n*) ≤ 16*n*/5 + O(1).

15. Gabriel Nivasch

**On the zone of a circle in an arrangement of lines** [arXiv:1503.03462]

Extended abstract in EuroComb 2015 (Electronic Notes in Discrete Mathematics, 49:221-231, 2015).

Full version in Discrete Mathematics, 340:1535-1552, 2017.

Edelsbrunner et al. (1992) showed that the zone of a convex curve (like a circle or a parabola) in an arrangement of lines has complexity O(*n* *α*(*n*)), where *α* is the inverse Ackermann function, by translating the sequence of edges of the zone into an *ababa*-free sequence *S*. Whether the complexity is only linear in *n* is a longstanding open problem.

Here we provide evidence that, for the case of a circle/parabola, the zone complexity is at most linear: We show that a certain configuration of segments is geometrically impossible. As a consequence, the Hart-Sharir sequences, which are essentially the only known way to construct *ababa*-free sequences of superlinear length, cannot occur in *S*.

14. Sathish Govindarajan and Gabriel Nivasch,

**A variant of the Hadwiger-Debrunner (****p****,****q****)-problem in the plane** [arXiv:1409.1194]

Discrete and Computational Geometry, 54:637-646, 2015.

Let *X* be a convex curve in the plane (say, the unit circle), and let *S* be a family of planar convex bodies, such that every two of them meet at a point of *X*. Then *S* has a transversal of size at most 1.75*10^{9}.

Suppose instead that *S* only satisfies the following "(*p*,2)-condition": Among every *p* elements of *S* there are two that meet at a common point of *X*. Then *S* has a transversal of size O(*p*^{8}). For comparison, the best known bound for the Hadwiger--Debrunner (*p*,*q*)-problem in the plane, with *q*=3, is O(*p*^{6}).

13. Gabriel Nivasch, János Pach, and Gábor Tardos,

**The visible perimeter of an arrangement of disks** [arXiv:1206.1422]

Extended abstract in Graph Drawing 2012 (Lecture Notes in Computer Science, 7704:364-375, 2013).

Full version in Computational Geometry: Theory and Applications, 47:42-51, 2014.

Given a collection of *n* opaque unit disks in the plane, we want to find a stacking order for them that maximizes their total visible perimeter. The problem is hardest when the set of centers is uniformly shrunk until it is very small. We show that if the set of centers is dense and very small, then: (1) there is always a stacking order that achieves visible perimeter Ω(*n*^{2/3}); (2) every stacking order achieves visible perimeter O(*n*^{3/4}); and (3) both bounds are asymptotically tight.

12. Gabriel Nivasch, János Pach, Rom Pinchasi, and Shira Zerbib,

**The number of distinct distances from a vertex of a convex polygon** [arXiv:1207.1266]

Journal of Computational Geometry, 4:1-12, 2013.

Erdős conjectured in 1946 that every *n*-point set *P* in convex position in the plane contains a point that determines at least floor(*n*/2) distinct distances to the other points of *P*. The best known lower bound due to Dumitrescu (2006) is 13*n*/36 – O(1). In the present note, we slightly improve on this result to (13/36 + eps)*n* – O(1) for eps ≈ 1/23000. Our main ingredient is an improved bound on the maximum number of isosceles triangles determined by *P*.

11. Boris Bukh and Gabriel Nivasch,

**Upper bounds for centerlines** [arXiv:1107.3421]

Journal of Computational Geometry, 3:20-30, 2012.

Bukh, Matousek, and Nivasch [8] made the following conjecture: For every *n*-point set *S* in **R**^{d} and every *k*, there exists a *k*-flat *f* in **R**^{d} (a "centerflat") at "depth" at least (*k*+1) *n* / (*k*+*d*+1) with respect to *S*, in the sense that every halfspace that contains *f* contains at least that many points of *S*. For *k*=0 this is the centerpoint theorem, and for *k* = *d*–1 it is trivial. Bukh et al. [8] proved the case *k* = *d*–2.

In this paper we focus on the case *k* = 1 (the case of "centerlines"). We show that the "stretched grid" [10] provides a tight upper bound for the conjecture; meaning, no line in **R**^{d} lies at depth larger than 2*n* / (*d*+2) with respect to the *n*-point stretched grid.

10. Boris Bukh, Jiri Matousek, and Gabriel Nivasch,

**Lower bounds for weak epsilon-nets and stair-convexity**

Extended abstract in Proc. 25th ACM Symp. on Computational Geometry (SoCG 2009), pp. 1–10, 2009 [PDF].

Full version in Israel Journal of Mathematics, 182:199-228, 2011 [arXiv:0812.5039].

For every fixed *d* ≥ 2 and every *r* ≥ 1 we construct point sets in **R**^{d} for which every weak 1/*r*-net has at least Ω(*r* log^{d}^{–1} *r*) points. This is the first superlinear lower bound for weak epsilon-nets in a fixed dimension. The construction is a "stretched grid", i.e., the Cartesian product of *d* suitable fast-growing finite sequences, and convexity in this grid can be analyzed using "stair-convexity", a new variant of the usual notion of convexity.

9. Gabriel Nivasch,

**Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations**

Extended abstract in Proc. 20th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 1–10, 2009. SODA 2009 Best Student Paper!

Full version in Journal of the ACM, 57, article 17, 44 pages, 2010 [arXiv:0807.0484].

Davenport-Schinzel sequences have strange upper and lower bounds of the form *n*⋅2^{poly(}^{α}^{(}^{n}^{))}, where *α*(*n*) denotes the inverse Ackermann function (Agarwal, Sharir, and Shor, 1989).

In this paper we derive improved upper bounds for DS sequences of general order *s*. The bounds are now asymptotically tight for *s* even.

More importantly, we also present a new upper-bound technique, based on recurrences very similar to those for "stabbing interval chains" [5]. With this new technique we re-derive our new upper bounds, and we also derive tighter upper bounds for generalized DS sequences.

Regarding lower bounds, we present a construction for DS sequences of order 3 with optimal leading coefficient. We also present a simpler variant of the construction of Agarwal, Sharir and Shor for sequences of even order *s*≥4.

8. Boris Bukh, Jiri Matousek, and Gabriel Nivasch,

**Stabbing simplices by points and flats** [arXiv:0804.4464]

Discrete and Computational Geometry, 43:321–338, 2010.

We construct an *n*-point set *S* in **R**^{d} such that no point in **R**^{d} stabs more than (*n* / (*d*+1))^{d}^{+1} + O(*n*^{d}) simplices spanned by *S*. We also prove that for every *n*-point set *S* in **R**^{d} there exists a (*d*–2)-flat that stabs at least (1 – (2*d*–1)^{–2}) *n*^{3} / 24 – O(*n*^{2}) triangles spanned by *S*. This latter bound follows from the following equipartition result: Every mass distribution in **R**^{d} can be divided into 4*d* – 2 equal parts by 2*d* – 1 hyperplanes passing through a common (*d*–2)-flat.

7. Gabriel Nivasch and Micha Sharir,

**Eppstein's bound on intersecting triangles revisited** [arXiv:0804.4415]

Journal of Combinatorial Theory, Series A, 116:494–497, 2009.

Let *S* be a set of *n* points in the plane, and let *T* be a set of *m* triangles with vertices in *S*. Then there exists a point in the plane contained in Ω(*m*^{3} / (*n*^{6} log^{2} *n*)) triangles of T. Eppstein (1993) gave a proof of this claim, but there is a problem with his proof. Here we provide a correct proof by slightly modifying Eppstein's argument.

6. Gabriel Nivasch,

**More on the Sprague-Grundy function for Wythoff's game**

In Games of No Chance 3 (M. H. Albert and R. J. Nowakowski, editors), MSRI Publications 56, pp. 377–410, Cambridge University Press, 2009.

We prove that, for every fixed *g*, the *g*-values of Wythoff's Sprague-Grundy function lie roughly along two diagonals, of slopes φ and φ^{-1}, radiating from the origin. We also present a convergence conjecture which, if true, yields a recursive algorithm for finding the *n*-th *g*-value in O(log *n*) arithmetical operations.

5. Noga Alon, Haim Kaplan, Gabriel Nivasch, Micha Sharir, and Shakhar Smorodinsky,

**Weak ε-nets and interval chains**

Extended abstract in Proc. 19th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 1194–1203, 2008 [PDF].

Full version in Journal of the ACM, 55, article 28, 32 pages, 2008 [PDF].

We construct *weak epsilon-nets *of almost linear size for some special types of point sets. Our bounds involve the extremely slow-growing inverse Ackermann function. The constructions result from a reduction to a new problem, which we call *stabbing interval chains*. We derive almost-tight upper and lower bounds for this new problem, involving functions of the inverse Ackermann hierarchy.

4. Gabriel Nivasch,

**An improved, simple construction of many halving edges **[PDF]

In Surveys on Discrete and Computational Geometry: Twenty Years Later (J. E. Goodman et al., editors), Contemporary Mathematics 453, pp. 299–305, AMS, 2008.

We construct, for every even *n*, a set of *n* points in the plane that generates Ω(*n* *e*^{(√ ln 4) √ ln }^{n} / √ ln *n*) halving edges. This improves Géza Tóth's previous bound by a constant factor in the exponent. Our construction is significantly simpler than Tóth's.

3. Gabriel Nivasch,

**The Sprague-Grundy function of the game Euclid **[PDF]

Discrete Mathematics, 306:2798–2800, 2006.

The Sprage-Grundy function of the game Euclid is given by *g*(*x*, *y*) = floor(|*y*/*x* - *x*/*y*|).

2. Gabriel Nivasch and Eyal Lev,

**Non-attacking qu****e****ens on a triangle** [PDF]

Mathematics Magazine, 78:399–403, 2005.

How many non-attacking queens can be placed on a triangular board of side *n*?

1. Gabriel Nivasch,

**Cycle detection using a stack** [PDF]

Information Processing Letters, 90:135–140, 2004.

A cute and efficient algorithm for detecting periodicity in sequences produced by repeated application of a given function.

## Ph.D. Thesis

**Weak epsilon-nets, Davenport-Schinzel sequences, and related problems **[PDF]

Tel Aviv University. Advisor: Micha Sharir. 2009

## M.Sc. Thesis

**The Sprague-Grundy function for Wythoff's game: On the location of the ****g****-values **[PDF]

Weizmann Institute of Science. Advisor: Aviezri S. Fraenkel. 2004

## Unpublished

Gabriel Nivasch,

**Experimental results on Hamiltonian-cycle-finding algorithms**, 2003 [PDF]

A project I did under the supervision of Prof. Uriel Feige, at the Weizmann Institute.

We tested a certain heuristic Hamiltonian-cycle algorithm by searching for solutions to knight tour problems. We got some surprising behavior when we added *fake edges *to the graphs—edges that provably are not part of any Hamiltonian cycle. The algorithm performed better *with *fake edges!