Show simple item record

dc.contributor.advisorSaha, Chandan
dc.contributor.authorGupta, Nikhil
dc.date.accessioned2018-07-09T13:29:26Z
dc.date.accessioned2018-07-31T04:39:20Z
dc.date.available2018-07-09T13:29:26Z
dc.date.available2018-07-31T04:39:20Z
dc.date.issued2018-07-09
dc.date.submitted2017
dc.identifier.urihttp://etd.iisc.ac.in/handle/2005/3802
dc.identifier.abstracthttp://etd.iisc.ac.in/static/etd/abstracts/4673/G28606-Abs.pdfen_US
dc.description.abstractUnderstanding 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.isoen_USen_US
dc.relation.ispartofseriesG28606en_US
dc.subjectNisan-Wigderson Polynomialen_US
dc.subjectPolynomial Evaluation Dimensionen_US
dc.subjectArithmetic Circuit Complexityen_US
dc.subjectHessian - Polynomialen_US
dc.subjectLie Algebraen_US
dc.subjectHessian Matrixen_US
dc.subject.classificationComputer Scienceen_US
dc.titleTowards a Charcterization of the Symmetries of the Nisan-Wigderson Polynomial Familyen_US
dc.typeThesisen_US
dc.degree.nameMSc Enggen_US
dc.degree.levelMastersen_US
dc.degree.disciplineFaculty of Engineeringen_US


Files in this item

This item appears in the following Collection(s)

Show simple item record