5 papers
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…
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…
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…