In this paper we show that black-box polynomial identity testing (PIT) for n-variate noncommutative polynomials f of degree D with at most t nonzero monomials can be done in randomized poly(n, log t, log D) time, and ...
详细信息
In this paper we show that black-box polynomial identity testing (PIT) for n-variate noncommutative polynomials f of degree D with at most t nonzero monomials can be done in randomized poly(n, log t, log D) time, and consequently in randomized poly(n, log t, s) time if f is computable by a circuit of size s. This result makes progress on a question that has been open for over a decade. Our algorithm is based on efficiently isolating a monomial using nondeterministic automata. The above result does not yield an efficient randomized PIT for noncommutative circuits in general, as noncommutative circuits of size s can compute polynomials with a double-exponential (in s) number of monomials. As a first step, we consider a natural class of homogeneous noncommutative circuits, that we call +-regular circuits, and give a white-box polynomial-time deterministic PIT for them. These circuits can compute noncommutative polynomials with number of monomials double-exponential in the circuit size. Our algorithm combines some new structural results for +-regular circuits with known PIT results for noncommutative algebraic branching programs, a rank bound for commutative depth-3 identities, and an equivalence testing problem for words. Finally, we solve the black-box PIT problem for depth-3 +-regular circuits in randomized polynomial time. In particular, we show if f is a nonzero noncommutative polynomial in n variables over the field F computed by a depth-3 +-regular circuit of size s, then f cannot be a polynomial identity for the matrix algebra M-s(F) when F is sufficiently large depending on the degree of f.
We show that proving mildly super-linear lower bounds on non-commutative arithmetic circuits implies exponential lower bounds on non-commutative circuits. That is, non-commutative circuit complexity is a threshold phe...
详细信息
ISBN:
(纸本)9783959770699
We show that proving mildly super-linear lower bounds on non-commutative arithmetic circuits implies exponential lower bounds on non-commutative circuits. That is, non-commutative circuit complexity is a threshold phenomenon: an apparently weak lower bound actually suffices to show the strongest lower bounds we could desire. This is part of a recent line of inquiry into why arithmetic circuit complexity, despite being a heavily restricted version of Boolean complexity, still cannot prove super-linear lower bounds on general devices. One can view our work as positive news (it suffices to prove weak lower bounds to get strong ones) or negative news (it is as hard to prove weak lower bounds as it is to prove strong ones). We leave it to the reader to determine their own level of optimism.
We show that proving mildly super-linear lower bounds on non-commutative arithmetic circuits implies exponential lower bounds on non-commutative circuits. That is, non-commutative circuit complexity is a threshold phe...
详细信息
ISBN:
(纸本)9783959770699
We show that proving mildly super-linear lower bounds on non-commutative arithmetic circuits implies exponential lower bounds on non-commutative circuits. That is, non-commutative circuit complexity is a threshold phenomenon: an apparently weak lower bound actually suffices to show the strongest lower bounds we could *** is part of a recent line of inquiry into why arithmetic circuit complexity, despite being a heavily restricted version of Boolean complexity, still cannot prove super-linear lower bounds on general devices. One can view our work as positive news (it suffices to prove weak lower bounds to get strong ones) or negative news (it is as hard to prove weak lower bounds as it is to prove strong ones). We leave it to the reader to determine their own level of optimism.
In this paper we show that black-box polynomial identity testing for noncommutative polynomials f is an element of F of degree D and sparsity t, can be done in randomized poly(n, log t, log D) time. As a consequence,...
详细信息
ISBN:
(纸本)9781450345286
In this paper we show that black-box polynomial identity testing for noncommutative polynomials f is an element of F < z(1), z(2), ... z(n)> of degree D and sparsity t, can be done in randomized poly(n, log t, log D) time. As a consequence, given a circuitC of size s computing a polynomial f is an element of F < z(1), z(2), ...z(n)> with at most t non-zero monomials, then testing if f is identically zero can be done by a randomized algorithm with running time polynomial in s and n and log t. This makes significant progress on a question that has been open for over ten years. Our algorithm is based on automata-theoretic ideas that can efficiently isolate a monomial in the given polynomial. In particular, we carry out the monomial isolation using nondeterministic automata. In general, noncommutative circuits of size s can compute polynomials of degree exponential in s and number of monomials double-exponential in s. In this paper, we consider a natural class of homogeneous noncommutative circuits, that we call +-regular circuits, and give a white-box polynomial time deterministic polynomial identity test. These circuits can compute noncommutative polynomials with number of monomials double-exponential in the circuit size. Our algorithm combines some new structural results for +-regular circuits with known results for noncommutative ABP identity testing, rank bound of commutative depth three identities, and equivalence testing problem for words. Finally, we consider the black-box identity testing problem for depth three +-regular circuits and give a randomized polynomial time identity test. In particular, we show if f 2 F < Z > is a nonzero noncommutative polynomial computed by a depth three +-regular circuit of size s, then f cannot be a polynomial identity for the matrix algebra M-s(F) when F is sufficiently large depending on the degree of f.
Symbolic matrices in non-commuting variables, and the related structural and algorithmic questions, have a remarkable number of diverse origins and motivations. They arise independently in (commutative) invariant theo...
详细信息
ISBN:
(纸本)9781509039333
Symbolic matrices in non-commuting variables, and the related structural and algorithmic questions, have a remarkable number of diverse origins and motivations. They arise independently in (commutative) invariant theory and representation theory, linear algebra, optimization, linear system theory, quantum information theory, and naturally in non-commutative algebra. In this paper we present a deterministic polynomial time algorithm for testing if a symbolic matrix in non-commuting variables over Q is invertible or not. The analogous question for commuting variables is the celebrated polynomial identity testing (PIT) for symbolic determinants. In contrast to the commutative case, which has an efficient probabilistic algorithm, the best previous algorithm for the non-commutative setting required exponential time [1] (whether or not randomization is allowed). The main (simple!) technical contribution of this paper is an analysis of an existing "operator scaling" algorithm due to Gurvits [2], which solved some special cases of the same problem we do (these already include optimization problems like matroid intersection). This analysis of the running time of Gurvits' algorithm combines results from some of these different fields. It lower bounds a parameter of quantum maps called capacity, via degree bounds from algebraic geometry on the Left-Right group action, which in turn is relevant due to certain characterization of the free skew (non-commutative) field. Via the known connections above, our algorithm efficiently solves several problems in different areas which had only exponential-time algorithms prior to this work. These include the "word problem" for the free skew field (namely identity testing for rational expressions over non-commuting variables), testing if a quantum operator is "rank decreasing", and the membership problem in the null-cone of a natural group action arising in Geometric Complexity Theory (GCT). Moreover, extending our algorithm to actually com
We investigate the phenomenon of depth-reduction in commutative and non-commutative arithmetic circuits. We prove that in the commutative setting, uniform semi-unbounded arithmetic circuits of logarithmic depth are as...
详细信息
We investigate the phenomenon of depth-reduction in commutative and non-commutative arithmetic circuits. We prove that in the commutative setting, uniform semi-unbounded arithmetic circuits of logarithmic depth are as powerful as uniform arithmetic circuits of polynomial degree (and unrestricted depth);earlier proofs did not work in the uniform setting. This also provides a unified proof of the circuit characterizations of the class LOGCFL and its counting variant #LOGCFL. We show that AC(1) has no more power than arithmetic circuits of polynomial size and degree n(O(log log n)) (improving the trivial bound of n(O(log n))). Connections sire drawn between TC1 and arithmetic circuits of polynomial size and degree. Then we consider non-commutative computation. We show that over the algebra (Sigma*, max, concat), arithmetic circuits of polynomial size and polynomial degree can be reduced to O(log(2) n) depth land even to O(log n) depth if unbounded-fanin gates are allowed). This establishes that OptLOGCFL is in AC(1). This is the first depth-reduction result for arithmetic circuits over a non-commutative semiring, and it complements the lower bounds of Kosaraju and Nisan showing that depth reduction cannot be done in the general non-commutative setting. We define new notions called "short-left-paths" and "short-right-paths'' and we show that these notions provide a characterization of the classes of arithmetic circuits for which optimal depth reduction is possible. This class also can be characterized using the AuxPDA model. Finally, we characterize the languages generated by efficient circuits over the semiring (2(Sigma*), union, concat) in terms of simple one-way machines, and we investigate and extend earlier lower bounds on non-commutative circuits. (C) 1998-Elsevier Science B.V. All rights reserved.
暂无评论