Symbolic Listings as Computation
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910381169967104 |
|---|---|
| author | Sawczuk, Hamilton Gnang, Edinah |
| author_facet | Sawczuk, Hamilton Gnang, Edinah |
| contents | We propose an algebraic model of computation which formally relates symbolic listings, complexity of Boolean functions, and low depth arithmetic circuit complexity. In this model algorithms are arithmetic formula expressing symbolic listings of YES instances of Boolean functions, and computation is executed via partial differential operators. We consider the Chow rank of an arithmetic formula as a measure of complexity and establish the Chow rank of multilinear polynomials with totally non-overlapping monomial support. We also provide Chow rank non-decreasing transformations from sets of graphs to sets of functional graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_15885 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Symbolic Listings as Computation Sawczuk, Hamilton Gnang, Edinah Discrete Mathematics We propose an algebraic model of computation which formally relates symbolic listings, complexity of Boolean functions, and low depth arithmetic circuit complexity. In this model algorithms are arithmetic formula expressing symbolic listings of YES instances of Boolean functions, and computation is executed via partial differential operators. We consider the Chow rank of an arithmetic formula as a measure of complexity and establish the Chow rank of multilinear polynomials with totally non-overlapping monomial support. We also provide Chow rank non-decreasing transformations from sets of graphs to sets of functional graphs. |
| title | Symbolic Listings as Computation |
| topic | Discrete Mathematics |
| url | https://arxiv.org/abs/2402.15885 |