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

arithmetic circuitshardnesslower boundspolynomial identity testingrandomness

Mathematics Subject Classification ID

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

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)

• Depth-4 lower bounds, determinantal complexity: a unified approach
• Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
• 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
• On the Symmetries of and Equivalence Test for Design Polynomials.
• A super-quadratic lower bound for depth four arithmetic circuits

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)