Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914138787151872 |
|---|---|
| author | Komarath, Balagopal Narayanan, Rohit |
| author_facet | Komarath, Balagopal Narayanan, Rohit |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_03388 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials Komarath, Balagopal Narayanan, Rohit Computational Complexity 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. |
| title | Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2511.03388 |