Computing polynomials with few multiplications

DOI10.4086/TOC.2011.V007A013zbMATH Open1247.68113OpenAlexW2398187817MaRDI QIDQ2913800FDOQ2913800

Authors: Shachar Lovett 

Publication date: 27 September 2012

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

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

Recommendations

• STACS 2005
• Multiplicative complexity of polynomial multiplication over finite fields
• On parallel evaluation of certain classes of polynomials with an increasing number of variables
• Simple multivariate polynomial multiplication
• On the parallel evaluation of multivariate polynomials

zbMATH Keywords

arithmetic circuitspolynomial identity testingmultiplications

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited In (10)

• A simple proof for the upper bound of the computational complexity of three monomials in three variables
• A super-quadratic lower bound for depth four arithmetic circuits
• A Selection of Lower Bounds for Arithmetic Circuits
• Code Generation for Polynomial Multiplication
• Arithmetic complexity in ring extensions
• Title not available (Why is that?)
• Computing values of a polynomial with only few multiplications
• Computing with barycentric polynomials
• Computing Elementary Symmetric Polynomials with a Subpolynomial Numberof Multiplications
• On the multiplicative complexity of polynomials

This page was built for publication: Computing polynomials with few multiplications

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