论文标题
改进的代数退化测试
Improved Algebraic Degeneracy Testing
论文作者
论文摘要
在经典的线性退化测试问题中，对于某些常数$ k $，我们得到了$ n $真实数字和$ k $ - variate线性多项式$ f $，并且必须确定是否存在$ k $ $ k $ a_1，\ ldots，a_k $，a_k $，a_k $，a_1，\ ldots $ f（a_1，\ ldots，a__k a _____k）= 0 $。我们考虑了此问题的概括，其中$ f $是任意的恒定度多项式，我们将获得$ k $的$ n $数字集，并且必须确定是否存在$ k $ - $ k $ - 数字的数字，每组$ f $ av $ nistans nisthes nestens nevens of nevens。对于此问题，我们给出了对幼稚的$ o^*（n^{k-1}）$算法的第一个改进（其中$ o^*（\ cdot）$ note法省略了次级别的单位因素）。 我们表明，问题可以在时间$ o^{k -2 + \ frac 4 {k + 2}}} \右）$ for $ o^{k -2 + \ frac 4 {n^{k -2 + \ frac 4 {n^{k -2 + \ frac 4 {n^{k + 2}} \右）$，并且随着时间的推移$ o^*\ left（n^{k -2 + \ frac {4k -8} {4k -8} {4k -5} {k^2-5} {k^2-5} {k^2-5}} {我们还证明，对于$ k = 4 $，可以在代数决策树模型中在时间$ o^*（n^{2.625}）$中解决该问题，对于$ k = 5 $，可以在时间$ o^*（n^{3.56}）$中解决同一模型，在上面的型号上都可以在上述尺寸上进行改进。 我们所有的结果都依赖于$ k $ - sum的标准聚会算法的代数概括，并由半代数范围搜索的多项式方法中最近的算法进步提供支持。实际上，我们的主要技术结果更广泛地适用，因为它提供了一种通用工具，用于检测任何维度的点和代数表面之间的事件和其他相互作用。特别是，它为霍普罗夫特点线发病率检测问题的一般代数版本提供了有效的算法。
In the classical linear degeneracy testing problem, we are given $n$ real numbers and a $k$-variate linear polynomial $F$, for some constant $k$, and have to determine whether there exist $k$ numbers $a_1,\ldots,a_k$ from the set such that $F(a_1,\ldots,a_k) = 0$. We consider a generalization of this problem in which $F$ is an arbitrary constant-degree polynomial, we are given $k$ sets of $n$ numbers, and have to determine whether there exist a $k$-tuple of numbers, one in each set, on which $F$ vanishes. We give the first improvement over the naïve $O^*(n^{k-1})$ algorithm for this problem (where the $O^*(\cdot)$ notation omits subpolynomial factors). We show that the problem can be solved in time $O^*\left( n^{k - 2 + \frac 4{k+2}}\right)$ for even $k$ and in time $O^*\left( n^{k - 2 + \frac{4k-8}{k^2-5}}\right)$ 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 meet-in-the-middle algorithm for $k$-SUM, powered by recent algorithmic advances in the polynomial method for semi-algebraic 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 point-line incidence detection problem in any dimension.
