Inhalt des Dokuments
Publikationen in der Arbeitsgruppe
| Zitatschlüssel | HI-Binary-Determinantal-Complexity |
|---|---|
| Autor | Jesko Hüttenhain and Christian Ikenmeyer |
| Seiten | 559 - 573 |
| Jahr | 2016 |
| ISSN | 0024-3795 |
| DOI | 10.1016/j.laa.2016.04.027 |
| Journal | Linear Algebra and its Applications |
| Jahrgang | 504 |
| Monat | 09 |
| Zusammenfassung | We prove that for writing the 3 by 3 permanent polynomial as a determinant of a matrix consisting only of zeros, ones, and variables as entries, a 7 by 7 matrix is required. Our proof is computer based and uses the enumeration of bipartite graphs. Furthermore, we analyze sequences of polynomials that are determinants of polynomially sized matrices consisting only of zeros, ones, and variables. We show that these are exactly the sequences in the complexity class of constant free polynomially sized (weakly) skew circuits. |
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe
Hilfsfunktionen
- Schriftgröße:
