Sums of products of polynomials in few variables: lower bounds and polynomial identity testing

DOI10.4230/LIPICS.CCC.2016.35MaRDI QIDQ5368769zbMATH OpenFDO

Authors Mrinal Kumar, Shubhangi Saraf

Publication date 10 October 2017

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

zbMATH Keywords

lower boundsarithmetic circuitshardnessrandomnesspolynomial identity testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
• Read-once polynomial identity testing
• Building above read-once polynomials: identity testing and hardness of representation
• Recent results on polynomial identity testing
• Black-box identity testing of depth-4 multilinear circuits

Cited in

(7)

• A super-quadratic lower bound for depth four arithmetic circuits
• On the Symmetries of and Equivalence Test for Design Polynomials.
• Lower bounds for depth-three arithmetic circuits with small bottom fanin
• Lower Bounds for Norms of Products of Polynomials
• Towards blackbox identity testing of log-variate circuits
• Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
• Depth-4 lower bounds, determinantal complexity: a unified approach

This page was built for publication: Sums of products of polynomials in few variables: lower bounds and polynomial identity testing

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