Nikhil Gupta, Chandan Saha

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 ...
more >>>