In a Nisan-Wigderson design polynomial (in short, a design polynomial), every pair of monomials share a few common variables. A useful example of such a polynomial, is the following:
$$\text{NW}_{d,k}(\mathbf{x}) = \sum_{h \in \mathbb{F}_d[z], ~\deg(h) \leq k}{~~~~\prod_{i = 0}^{d-1}{x_{i, h(i)}}},$$
where $d$ is a prime, $\mathbb{F}_d$ is the finite field with $d$ elements, and $k \ll d$. The degree of the gcd of every pair of monomials in $\text{NW}_{d,k}$ is at most $k$. For concreteness, we fix $k = \lceil \sqrt{d} \rceil$. The family of polynomials $\mathcal{NW} :=$ {$\text{NW}_{d,k} : d \text{ is a prime}$} and close variants of it have been used as hard explicit polynomial families in several recent arithmetic circuit lower bound proofs. But, unlike the permanent, very little is known about the various structural and algorithmic/complexity aspects of $\mathcal{NW}$ beyond the fact that $\mathcal{NW} \in \text{VNP}$. Is $\text{NW}_{d,k}$ characterized by its symmetries? Is it circuit-testable, i.e., given a circuit $\text{C}$ can we check efficiently if $\text{C}$ computes $\text{NW}_{d,k}(\mathbf{x})$? What is the complexity of equivalence test for $\mathcal{NW}$, i.e., given black-box access to a $f \in \mathbb{F}[\mathbf{x}]$, can we check efficiently if there exists an invertible linear transformation $A$ such that $f = \text{NW}_{d,k}(A \cdot \mathbf{x})$? Characterization of polynomials by their symmetries plays a central role in the geometric complexity theory program. Here, we answer the first two questions and partially answer the third.

We show that $\text{NW}_{d,k}(\mathbf{x})$ is characterized by its group of symmetries over $\mathbb{C}$, but not over $\mathbb{R}$. We also show that $\text{NW}_{d,k}(\mathbf{x})$ is characterized by circuit identities which implies that $\text{NW}_{d,k}(\mathbf{x})$ is circuit-testable in randomized polynomial time. As another application of this characterization, we obtain the ``flip theorem'' for $\mathcal{NW}$: Suppose $\text{NW}_{d,k}(\mathbf{x})$ is not computable by circuits of size $s$. Then, there exist $\text{poly}(s)$ many points $\mathbf{a}_{1},\ldots,\mathbf{a}_{m}$ such that for every circuit $\text{C}$ of size $s$, there is an $\ell \in [m]$ satisfying $\text{C}(\mathbf{a}_{\ell}) \neq \text{NW}_{d,k}(\mathbf{a}_{\ell})$. These points can be computed deterministically in $\text{poly}(s)$ time if black-box polynomial identity testing for size-$s$ circuits can be derandomized in $\text{poly}(s)$ time. It is well-known that the permanent polynomial has the above-mentioned features.

We give an efficient equivalence test for $\mathcal{NW}$ in the case where the transformation $A$ is a block-diagonal permutation-scaling matrix. The design of this algorithm is facilitated by an almost complete understanding of the group of symmetries of $\text{NW}_{d,k}(\mathbf{x})$: We show that if $A$ is in the group of symmetries of $\text{NW}_{d,k}(\mathbf{x})$ then $A = D \cdot P$, where $D$ and $P$ are diagonal and permutation matrices respectively. This is proved by completely characterizing the Lie algebra of $\text{NW}_{d,k}(\mathbf{x})$, and using an interplay between the Hessian of $\text{NW}_{d,k}(\mathbf{x})$ and the evaluation dimension.

We have added a special case of the equivalence test for design polynomials.

In a Nisan-Wigderson design polynomial (in short, a design polynomial), the gcd of every pair of monomials has a low degree. A useful example of such a polynomial is the following:
$$\text{NW}_{d,k}(\mathbf{x}) = \sum_{h \in \mathbb{F}_d[z], ~\deg(h) \leq k}{~~~~\prod_{i = 0}^{d-1}{x_{i, h(i)}}},$$
where $d$ is a prime, $\mathbb{F}_d$ is the finite field with $d$ elements, and $k \ll d$. The degree of the gcd of every pair of monomials in $\text{NW}_{d,k}$ is at most $k$. For concreteness, let us fix $k = \lceil \sqrt{d} \rceil$. The family of polynomials $\mathcal{NW} :=$ {$\text{NW}_{d,k} : d \text{ is a prime}$} and close variants of it have been used as hard explicit polynomial families in several recent arithmetic circuit lower bound proofs. But, unlike the permanent, very little is known about the various complexity and structural aspects of $\mathcal{NW}$ beyond the fact that $\mathcal{NW} \in \text{VNP}$. Is $\mathcal{NW}$ $\text{VNP}$-complete? Is $\text{NW}_{d,k}$ characterized by its symmetries? Is it circuit-testable, i.e., given a circuit $\text{C} $ can we check efficiently if $\text{C}$ computes $\text{NW}_{d,k}$? Characterization of polynomials by their symmetries plays a central role in the geometric complexity theory program. Here, we answer the last two questions.

We show that $\text{NW}_{d,k}$ is characterized by its group of symmetries over $\mathbb{C}$. We also show that $\text{NW}_{d,k}$ is characterized by circuit identities which implies that $\text{NW}_{d,k}$ is circuit-testable in randomized polynomial time. As another implication, we obtain the ``flip theorem'' for $\mathcal{NW}$: Suppose $\text{NW}_{d,k}$ is not computable by circuits of size $s$. Then, there exist $\text{poly}(s)$ many points $\mathbf{a}_1, \ldots, \mathbf{a}_m$ such that for every circuit $\text{C} $ of size $s$, there is an $\ell \in [m]$ satisfying $\text{C} (\mathbf{a}_\ell) \neq \text{NW}_{d,k}(\mathbf{a}_\ell)$. These points can be computed deterministically in $\text{poly}(s)$ time if black-box polynomial identity testing for size-$s$ circuits can be derandomized in $\text{poly}(s)$ time. It is well-known that the permanent polynomial has the above-mentioned features.

We also show a structural similarity between the group of symmetries of the permanent and that of $\text{NW}_{d,k}$: If $A$ is in the group of symmetries of $\text{NW}_{d,k}$ then $A = D \cdot P$, where $D$ and $P$ are diagonal and permutation matrices respectively. This is proved by completely characterizing the Lie algebra of $\text{NW}_{d,k}$, and using an interplay between the Hessian of $\text{NW}_{d,k}$ and the evaluation dimension.