File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Quadratic lower bound for permanent Vs. Determinant in any characteristic

TitleQuadratic lower bound for permanent Vs. Determinant in any characteristic
Authors
KeywordsArithmetic complexity
Determinant
Finite field
Permanent
Issue Date2010
Citation
Computational Complexity, 2010, v. 19, n. 1, p. 37-56 How to Cite?
AbstractIn Valiant's theory of arithmetic complexity, the classes VP and VNP are analogs of P and NP. A fundamental problem concerning these classes is the Permanent and Determinant Problem: Given a field of characteristic ≠ 2, and an integer n, what is the minimum m such that the permanent of an n × n matrix X = (xij) can be expressed as a determinant of an m × m matrix, where the entries of the determinant matrix are affine linear functions of xij 's, and the equality is in [X]. Mignon and Ressayre (2004) proved a quadratic lower bound m = Ω(n2) for fields of characteristic 0. We extend the Mignon-Ressayre quadratic lower bound to all fields of characteristic ≠ 2. © 2010 Birkhäuser/Springer Basel.
Persistent Identifierhttp://hdl.handle.net/10722/326802
ISSN
2023 Impact Factor: 0.7
2023 SCImago Journal Rankings: 0.453
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorCai, Jin Yi-
dc.contributor.authorChen, Xi-
dc.contributor.authorLi, Dong-
dc.date.accessioned2023-03-31T05:26:37Z-
dc.date.available2023-03-31T05:26:37Z-
dc.date.issued2010-
dc.identifier.citationComputational Complexity, 2010, v. 19, n. 1, p. 37-56-
dc.identifier.issn1016-3328-
dc.identifier.urihttp://hdl.handle.net/10722/326802-
dc.description.abstractIn Valiant's theory of arithmetic complexity, the classes VP and VNP are analogs of P and NP. A fundamental problem concerning these classes is the Permanent and Determinant Problem: Given a field of characteristic ≠ 2, and an integer n, what is the minimum m such that the permanent of an n × n matrix X = (xij) can be expressed as a determinant of an m × m matrix, where the entries of the determinant matrix are affine linear functions of xij 's, and the equality is in [X]. Mignon and Ressayre (2004) proved a quadratic lower bound m = Ω(n2) for fields of characteristic 0. We extend the Mignon-Ressayre quadratic lower bound to all fields of characteristic ≠ 2. © 2010 Birkhäuser/Springer Basel.-
dc.languageeng-
dc.relation.ispartofComputational Complexity-
dc.subjectArithmetic complexity-
dc.subjectDeterminant-
dc.subjectFinite field-
dc.subjectPermanent-
dc.titleQuadratic lower bound for permanent Vs. Determinant in any characteristic-
dc.typeArticle-
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/s00037-009-0284-2-
dc.identifier.scopuseid_2-s2.0-77949314433-
dc.identifier.volume19-
dc.identifier.issue1-
dc.identifier.spage37-
dc.identifier.epage56-
dc.identifier.eissn1420-8954-
dc.identifier.isiWOS:000275427200002-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats