direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

There is no English translation for this web page.

Ehemalige Mitarbeiter

Dr. Christian Ikenmeyer


University of Liverpool
Department of Computer Science
Ashton Building, Office 311
Ashton Street, Liverpool, L69 3BX
United Kingdom
Persönliche Homepage

Publikationen in der Arbeitsgruppe

Binary determinantal complexity
Citation key HI-Binary-Determinantal-Complexity
Author Jesko Hüttenhain and Christian Ikenmeyer
Pages 559 - 573
Year 2016
ISSN 0024-3795
DOI 10.1016/j.laa.2016.04.027
Journal Linear Algebra and its Applications
Volume 504
Month 09
Abstract 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.
Link to publication Link to original publication Download Bibtex entry

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions

This site uses Matomo for anonymized webanalysis. Visit Data Privacy for more information and opt-out options.