Symmetric Arithmetic Circuits
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2020
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909076842086400 |
|---|---|
| author | Dawar, Anuj Wilsenach, Gregory |
| author_facet | Dawar, Anuj Wilsenach, Gregory |
| contents | We introduce symmetric arithmetic circuits, i.e. arithmetic circuits with a natural symmetry restriction. In the context of circuits computing polynomials defined on a matrix of variables, such as the determinant or the permanent, the restriction amounts to requiring that the shape of the circuit is invariant under simultaneous row and column permutations of the matrix. We establish unconditional exponential lower bounds on the size of any symmetric circuit for computing the permanent. In contrast, we show that there are polynomial-size symmetric circuits for computing the determinant over fields of characteristic zero. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2002_06451 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Symmetric Arithmetic Circuits Dawar, Anuj Wilsenach, Gregory Computational Complexity Discrete Mathematics Logic in Computer Science F.1.3; F.2.1 We introduce symmetric arithmetic circuits, i.e. arithmetic circuits with a natural symmetry restriction. In the context of circuits computing polynomials defined on a matrix of variables, such as the determinant or the permanent, the restriction amounts to requiring that the shape of the circuit is invariant under simultaneous row and column permutations of the matrix. We establish unconditional exponential lower bounds on the size of any symmetric circuit for computing the permanent. In contrast, we show that there are polynomial-size symmetric circuits for computing the determinant over fields of characteristic zero. |
| title | Symmetric Arithmetic Circuits |
| topic | Computational Complexity Discrete Mathematics Logic in Computer Science F.1.3; F.2.1 |
| url | https://arxiv.org/abs/2002.06451 |