8 papers · 1 filter
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…
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…
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…