Publications

27. Gabriel Nivasch and Lior Shiboli

Ordinals and recursive algorithms [arXiv:2311.17210]

Submitted for publication.

Motivated by recursive algorithms that arise in the study of fusible numbers, we determine sufficient conditions under which recursive algorithms of the form "M(x): if x < 0 return f(x), else return g1(–M(x–g2(–M(x–...–gk(–M(x–s(x)))...))))" halt for all x. Specifically, we show that if the given functions f, s, g1, ..., gk  satisfy a certain condition which we call ordinal decreasing, then M halts for all x and is also ordinal decreasing. Further, to each ordinal decreasing function corresponds an ordinal type. We bound the ordinal type o(M) in terms of  o(f), o(s), o(g1), ..., o(gk).

26. Alexander I. Bufetov, Gabriel Nivasch, and Fedor Pakhomov

Generalized fusible numbers and their ordinals [arXiv:2205.11017]

Annals of Pure and Applied Logic, 175, 25 pages, 2024.

Kruskal's tree theorem implies an upper bound of the small Veblen ordinal for the order type of any generalization of fusible numbers to n-ary functions. We show that the natural generalization, and indeed, any linear n-ary function, yields a set with order type just φn–1(0). On the other hand, there do exist (quite artificial) continuous functions that yield order types approaching the small Veblen ordinal.

23. Jeff Erickson, Gabriel Nivasch, and Junyan Xu

Fusible numbers and Peano Arithmetic [arXiv:2003.14342]

Preliminary version in Proc. 36th Ann. ACM/IEEE Symp. on Logic in Comp. Sci. (LICS), 13 pages, 2021. Distinguished Paper

Full version in Logical Methods in Computer Science, 18(3), article 6, 26 pages, 2022. 

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."

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 Rd, we call a multiset A a one-sided weak ε-approximant for P (with respect to convex sets) if, for every convex set C in Rd, 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 Rd 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 A1, ..., An 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 Ai-equivalence classes of size larger than 1, then X contains a rainbow matching?

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

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. 

Bukh, Matousek, and Nivasch [8] made the following conjecture: For every n-point set S in Rd and every k, there exists a k-flat f in Rd (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 Rd lies at depth larger than 2n / (d+2) with respect to the n-point stretched grid. 

Davenport-Schinzel sequences have strange upper and lower bounds of the form n⋅2poly(α(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. 

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.

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.

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!