5 citations · 11 across the 11 of their papers we have counts for
16 papers
Faster Algorithms for Finding Small Induced Patterns in Sparse Host Graphs
Priyanshi Agrawal, Balagopal Komarath
We study algorithms for detecting induced subgraphs corresponding to fixed pattern graphs in host graphs. We show that at least five of the 21 connected graphs on five vertices can…
VP, VNP and Algebraic Branching Programs over Min-Plus Semirings
Balagopal Komarath, Harshil Mittal, Jayalal Sarma
Arithmetic circuit complexity studies the complexity of computing polynomials using only arithmetic operations such as addition, multiplication, subtraction, and division. Polynomi…
Counting Patterns in Degenerate Graphs in Constant Space
Balagopal Komarath, Anant Kumar, Akash Pareek
For a fixed pattern graph, we study the algorithmic complexity of counting homomorphisms, subgraph isomorphisms, and induced subgraph isomorphisms into an -vertex, -degenerat…
Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials
Balagopal Komarath, Rohit Narayanan
We introduce baggy elimination trees, a novel graph decomposition that generalises the classical elimination trees underlying treedepth, and use them to give a complete characteris…
Sensitivity and Query Complexity under Uncertainty
Deepu Benson, Balagopal Komarath, Nikhil Mande +3
In this paper, we study the query complexity of Boolean functions in the presence of uncertainty, motivated by parallel computation with an unlimited number of processors where inp…
Hazard-free Decision Trees
Deepu Benson, Balagopal Komarath, Jayalal Sarma +1
Decision trees are one of the most fundamental computational models for computing Boolean functions . It is well-known that the depth and size of d…
Finding and Counting Patterns in Sparse Graphs
Balagopal Komarath, Anant Kumar, Suchismita Mishra +1
We consider algorithms for finding and counting small, fixed graphs in sparse host graphs. In the non-sparse setting, the parameters treedepth and treewidth play a crucial role in…
Karchmer-Wigderson Games for Hazard-free Computation
Christian Ikenmeyer, Balagopal Komarath, Nitin Saurabh
We present a Karchmer-Wigderson game to study the complexity of hazard-free formulas. This new game is both a generalization of the monotone Karchmer-Wigderson game and an analog o…
Graph Homomorphism Polynomials: Algorithms and Complexity
Balagopal Komarath, Anurag Pandey, C. S. Rahul
We study homomorphism polynomials, which are polynomials that enumerate all homomorphisms from a pattern graph to -vertex graphs. These polynomials have received a lot of at…
On the complexity of detecting hazards
Balagopal Komarath, Nitin Saurabh
Detecting and eliminating logic hazards in Boolean circuits is a fundamental problem in logic circuit design. We show that there is no time algorithm…
Graph Pattern Polynomials
Markus Bläser, Balagopal Komarath, Karteek Sreenivasaiah
We study the time complexity of induced subgraph isomorphism problems where the pattern graph is fixed. The earliest known example of an improvement over trivial algorithms is by I…
On the complexity of hazard-free circuits
Christian Ikenmeyer, Balagopal Komarath, Christoph Lenzen +3
The problem of constructing hazard-free Boolean circuits dates back to the 1940s and is an important problem in circuit design. Our main lower-bound result unconditionally shows th…
On the Complexity of L-reachability
Balagopal Komarath, Jayalal Sarma, K. S. Sunil
We initiate a complexity theoretic study of the language based graph reachability problem (L-REACH) : Fix a language L. Given a graph whose edges are labeled with alphabet symbols…
Pebbling Meets Coloring: Reversible Pebble Game On Trees
Balagopal Komarath, Jayalal Sarma, Saurabh Sawlani
The reversible pebble game is a combinatorial game played on rooted DAGs. This game was introduced by Bennett (1989) motivated by applications in designing space efficient reversib…
Comparator Circuits over Finite Bounded Posets
Balagopal Komarath, Jayalal Sarma, K. S. Sunil
Comparator circuit model was originally introduced by Mayr and Subramanian (1992) (and further studied by Cook, Filmus and Le (2012)) to capture problems which are not known to be…
Pebbling, Entropy and Branching Program Size Lower Bounds
Balagopal Komarath, Jayalal Sarma M. N
We contribute to the program of proving lower bounds on the size of branching programs solving the Tree Evaluation Problem introduced by Cook et. al. (2012). Proving a super-polyno…