Skip to main navigation Skip to search Skip to main content

Determinantal complexities and field extensions

  • National University of Singapore
  • Chinese Academy of Sciences

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

Let double-struck F be a field of characteristic ≠ 2. The determinantal complexity of a polynomial P ∈ double-struck F[x1,..., x n] is defined as the smallest size of a matrix M whose entries are linear polynomials of xi 's over double-struck F, such that P = det(M) as polynomials in double-struck F[x1,..., xn]. To determine the determinantal complexity of the permanent polynomial is a long-standing open problem. Let double-struck K be an extension field of double-struck F; then P can be viewed as a polynomial over double-struck K. We are interested in the comparison between the determinantal complexity of P over double-struck K (denoted as dcdouble-struck K(P))), and that of P over double-struck F (denoted as dcdouble-struck F(P). It is clear that dcdouble-struck K(P) ≤, dcdouble-struck F(P) and the question is whether strict inequality can happen. In this note we consider polynomials defined over ℚ. For P = x12 + ⋯ + xn2, there exists a constant multiplicative gap between dc(P) and dc(P): we prove dc (P) ≥ n while ⌈n/2⌉ + 1 ≥ dc (P). We also consider additive constant gaps: (1) there exists a quadratic polynomial Q ∈ ℚ [x, y], such that dcℚ-(Q) = 3 and ; (2) there exists a cubic polynomial C ∈ ℚ[x, y] with a rational zero, such that dc(C) = 4 and dcℚ-(C) = 3. For additive constant gaps, geometric criteria are presented to decide when dc = dcℚ-.

Original languageEnglish
Title of host publicationAlgorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings
Pages119-129
Number of pages11
DOIs
StatePublished - 2013
Event24th International Symposium on Algorithms and Computation, ISAAC 2013 - Hong Kong, China
Duration: Dec 16 2013Dec 18 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8283 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference24th International Symposium on Algorithms and Computation, ISAAC 2013
Country/TerritoryChina
CityHong Kong
Period12/16/1312/18/13

Fingerprint

Dive into the research topics of 'Determinantal complexities and field extensions'. Together they form a unique fingerprint.

Cite this