2 citations · 2 across the 7 of their papers we have counts for
Showing 2025 · cs.CCShow all
3 papers · 2 filters
cs.CC2025
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…
cs.CC2025
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…
cs.CC2025
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…