On the Expressive Power of Read-Once Determinants

DOI10.1007/978-3-319-22177-9_8MaRDI QIDQ2947872zbMATH OpenOpenAlexFDO

Authors N. R. Aravind, Pushkar S. Joglekar

Publication date 29 September 2015

Published in Fundamentals of Computation Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.06511

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Determinants, permanents, traces, other special matrix functions (15A15)

Abstract: We introduce and study the notion of read-$k$ projections of the determinant: a polynomial $finmathbbF[x_1,ldots,x_n]$ is called a {it read-$k$ projection of determinant} if $f=det(M)$, where entries of matrix $M$ are either field elements or variables such that each variable appears at most $k$ times in $M$. A monomial set $S$ is said to be expressible as read-$k$ projection of determinant if there is a read-$k$ projection of determinant $f$ such that the monomial set of $f$ is equal to $S$. We obtain basic results relating read-$k$ determinantal projections to the well-studied notion of determinantal complexity. We show that for sufficiently large $n$, the $nimesn$ permanent polynomial $Per{m}_n$ and the elementary symmetric polynomials of degree $d$ on $n$ variables $S_n^d$ for $2leqdleqn-2$ are not expressible as read-once projection of determinant, whereas $mon(Per{m}_n)$ and $mon(S_n^d)$ are expressible as read-once projections of determinant. We also give examples of monomial sets which are not expressible as read-once projections of determinant.

Recommendations

• Combinatorial characterization of read-once formulae
• On the shrinkage exponent for read-once formulae
• Read-Once Functions Revisited and the Readability Number of a Boolean Function
• An improvement on the complexity of factoring read-once Boolean functions
• Characterizing arithmetic read-once formulae
• On the complexity of computing determinants
• On the expressivity of linear recursion schemes
• On interpolating arithmetic read-once formulas with exponentiation
• Exact Identification of Read-Once Formulas Using Fixed Points of Amplification Functions
• scientific article; zbMATH DE number 859790

Cites work

• scientific article; zbMATH DE number 2151804 (Why is no real title available?)
• scientific article; zbMATH DE number 5485561 (Why is no real title available?)
• An algebraic matching algorithm
• Depth-3 arithmetic circuits over fields of characteristic zero
• Deterministic black-box identity testing \(\pi\)-ordered algebraic branching programs
• Deterministic polynomial time algorithms for matrix completion problems
• Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields.
• Feasible arithmetic computations: Valiant's hypothesis
• Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials
• Lower bounds on arithmetic circuits via partial derivatives
• Some Exact Complexity Results for Straight-Line Computations over Semirings

Cited in

(3)

• Characterizing arithmetic read-once formulae
• Affine projections of polynomials (extended abstract)
• On the complexity of the permanent in various computational models

This page was built for publication: On the Expressive Power of Read-Once Determinants

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947872)