File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: A quadratic lower bound for the permanent and determinant problem over any characteristic ≠ 2

TitleA quadratic lower bound for the permanent and determinant problem over any characteristic ≠ 2
Authors
KeywordsArithmetic complexity
Determinant
Finite field
Permanent
Issue Date2008
Citation
Proceedings of the Annual ACM Symposium on Theory of Computing, 2008, p. 491-497 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 f 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 F[X]. Mignon and Ressayre (2004) [11] 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. Copyright 2008 ACM.
Persistent Identifierhttp://hdl.handle.net/10722/326757
ISSN
2023 SCImago Journal Rankings: 3.322

 

DC FieldValueLanguage
dc.contributor.authorCai, Jin Yi-
dc.contributor.authorChen, Xi-
dc.contributor.authorLi, Dong-
dc.date.accessioned2023-03-31T05:26:18Z-
dc.date.available2023-03-31T05:26:18Z-
dc.date.issued2008-
dc.identifier.citationProceedings of the Annual ACM Symposium on Theory of Computing, 2008, p. 491-497-
dc.identifier.issn0737-8017-
dc.identifier.urihttp://hdl.handle.net/10722/326757-
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 f 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 F[X]. Mignon and Ressayre (2004) [11] 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. Copyright 2008 ACM.-
dc.languageeng-
dc.relation.ispartofProceedings of the Annual ACM Symposium on Theory of Computing-
dc.subjectArithmetic complexity-
dc.subjectDeterminant-
dc.subjectFinite field-
dc.subjectPermanent-
dc.titleA quadratic lower bound for the permanent and determinant problem over any characteristic ≠ 2-
dc.typeConference_Paper-
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1145/1374376.1374446-
dc.identifier.scopuseid_2-s2.0-57049134175-
dc.identifier.spage491-
dc.identifier.epage497-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats