Cancellation is exponentially powerful for computing the determinant

DOI10.1016/S0020-0190(97)00069-0zbMath1337.68137MaRDI QIDQ287054

Rimli Sengupta

Publication date: 26 May 2016

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

computational complexitycancellationdeterminantalgebraic circuit

Mathematics Subject Classification ID

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

Related Items (1)

Unnamed Item

Cites Work

• On computing the determinant in small parallel time using a small number of processors
• Negation can be exponentially powerful
• A lower bound on the number of additions in monotone computations
• Gaussian elimination is not optimal
• Some Exact Complexity Results for Straight-Line Computations over Semirings

This page was built for publication: Cancellation is exponentially powerful for computing the determinant