Talks - Fall 2017

Ecponential Polynomials

Title

Speaker

Date

Time

Venue

Abstract

On the Complexity of Hilbert's Nullstellensatz over Positive Characteristic

Ashish Dwivedi

4Aug (Fri), 2017

11am to 11:45am

KD101

An important problem in computational algebraic geometry is to decide if there exists a common solution of a given set of multivariate polynomials over an algebraically closed field. This decision problem is also known as Hilbert's Nullstellensatz (HN). The complexity of HN over arbitrary characteristic fields is known to be in PSPACE. Over zero characteristic, this problem is shown to be in AM by Koiran (1996) under the assumption that "Generalized Riemann Hypothesis" is true. We are interested in HN over positive characteristic fields.

We divide the problem in two cases: first, when the dimension of the given system of polynomial equations is positive and second, when the dimension of the given system of polynomial equations is zero.

In positive dimensional case, we solve three special cases in NP. First case is when the zero set of the given affine or projective system is either empty or absolutely irreducible. Second when the zero set of given affine system is either empty or one of its absolutely irreducible component of same dimension is definable in the coefficient field of the system. Third case is when the zero set of given projective system is either empty or one of its absolutely irreducible component of same dimension is definable in the coefficient field of the system such that the product of the degree of polynomials defining the component, is not more than the product of the degree of the given polynomials.

In zero dimensional case, we construct an affine system which have no small zeros. Further, we give a reduction of affine zero dimensional systems to affine positive dimensional systems making general affine positive dimensional case at least as hard as affine zero dimensional case.

ALL SESSIONS


Contact

Image

Sumanta Ghosh

Head Co-ordinator

Image

Rajendra Kumar

Co-ordinator

Image

Mahesh S R

Co-ordinator