Research Summary

The ultimate goal of compuational complexity theory is to characterize the power and limitations of general computational models such as Turing machines, Boolean circuits, and algebraic circuits. However, experience has shown that this might be too difficult in the short-term. One approach to handle this difficulty is to study the relative complexity of problems. For example, instead of proving that a problem does not have an efficient algorithm, we settle for proving that it is NP-complete. Another approach to handle the difficulty is to study computational models that are not general, but restricted in some useful way. My research focus is on this approach. A key aspect of my research is focus on restricted, yet useful computational models.

Boolean circuits form the basis for all modern (non-quantum) processors. However, this is a general model and proving any non-trivial and interesting lower bound has remained elusive. Hazard-free circuits are a restricted form of Boolean circuits where we demand that the circuit must behave well even in the presence of unstable voltages. This model is interesting due to its real-world applicability. I have co-authored multiple papers that show tight lower bounds against hazard-free circuits for practical problems such as matrix multiplication, determinant, maximum matching, and multiplexer.

My other main area of interest is the connection between structural graph theory and algebraic circuits. An algebraic circuit is a computational model for polynomials that is only allowed to use addition and multiplication. Many state-of-the art algorithms for graph pattern finding and counting rely on construction of algebraic circuits for certain polynomials as an intermediate step. I have co-authored multiple papers that design state-of-the art algorithms for these problems by improving those constructions or utilizing existing constructions in novel ways. I have also co-authored multiple papers that show limitations of these approaches by showing that their efficiency is linked, and therefore limited, by well-known structural graph parameters.