Arithmetic complexity in ring extensions

DOI10.4086/TOC.2011.V007A008zbMATH Open1234.03027OpenAlexW2399793979MaRDI QIDQ3002833FDOQ3002833

Authors: Amir Yehudayoff, Pavel Hrubeš 

Publication date: 24 May 2011

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

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

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

zbMATH Keywords

polynomialscircuit complexityalgebraic complexityformula sizealgebraic extensionsdivision gates

Mathematics Subject Classification ID

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

Cited In (12)

• On polynomials with symmetric Galois group which are easy to compute
• A super-quadratic lower bound for depth four arithmetic circuits
• A Selection of Lower Bounds for Arithmetic Circuits
• Complexity of elements in rings
• Efficient Black-Box Identity Testing for Free Group Algebras
• Doubly efficient interactive proofs over infinite and non-commutative rings
• Title not available (Why is that?)
• Sums of read-once formulas: how many summands are necessary?
• Title not available (Why is that?)
• Witnessing matrix identities and proof complexity
• Title not available (Why is that?)
• On the complexity of computing a random Boolean function over the reals

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)