Show simple item record

dc.contributor.advisorDukkipati, Ambedkar
dc.contributor.authorPrabhanjan, V A
dc.date.accessioned2013-06-14T10:24:45Z
dc.date.accessioned2018-07-31T04:38:22Z
dc.date.available2013-06-14T10:24:45Z
dc.date.available2018-07-31T04:38:22Z
dc.date.issued2013-06-14
dc.date.submitted2011
dc.identifier.urihttp://etd.iisc.ac.in/handle/2005/2056
dc.identifier.abstracthttp://etd.iisc.ac.in/static/etd/abstracts/2652/G24951-Abs.pdfen_US
dc.description.abstractThe theory of Grobner bases has garnered the interests of a large number of researchers in computational algebra due to its applications not only in mathematics but also in areas like control systems, robotics, cryptography to name a few. It is well known that the computation of Grobner bases takes time doubly exponential in the number of indeterminates rendering it impractical in all but a few places.The current known algorithms for Grobner bases depend on the term order over which Grobner bases is computed. In this thesis, we study computational complexity of some problems in computational ideal theory. We also study the algebraic formulation of combinatorial optimization problems. Gritzmann and Sturmfels (1993) posed the following question: Given a set of generators, decide whether it is a Gr¨obner bases with respect to some term order. This problem, termed as the Grobner Basis Detection(GBD)problem, was introduced as an application of Minkowski addition of polytopes. It was shown by Sturmfels and Wiegelmann (1997) that GBD is NP-hard. We study the problem for the case of zero-dimensional ideals and show that the problem is hard even in this special case. We study the detection problem in the case of border bases which are an alternative to Grobner bases in the case of zero dimensional ideals. We propose the Border Basis Detection(BBD) problem which is defined as follows: Given a set of generators of an ideal, decide whether that set of generators is a border basis of the ideal with respect to some order ideal. It is shown that BBD is NP-complete. We also formulate the rainbow connectivity problem as a system of polynomial equations such that solving the polynomial system yields a solution to it. We give an alternate formulation of the rainbow connectivity problem as a membership problem in polynomial ideals.en_US
dc.language.isoen_USen_US
dc.relation.ispartofseriesG24951en_US
dc.subjectComputational Algebraen_US
dc.subjectGrobner Basesen_US
dc.subjectBorder Basesen_US
dc.subjectBorder Basis Detection (BBD)en_US
dc.subjectComputational Complexityen_US
dc.subjectRainbow Connectivityen_US
dc.subjectGrober Basis Detection (GBD)en_US
dc.subjectPolynomial Equationsen_US
dc.subject.classificationComputer Scienceen_US
dc.titleOn The Complexity Of Grobner Basis And Border Basis Detectionen_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