Arithmetic circuits with locally low algebraic rank

DOI10.4086/TOC.2017.V013A006MaRDI QIDQ5368901zbMATH OpenOpenAlexFDO

Authors Mrinal Kumar, Shubhangi Saraf

Publication date 11 October 2017

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

partial derivativeslower boundsarithmetic circuitshitting setsalgebraic rankpolynomial identity testingprojected shifted partialsnon-homogeneous depth-4 circuits

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Arithmetic circuits with locally low algebraic rank
• On the power of homogeneous depth 4 arithmetic circuits
• Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits
• The computational power of depth five arithmetic circuits
• Arithmetic circuit lower bounds via MaxRank

Cited in

(9)

• On the power of homogeneous depth 4 arithmetic circuits
• Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits
• Arithmetic circuits with locally low algebraic rank
• Jacobian hits circuits: hitting sets, lower bounds for depth-\(D\) occur-\(k\) formulas and depth-3 transcendence degree-\(k\) circuits
• Jacobian hits circuits: hitting-sets, lower bounds for depth-\(D\) occur-\(k\) formulas \& depth-\(3\) transcendence degree-\(k\) circuits
• Quasi-polynomial hitting-set for set-depth-\({\Delta}\) formulas
• Linear independence, alternants, and applications
• Succinct hitting sets and barriers to proving algebraic circuits lower bounds
• Improved hitting set for orbit of ROABPs

This page was built for publication: Arithmetic circuits with locally low algebraic rank

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