The research articles that I have co-authored are given below in reverse chronological order.
with Pranjal Dutta, Christian Ikenmeyer, Harshil Mittal, Saraswati Girish Nanoti and Dhara Thakkar.
A polynomial can be approximately expressed as a sequence of 2x2 matrices containing only variables and field elements if some entry in the product of those matrices is approximately that polynomial. In this paper, we show that for any polynomial p, we can approximately express some power of p using a sequence of 2x2 matrices.
with Anant Kumar, Suchismita Mishra, and Aditi Sethia
A pattern is a small graph that we want to find in a larger graph called the host graph. The state of the art algorithms for finding and counting patterns in graphs are oblivious to the number of edges in the host graph. We introduce two natural parameters on the pattern and show that we can obtain asymptotic improvements on sparse host graphs for many patterns. For certain simple classes of patterns, we also characterize, using forbidden induced minors, patterns that can be detected or counted easily.
with Anurag Pandey and Nitin Saurabh
Determinants of symbolic matrices are a very important sequence of polynomials in engineering. From a theoretical perspective, any polynomial with a small algebraic formula can be expressed as a projection of the determinant of a small matrix that contains only variables and constants. However, determinants of symbolic matrices are believed to be uncomputable by small formulas. In this paper, we look at determinants of symbolic matrices with low bandwidth. We show that such determinants can still express all formulas and can be computed by small formulas. We also exhibit very simple polynomials, namely Narayana's cows polynomials and Padovan polynomials that have this property.
with Christian Ikenmeyer and Nitin Saurabh
Karchmer-Wigderson games are two-player, collaborative, communication games where two people with a part of the input try to compute a function at the whole input while minimizing communication. Variants of this game characterize Boolean and monotone formula complexity. Using this relationship, we can obtain good lower bounds for monotone formulas. However, we do not know how to obtain good lower bounds for Boolean formulas. In this work, we introduce a variant of this game that is related to hazard-free formulas and show that it acts as a bridge between the monotone and the Boolean game. Therefore, using this game, we can prove lower bounds that was not possible using the monotone game. As an application, we examine hazard-free formula complexity of the multiplexer function.
With Anurag Pandey and Rahul C S
Graph homomorphism polynomials are polynomials that enumerate graph homomorphisms from a small, fixed pattern graph to large cliques. These polynomials have wide-ranging applications in graph pattern detection and counting. Monotone arithmetic circuits (circuits that do not use cancellation) are usually used to efficiently compute these polynomials. We completely characterize the complexity of all homomorphism polynomials in all three major monotone models (circuits, branching programs, and formulas) in terms of well-known structural graph parameters.
With Nitin Saurabh
Detecting whether a given circuit has a logic hazard is a fundamental problem in logic circuit design. The best algorithm for this problem is due to Eichelberger (1965) and runs in exponential time. In this paper, we show that if a widely believed complexity theoretic hypothesis called the strong exponential time hypothesis is true, Eichelberger's algorithm is asymptotically optimal. We also show that there is a polynomial time algorithm that solves this problem in practice if the circuit is in CNF or DNF.
with Markus Bläser and Karteek Sreenivasaiah
We show that efficient constructions of circuits for computing homomorphism polynomials for small pattern graphs can be used to solve the induced subgraph isomorphism problem for small pattern graphs. Our main result is that there exists a k-vertex pattern graph that has a faster detection algorithm than the one for k-clique. This answers an open problem from 1985.
with Christian Ikenmeyer, Christoph Lenzen, Vladimir Lysikov, Andrey Mokhov, and Karteek Sreenivasaiah
A circuit is said to have a hazard if given an input where some of the bits are unstable, it outputs an unstable value even if the value of the function is determined by the stable inputs. In 1957, Huffman asked whether given a circuit that has hazards, is it possible to obtain a hazard-free circuit that computes the same function without adding too many gates? In this paper, we show that this is impossible. The result is obtained using a newly discovered connection between hazard-free computation and monotone computation.
with Jayalal Sarma and K.S. Sunil
The comparator circuit model characterizes the complexity of many interesting problems such as the stable matching problem. Intuitively, this circuit model appears to be slightly less powerful than arbitrary polynomial time computation. In this paper, we study generalizations of the comparator circuit model that characterizes polynomial time computation. We also show that certain natural restrictions on the comparator circuit model enables us to characterize space bounded computation.
with Jayalal Sarma and Saurabh Sawlani
The reversible pebbling game, played on directed acyclic graphs, was invented to determine storage requirements of reversible computation that follows a specific algorithm. It was known that this pebbling game is equivalent to many other pebbling games invented to study other computational models. In this paper, we relate reversible pebbling to a purely structural property of graphs called edge-rank coloring. Many interesting structural and algorithmic results follow from this discovery.
with Jayalal Sarma and K.S. Sunil
We look at a generalization of the graph reachability problem where all edges are labelled from an alphabet and paths are valid only if the string yielded by the path belongs to a language.
With Kristoffer Arnsfelt Hansen, Jayalal Sarma, Sven Skyum, and Navid Talebanfard
We show that constant depth circuits can decide the perfect matching, 3-coloring, and disjoint paths problem on graphs where the vertices can be arranged on a constant width grid and edges exist only between consecutive layers in the grid.
with Jayalal Sarma
We look at computational models that solve a problem where the dependence between data values can be described using a complete binary tree and the root of the tree is the final output. We show that even with the help of non-determinism, such models require large storage to solve the problem.
I did my PhD at IIT Madras, India. Jayalal Sarma was my PhD advisor. You can download my PhD thesis from here.