Arithmetic circuits with locally low algebraic rank

DOI10.4230/LIPICS.CCC.2016.34MaRDI QIDQ5368768zbMATH OpenFDO

Authors Mrinal Kumar, Shubhangi Saraf

Publication date 10 October 2017

Full work available at URL https://doi.org/10.4230/LIPICS.CCC.2016.34

zbMATH Keywords

algebraic independencearithmetic circuitslower bounds

Mathematics Subject Classification ID

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

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
• Algebraic independence over positive characteristic: new criterion and applications to locally low algebraic rank circuits
• Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits

Cited in

(14)

• Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits
• Depth-4 lower bounds, determinantal complexity: a unified approach
• On constant depth circuits parameterized by degree: identity testing and depth reduction
• Jacobian hits circuits: hitting sets, lower bounds for depth-D occur-k formulas and depth-3 transcendence degree-k circuits
• Algebraic independence and blackbox identity testing
• Algebraic independence over positive characteristic: new criterion and applications to locally low algebraic rank circuits
• Succinct hitting sets and barriers to proving algebraic circuits lower bounds
• Towards blackbox identity testing of log-variate circuits
• On the Symmetries of and Equivalence Test for Design Polynomials.
• scientific article; zbMATH DE number 7250150 (Why is no real title available?)
• Arithmetic circuits with locally low algebraic rank
• 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
• Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring

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 Q5368768)