Abstract
In the classical linear degeneracy testing problem, we are given n real numbers and a kvariate linear polynomial F, for some constant k, and have to determine whether there exist k numbers a_1,…,a_k from the set such that F(a_1,…,a_k) = 0. We consider a generalization of this problem in which F is an arbitrary constantdegree polynomial, we are given k sets of n real numbers, and have to determine whether there exists a ktuple of numbers, one in each set, on which F vanishes. We give the first improvement over the naïve O^*(n^{k1}) algorithm for this problem (where the O^*(⋅) notation omits subpolynomial factors).
We show that the problem can be solved in time O^*(n^{k  2 + 4/(k+2)}) for even k and in time O^*(n^{k  2 + (4k8)/(k²5)}) for odd k in the real RAM model of computation. We also prove that for k = 4, the problem can be solved in time O^*(n^2.625) in the algebraic decision tree model, and for k = 5 it can be solved in time O^*(n^3.56) in the same model, both improving on the above uniform bounds.
All our results rely on an algebraic generalization of the standard meetinthemiddle algorithm for kSUM, powered by recent algorithmic advances in the polynomial method for semialgebraic range searching. In fact, our main technical result is much more broadly applicable, as it provides a general tool for detecting incidences and other interactions between points and algebraic surfaces in any dimension. In particular, it yields an efficient algorithm for a general, algebraic version of Hopcroft’s pointline incidence detection problem in any dimension.
BibTeX  Entry
@InProceedings{cardinal_et_al:LIPIcs.SoCG.2023.22,
author = {Cardinal, Jean and Sharir, Micha},
title = {{Improved Algebraic Degeneracy Testing}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {22:122:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772730},
ISSN = {18688969},
year = {2023},
volume = {258},
editor = {Chambers, Erin W. and Gudmundsson, Joachim},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17872},
URN = {urn:nbn:de:0030drops178723},
doi = {10.4230/LIPIcs.SoCG.2023.22},
annote = {Keywords: Degeneracy testing, kSUM problem, incidence bounds, Hocroft’s problem, polynomial method, algebraic decision trees}
}
Keywords: 

Degeneracy testing, kSUM problem, incidence bounds, Hocroft’s problem, polynomial method, algebraic decision trees 
Collection: 

39th International Symposium on Computational Geometry (SoCG 2023) 
Issue Date: 

2023 
Date of publication: 

09.06.2023 