Uniformity within Parameterized Circuit Classes
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914032659726336 |
|---|---|
| author | Hegeman, Steef Martens, Jan Laarman, Alfons |
| author_facet | Hegeman, Steef Martens, Jan Laarman, Alfons |
| contents | We study uniformity conditions for parameterized Boolean circuit families. Uniformity conditions require that the infinitely many circuits in a circuit family are in some sense easy to construct from one shared description. For shallow circuit families, logtime-uniformity is often desired but quite technical to prove. Despite that, proving it is often left as an exercise for the reader -- even for recently introduced classes in parameterized circuit complexity, where uniformity conditions have not yet been explicitly studied. We formally define parameterized versions of linear-uniformity, logtime-uniformity, and FO-uniformity, and prove that these result in equivalent complexity classes when imposed on $\text{para-}\textsf{AC}^0$ and $\text{para-}\textsf{AC}^{0\uparrow}$. Overall, we provide a convenient way to verify uniformity for shallow parameterized circuit classes, and thereby substantiate claims of uniformity in the literature. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_09657 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Uniformity within Parameterized Circuit Classes Hegeman, Steef Martens, Jan Laarman, Alfons Computational Complexity Logic in Computer Science We study uniformity conditions for parameterized Boolean circuit families. Uniformity conditions require that the infinitely many circuits in a circuit family are in some sense easy to construct from one shared description. For shallow circuit families, logtime-uniformity is often desired but quite technical to prove. Despite that, proving it is often left as an exercise for the reader -- even for recently introduced classes in parameterized circuit complexity, where uniformity conditions have not yet been explicitly studied. We formally define parameterized versions of linear-uniformity, logtime-uniformity, and FO-uniformity, and prove that these result in equivalent complexity classes when imposed on $\text{para-}\textsf{AC}^0$ and $\text{para-}\textsf{AC}^{0\uparrow}$. Overall, we provide a convenient way to verify uniformity for shallow parameterized circuit classes, and thereby substantiate claims of uniformity in the literature. |
| title | Uniformity within Parameterized Circuit Classes |
| topic | Computational Complexity Logic in Computer Science |
| url | https://arxiv.org/abs/2509.09657 |