Here's the list of research articles that I have co-authored in reverse chronological order.
Graph homomorphism polynomials: Algorithms and complexity (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.
On the complexity of detecting hazards (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 time O(s.3^n) where s is the size of the circuit and n is the number of distinct input variables to the circuit. In this paper, we show that if a widely believed complexity theoretic hypothesis called the strong exponential time hypothesis is true, this algorithm is 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.
Graph pattern polynomials (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.
On the complexity of hazard-free circuits (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.
Comparator circuits over finite bounded posets (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.
Pebbling meets coloring: Reversible pebble game on trees (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.
On the complexity of L-reachability (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.
Circuit complexity of properties of graphs with constant planar cutwidth (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.
Pebbling, entropy and branching program size lower bounds (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 here.