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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

A $\Sigma\Pi\Sigma\Pi(k)$ circuit$C=\sum_{i=1}^kF_i=\sum_{i=1}^k\prod_{j=1}^{d_i}f_{ij}$ is unmixed if for each$i\in[k]$, $F_i=f_{i1}(x_1)... f_{in}(x_n)$, where each $f_{ij}$ is aunivariate polynomial given in the sparse representation. In this paper, wegive a polynomial time black-box algorithm of identity testing for the lowdegree unmixed $\Sigma\Pi\Sigma\Pi(k)$ circuits. In order to obtain theblack-box algorithm, we first show that a special class of low degree unmixed$\Sigma\Pi\Sigma\Pi(k)$ circuits of size $s$ is $s^{O(k^2)}$-sparse. Then weconstruct a hitting set $\mathcal{H}$ in polynomial time for the low degreeunmixed $\Sigma\Pi\Sigma\Pi(k)$ circuits from the sparsity result above. Theconstructed hitting set is polynomial size. Thus we can test whether thecircuit or the polynomial $C$ is identically zero by checking whether $C(a)=0$for each $a\in\mathcal{H}$. This is the first polynomial time black-boxalgorithm for the low degree unmixed $\Sigma\Pi\Sigma\Pi(k)$ circuits, whichalso partly answers a question of Saxena \cite{SAX}.

Black-box Identity Testing for Low Degree Unmixed $\Sigma\Pi\Sigma\Pi(k)$ Circuits