Arithmetic complexity in ring extensions

DOI10.4086/TOC.2011.V007A008MaRDI QIDQ3002833zbMATH OpenOpenAlexFDO

Authors Amir Yehudayoff, Pavel Hrubeš

Publication date 24 May 2011

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2011.v007a008

zbMATH Keywords

algebraic complexityalgebraic extensionscircuit complexitydivision gatesformula sizepolynomials

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Ordinary and skew polynomial rings and semigroup rings (16S36) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 165425
• The complexity of two problems on arithmetic circuits
• scientific article; zbMATH DE number 3988701
• Depth-3 arithmetic circuits over fields of characteristic zero
• Computing polynomials with few multiplications

Cited in

(14)

• On polynomials with symmetric Galois group which are easy to compute
• Sums of read-once formulas: how many summands are necessary?
• Complexity of elements in rings
• A Selection of Lower Bounds for Arithmetic Circuits
• scientific article; zbMATH DE number 4057005 (Why is no real title available?)
• scientific article; zbMATH DE number 165425 (Why is no real title available?)
• Witnessing matrix identities and proof complexity
• A super-quadratic lower bound for depth four arithmetic circuits
• scientific article; zbMATH DE number 7561765 (Why is no real title available?)
• On the complexity of computing a random Boolean function over the reals
• Efficient Black-Box Identity Testing for Free Group Algebras
• Doubly efficient interactive proofs over infinite and non-commutative rings
• A subquadratic upper bound on Hurwitz's problem and related noncommutative polynomials
• On approximate symmetric polynomials and tightness of homogenization results

This page was built for publication: Arithmetic complexity in ring extensions

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