English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

In this paper we show that black-box polynomial identity testing for noncommutative polynomials f∈⟨z1,z2,…,zn⟩ of degree D and sparsity t, can be done in randomized (n,logt,logD) time. As a consequence, given a circuit C of size s computing a polynomial f∈⟨ z1,z2,…,zn⟩ 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 logt. 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∈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 s() when  is sufficiently large depending on the degree of f.

Randomized polynomial time identity testing for noncommutative circuits