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

DOI10.4230/LIPICS.CCC.2016.35zbMATH Open1380.68201arXiv1504.06213MaRDI QIDQ5368769FDOQ5368769

Authors: Mrinal Kumar, Shubhangi Saraf 

Publication date: 10 October 2017

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

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

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)

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)