5 citations · 11 across the 11 of their papers we have counts for
4 papers · 1 filter
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…