In a Nisan-Wigderson design polynomial, denoted NW, every pair of monomials has few variables in common and this property has been used in recent years to prove lower bounds for several classes of arithmetic circuits. But unlike other well known polynomial families, like the Permanent, the Determinant and the iterated matrix multiplication polynomials, many natural questions on the design polynomial family are open. Some of them are as follows:
* Is the design polynomial family VNP complete?
* What is the structure of the group of symmetries of NW?
* Is NW characterized by its symmetries over the complex field, real field and finite fields?
* Given an arithmetic circuit C, can we efficiently test if C computes NW?
* Given oracle access to a polynomial f, can we determine efficiently if f is equivalent to NW, i.e. if f = NW(AX) for some invertible matrix A, where X is a column vector of variables.
* Given a point v in the Boolean hypercube, can it be checked efficiently if NW(v)=0? In this talk, we would discuss answers to a few of these questions.
Joint work with Chandan Saha.
This video was produced by the International Centre for Physical Sciences, forming part of the Workshop on Algebraic Complexity Theory.
