Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials
Authors
Balagopal Komarath
Rohit Narayanan
Abstract
We characterize the monotone bounded depth formula complexity for graph homomorphism and colored isomorphism polynomials using a graph parameter called the cost of bounded product depth baggy elimination tree. Using this characterization, we show an almost optimal separation between monotone circuits and monotone formulas using constant-degree polynomials for all fixed product depths, and an almost optimal separation between monotone formulas of product depths $Δ$ and $Δ$ + 1 for all $Δ$ $\ge$ 1.
