Computations beyond Exponentiation Gates and Applications
Computations beyond Exponentiation Gates and Applications
复制标题
超越幂门的计算和应用
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Ilya Volkovich
中科院分区：
文献类型：
--
作者：
Ilya Volkovich
在算术电路复杂性方面，标准运算是{+，×}。然而，在某些情况下，也考虑了幂运算门(见例如。[BB98、ASSS12、Kay12、KSS14])。在这篇文章中，我们研究了给定先知对其幂的访问，如何有效地计算多项式的问题。也就是说，在乘法门之外。作为应用，我们证明了：·电路类C的重构算法可以扩展到处理f∈C的f。存在一个分解稀疏多项式的有效算法。·存在一个有效的算法来检验稀疏多项式的两次幂是否相等。也就是说，当f和g稀疏时，f≡g。
In Arithmetic Circuit Complexity the standard operations are {+,×}. Yet, in some scenarios exponentiation gates are considered as well (see e.g. [BB98, ASSS12, Kay12, KSS14]). In this paper we study the question of efficiently evaluating a polynomial given an oracle access to its power. That is, beyond an exponentiation gate. As applications, we show that: • A reconstruction algorithm for a circuit class C can be extended to handle f for f ∈ C. • There exists an efficient algorithm for factoring sparse multiquadratic polynomials. • There exists an efficient algorithm for testing whether two powers of sparse polynomials are equal. That is, f ≡ g when f and g are sparse.