论文标题
循环组合认同测试和应用
Cyclotomic Identity Testing and Applications
论文作者
论文摘要
我们考虑循环基因身份测试（CIT）问题：给定多项式$ f（x_1，\ ldots，x_k）$，决定$ f（ζ_N^{e_1} {e_1}，\ ldots，ζ_N^{e_k}）$是零的$ e_1，\ ldots，e_k $是整数，以二进制为代表。当代数电路给出$ f $时，我们给出一种随机的多项式时间算法，用于CIT假设普遍的Riemann假设（GRH），并表明该问题是无条件地存在的。当$ f $由多项式界限的电路给出时，我们给出了随机的NC算法。如果$ f $是线性形式，我们表明问题在于NC。要了解何时可以在确定性的多项式时间内解决CIT，我们考虑所谓的对角度深度-3电路，即多项式$ f = \ sum_ {i = 1}^m g_i^{d_i} $，其中$ g_i $是$ g_i $是线性形式和$ d_i $ a position Integer。我们观察到，该类别CIT的多项式时间算法将产生用于多项式认同测试的亚指数时间算法。但是，假设GRH，我们表明，如果线性形式〜$ g_i $都是相同的，那么CIT可以在多项式时间内解决。最后，我们使用结果给出了一个新的证据，即可以在随机NC中确定压缩字符串平等，即使用无上下文语法提出的字符串。
We consider the cyclotomic identity testing (CIT) problem: given a polynomial $f(x_1,\ldots,x_k)$, decide whether $f(ζ_n^{e_1},\ldots,ζ_n^{e_k})$ is zero, where $ζ_n = e^{2πi/n}$ is a primitive complex $n$-th root of unity and $e_1,\ldots,e_k$ are integers, represented in binary. When $f$ is given by an algebraic circuit, we give a randomized polynomial-time algorithm for CIT assuming the generalised Riemann hypothesis (GRH), and show that the problem is in coNP unconditionally. When $f$ is given by a circuit of polynomially bounded degree, we give a randomized NC algorithm. In case $f$ is a linear form we show that the problem lies in NC. Towards understanding when CIT can be solved in deterministic polynomial-time, we consider so-called diagonal depth-3 circuits, i.e., polynomials $f=\sum_{i=1}^m g_i^{d_i}$, where $g_i$ is a linear form and $d_i$ a positive integer given in unary. We observe that a polynomial-time algorithm for CIT on this class would yield a sub-exponential-time algorithm for polynomial identity testing. However, assuming GRH, we show that if the linear forms~$g_i$ are all identical then CIT can be solved in polynomial time. Finally, we use our results to give a new proof that equality of compressed strings, i.e., strings presented using context-free grammars, can be decided in randomized NC.
