Arithmetic circuits with locally low algebraic rank
DOI10.4086/TOC.2017.V013A006zbMATH Open1378.68051arXiv1806.06097OpenAlexW3106203092MaRDI QIDQ5368901FDOQ5368901
Authors: Mrinal Kumar, Shubhangi Saraf 
Publication date: 11 October 2017
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1806.06097
Recommendations
partial derivativeslower boundsarithmetic circuitshitting setsalgebraic rankpolynomial identity testingprojected shifted partialsnon-homogeneous depth-4 circuits
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
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)
