 LeeAd 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. 57065716, 2018.
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.
 David Eppstein, Sariel HarPeled, and Gabriel Nivasch
Grid peeling and the affine curveshortening flow [arXiv:1710.03960]
Preliminary version in Proc. 20th Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 109116, 2018.
Full version in Experimental Mathematics.
We observe that, experimentally, grid peeling (the convexlayer decomposition of subsets of the integer grid) seems to behave at the limit like the affine curveshortening flow. We offer some theoretical arguments to explain this phenomenon. We also derive some rigorous results for the special case of peeling the quarterinfinite grid.
 Boris Bukh, PoShen Loh, and Gabriel Nivasch,
Classifying unavoidable Tverberg partitions [arXiv:1611.01078]
Journal of Computational Geometry, 8(1):174205, 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.
 Boris Bukh and Gabriel Nivasch,
Onesided epsilonapproximants [arXiv:1603.05717]
A Journey through Discrete Mathematics: A Tribute to Jiří Matoušek (M. Loebl et al., editors), pp. 343356, Springer, 2017.
Given a finite point set P in R^{d}, we call a multiset A a onesided 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 (twosided) weak εapproximants, for every set P in R^{d} there exists a onesided weak εapproximant of size bounded by a function of ε and d.
 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:251257, 2015).
Full version in Graphs and Combinatorics, 33:473484, 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) ≤ 10n/3 + O(√n). We improve the bound to v(n) ≤ 16n/5 + O(1).
 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:221231, 2015).
Full version in Discrete Mathematics, 340:15351552, 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 ababafree 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 HartSharir sequences, which are essentially the only known way to construct ababafree sequences of superlinear length, cannot occur in S.
 Sathish Govindarajan and Gabriel Nivasch,
A variant of the HadwigerDebrunner (p,q)problem in the plane [arXiv:1409.1194]
Discrete and Computational Geometry, 54:637646, 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 HadwigerDebrunner (p,q)problem in the plane, with q=3, is O(p^{6}).
 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:364375, 2013).
Full version in Computational Geometry: Theory and Applications, 47:4251, 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.
 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:112, 2013.
Erdős conjectured in 1946 that every npoint 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 13n/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.
 Boris Bukh and Gabriel Nivasch,
Upper bounds for centerlines [arXiv:1107.3421]
Journal of Computational Geometry, 3:2030, 2012.
Bukh, Matousek, and Nivasch made the following conjecture: For every npoint set S in R^{d} and every k, there exists a kflat 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. 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" provides a tight upper bound for the conjecture; meaning, no line in R^{d} lies at depth larger than 2n / (d+2) with respect to the npoint stretched grid.
 Boris Bukh, Jiri Matousek, and Gabriel Nivasch,
Lower bounds for weak epsilonnets and stairconvexity
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:199228, 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/rnet has at least Ω(r log^{d–1} r)
points. This is the first superlinear lower bound for weak epsilonnets
in a fixed dimension. The construction is a "stretched grid", i.e., the
Cartesian product of d suitable fastgrowing finite sequences,
and convexity in this grid can be analyzed using "stairconvexity", a
new variant of the usual notion of convexity.
 Gabriel Nivasch,
Improved bounds and new techniques for DavenportSchinzel sequences and their generalizations
Extended abstract in Proc. 20th ACMSIAM 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].
DavenportSchinzel 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 upperbound technique, based on recurrences very similar to those for "stabbing interval chains". With this new technique we rederive 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.
 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 npoint 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 npoint set S in R^{d} there exists a (d–2)flat that stabs at least (1 – (2d–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 4d – 2 equal parts by 2d – 1 hyperplanes passing through a common (d–2)flat.
 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.
 Gabriel Nivasch,
More on the SpragueGrundy 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 gvalues of Wythoff's SpragueGrundy 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 nth gvalue in O(log n) arithmetical operations.
 Noga Alon, Haim Kaplan, Gabriel Nivasch, Micha Sharir, and Shakhar Smorodinsky,
Weak εnets and interval chains
Extended abstract in Proc. 19th ACMSIAM 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 epsilonnets of almost linear size for some special types of point sets. Our bounds involve the extremely slowgrowing inverse Ackermann function. The constructions result from a reduction to a new problem, which we call stabbing interval chains. We derive almosttight upper and lower bounds for this new problem, involving functions of the inverse Ackermann hierarchy.
 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.
 Gabriel Nivasch,
The SpragueGrundy function of the game Euclid [PDF]
Discrete Mathematics, 306:2798–2800, 2006.
The SprageGrundy function of the game Euclid is given by g(x, y) = floor[y/x  x/y].
 Gabriel Nivasch and Eyal Lev,
Nonattacking queens on a triangle [PDF]
Mathematics Magazine, 78:399–403, 2005.
How many nonattacking queens can be placed on a triangular board of side n?
 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 epsilonnets, DavenportSchinzel sequences, and related problems [PDF]
Tel Aviv University. Advisor: Micha Sharir. 2009
M.Sc. Thesis
The SpragueGrundy function for Wythoff's game: On the location of the gvalues [PDF]
Weizmann Institute of Science. Advisor: Aviezri S. Fraenkel. 2004
Unpublished
 Gabriel Nivasch,
Experimental results on Hamiltoniancyclefinding algorithms, 2003 [PDF]
A project I did under the supervision of Prof. Uriel Feige, at the Weizmann Institute.
We tested a certain heuristic Hamiltoniancycle 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!
