**Assistant Professor**

Department of Computer Science and Engineering

IIT Guwahati

Guwahati - 781039

Assam, India

**Title :**Computations of Binomial Ideals [pdf]**Supervisor :**Shashank K Mehta.**Institute :**Department of Computer Science and Technology, Indian Institute of Technology Kanpur, 2012.**Abstract :**Computation of the saturation of a pure difference binomial ideal is computationally at least as hard as solving an integer program. Computation of the saturation of a (general) binomial ideal, radical of a binomial ideal, primary decomposition and cellular decomposition of a binomial ideal etc. have worse time complexities. All these computations involve repeated Gröbner bases computation. We present a technique where the ideal is projected to polynomial rings of lesser variables in successive steps. Thereby the Gröbner basis computation becomes faster. We further refine this reduction technique and using this we propose a divide and conquer technique which is shown to be applicable in the computation of a variety of derived ideals associated with the given binomial ideal.

**A Divide and Conquer Method to Compute Binomial Ideals**[Preprint]

with Shashank K Mehta.**Abstract :**A binomial is a polynomial with at most two terms. In this paper, we give a*divide-and-conquer*strategy to compute binomial ideals. This work is a generalization of the work done by the authors in ISAAC 2009 and COCOA 2011 and is motivated by the fact that any algorithm to compute binomial ideals spends a significant amount of time computing Gröbner basis and that Gröbner basis computation is very sensitive to the number of variables in the ring. The divide and conquer strategy breaks the problem into subproblems in rings of lesser number of variables than the original ring. We apply the framework on four problems - radicals, cellular decomposition, prime decomposition and saturation of binomial ideals.

**A Saturation algorithm for homogeneous binomial ideals**

with Shashank K Mehta.**Abstract :**Let*k[x*be a polynomial ring in_{1}, … , x_{n}]*n*variables, and let*I ⊂ k[x*be a homogeneous binomial ideal. We describe a fast algorithm to compute the saturation,_{1}, … , x_{n}]*I : (x*. In the special case when_{1}… x_{n})^{∞}*I*is a toric ideal, we present some preliminary results comparing our algorithm with*Project and Lift*by Hemmecke and Malkin.**Full Paper :**In the proceedings of the 5th Conference on Combinatorial Optimization and Applications(COCOA), 2011, Lecture Notes in Computer Science(LNCS), Volume 6831, pp. 357-371, 2011. [pdf]**Extended Abstract :**In the poster session of the 36th International Symposium on Symbolic and Algebraic Computation(ISSAC), 2011. Also appeared in ISSAC 2011 Poster Abstracts. Communications in Computer Algebra, 45(2):107--142, 2011. [pdf]**Poster :**As presented in the poster session of the 36th International Symposium on Symbolic and Algebraic Computation(ISSAC), 2011. [pdf]

**Generalized reduction to compute Toric ideals.**

with Shashank K Mehta.**Abstract :**Toric ideals have many applications including solving integer programs. Several algorithms for computing the toric ideal of an integer matrix are available in the literature. Since it is an NP hard problem the present approaches can only solve relatively small problems. We propose a new approach which improves upon a well known saturation technique.**Journal :**As an invited paper in Discrete Mathematics, Algorithms and Applications (DMAA), 1:45-59, 2010. [pdf]**Conference :**In the proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC), 2009. [pdf]

**Simpler algorithm for estimating frequency moments of data streams.**

with Lakshminath Bhuvanagiri, Sumit Ganguly and Chandan Saha**Abstract :**The problem of estimating the*k*frequency moment^{th}*F*over a data stream by looking at the items exactly once as they arrive was posed in [1, 2]. A succession of algorithms have been proposed for this problem [1, 2, 6, 8, 7]. Recently, Indyk and Woodruff [11] have presented the first algorithm for estimating_{k}*F*, for_{k}*k > 2*, using space*O(n*, matching the space lower bound (up to poly-logarithmic factors) for this problem [1, 2, 3, 4, 13] (^{1-2/k})*n*is the number of distinct items occurring in the stream.) In this paper, we present a simpler 1-pass algorithm for estimating*F*._{k}**Conference :**In the Proc. of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006. [pdf]

**Practical Algorithms for Tracking Database Join Sizes.**

with Sumit Ganguly and Chandan Saha**Abstract :**We present novel algorithms for estimating the size of the natural join of two data streams that have efficient update processing times and provide excellent quality of estimates.**Conference :**In the Proc. of the 25th on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2005. [ps]

**Polynomial Irreducibility Testing through Minkowski Summand Computation.**

with Shashank K Mehta.**Abstract :**In this paper, we address the problem of deciding absolute irreduciblity of multivariate polynomials. Our work has been motivated by a recent work due to Gao et. al. [1,2,3] where they have considered the problem for bivariate polynomials by studying the integral decomposability of polygons in the sense of Minkowski sum. We have generalized their result to polynomials containing arbitrary number of variables by reducing the problem of Minkowski decomposability of an integer (lattice) polytope to an integer linear program. We also present experimental results of computation of Minkowski decomposition using this integer program.**Conference :**In the Proc. of the 20th Canadian Conference on Computational Geometry (CCCG), 2008. [pdf]

- Microsoft Research India PhD Fellow 2006.
- The SAARC/IAESTE-Japan Academic Internship Program 2008.

Introduction to Computing (CS101), Semester II, 2011-2012.

Theoretical Foundations of Computer Science (CS205M), Semester I, 2012-2013.

Formal Languages and Automata Theory(CS203), Semester II, 2012-2013.

Theoretical Foundations of Computer Science(CS301), Semester I, 2013-2014.