## Towards a Charcterization of the Symmetries of the Nisan-Wigderson Polynomial Family

dc.contributor.advisor | Saha, Chandan | |

dc.contributor.author | Gupta, Nikhil | |

dc.date.accessioned | 2018-07-09T13:29:26Z | |

dc.date.accessioned | 2018-07-31T04:39:20Z | |

dc.date.available | 2018-07-09T13:29:26Z | |

dc.date.available | 2018-07-31T04:39:20Z | |

dc.date.issued | 2018-07-09 | |

dc.date.submitted | 2017 | |

dc.identifier.uri | http://etd.iisc.ac.in/handle/2005/3802 | |

dc.identifier.abstract | http://etd.iisc.ac.in/static/etd/abstracts/4673/G28606-Abs.pdf | en_US |

dc.description.abstract | Understanding the structure and complexity of a polynomial family is a fundamental problem of arithmetic circuit complexity. There are various approaches like studying the lower bounds, which deals with nding the smallest circuit required to compute a polynomial, studying the orbit and stabilizer of a polynomial with respect to an invertible transformation etc to do this. We have a rich understanding of some of the well known polynomial families like determinant, permanent, IMM etc. In this thesis we study some of the structural properties of the polyno-mial family called the Nisan-Wigderson polynomial family. This polynomial family is inspired from a well known combinatorial design called Nisan-Wigderson design and is recently used to prove strong lower bounds on some restricted classes of arithmetic circuits ([KSS14],[KLSS14], [KST16]). But unlike determinant, permanent, IMM etc, our understanding of the Nisan-Wigderson polynomial family is inadequate. For example we do not know if this polynomial family is in VP or VNP complete or VNP-intermediate assuming VP 6= VNP, nor do we have an understanding of the complexity of its equivalence test. We hope that the knowledge of some of the inherent properties of Nisan-Wigderson polynomial like group of symmetries and Lie algebra would provide us some insights in this regard. A matrix A 2 GLn(F) is called a symmetry of an n-variate polynomial f if f(A x) = f(x): The set of symmetries of f forms a subgroup of GLn(F), which is also known as group of symmetries of f, denoted Gf . A vector space is attached to Gf to get the complete understanding of the symmetries of f. This vector space is known as the Lie algebra of group of symmetries of f (or Lie algebra of f), represented as gf . Lie algebra of f contributes some elements of Gf , known as continuous symmetries of f. Lie algebra has also been instrumental in designing e cient randomized equivalence tests for some polynomial families like determinant, permanent, IMM etc ([Kay12], [KNST17]). In this work we completely characterize the Lie algebra of the Nisan-Wigderson polynomial family. We show that gNW contains diagonal matrices of a speci c type. The knowledge of gNW not only helps us to completely gure out the continuous symmetries of the Nisan-Wigderson polynomial family, but also gives some crucial insights into the other symmetries of Nisan-Wigderson polynomial (i.e. the discrete symmetries). Thereafter using the Hessian matrix of the Nisan-Wigderson polynomial and the concept of evaluation dimension, we are able to almost completely identify the structure of GNW . In particular we prove that any A 2 GNW is a product of diagonal and permutation matrices of certain kind that we call block-permuted permutation matrix. Finally, we give explicit examples of nontrivial block-permuted permutation matrices using the automorphisms of nite eld that establishes the richness of the discrete symmetries of the Nisan-Wigderson polynomial family. | en_US |

dc.language.iso | en_US | en_US |

dc.relation.ispartofseries | G28606 | en_US |

dc.subject | Nisan-Wigderson Polynomial | en_US |

dc.subject | Polynomial Evaluation Dimension | en_US |

dc.subject | Arithmetic Circuit Complexity | en_US |

dc.subject | Hessian - Polynomial | en_US |

dc.subject | Lie Algebra | en_US |

dc.subject | Hessian Matrix | en_US |

dc.subject.classification | Computer Science | en_US |

dc.title | Towards a Charcterization of the Symmetries of the Nisan-Wigderson Polynomial Family | en_US |

dc.type | Thesis | en_US |

dc.degree.name | MSc Engg | en_US |

dc.degree.level | Masters | en_US |

dc.degree.discipline | Faculty of Engineering | en_US |