On the Expressive Power of Read-Once Determinants

DOI10.1007/978-3-319-22177-9_8zbMATH Open1380.68455arXiv1508.06511OpenAlexW1941738311MaRDI QIDQ2947872FDOQ2947872

Authors: N. R. Aravind, Pushkar S. Joglekar 

Publication date: 29 September 2015

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

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.

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

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

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)

Cites Work

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

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)