Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits
From MaRDI portal
Publication:1630382
DOI10.1007/s00037-018-0167-5zbMath1446.12001OpenAlexW2803711344WikidataQ129892134 ScholiaQ129892134MaRDI QIDQ1630382
Nitin Saxena, Anurag Pandey, Amit Sinhababu
Publication date: 10 December 2018
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6505/
independenceJacobianfinite fieldtranscendencedegreelower boundcircuitdifferentialinseparableidentity testingdepth-4Hasse-Schmidtshifted partials
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Computational methods for problems pertaining to field theory (12-08)
Related Items
Uses Software
Cites Work
- Factors of low individual degree polynomials
- Extractors and rank extractors for polynomial sources
- Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
- The complexity of partial derivatives
- A probabilistic remark on algebraic program testing
- Apolarity and canonical forms for homogeneous polynomials
- Using Gröbner bases to determine algebra membership, split surjective algebra homomorphisms determine birational equivalence
- Extractors for varieties
- Algebraic independence and blackbox identity testing
- Arithmetic Circuits: A Chasm at Depth 3
- Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits
- Progress on Polynomial Identity Testing-II
- Modern Computer Algebra
- An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
- On the Power of Homogeneous Depth 4 Arithmetic Circuits
- Arithmetic Circuits: A survey of recent results and open questions
- A Course in Commutative Algebra
- Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits
- On the Algebraic Characteristic Set for a Class of Matroids
- A Lower Bound for the Formula Size of Rational Functions
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Fast Parallel Matrix Inversion Algorithms
- Algebraic Independence over Positive Characteristic: New Criterion and Applications to Locally Low Algebraic Rank Circuits
- Discovering the roots: uniform closure results for algebraic classes under factoring
- Bootstrapping variables in algebraic circuits
- A super-polynomial lower bound for regular arithmetic formulas
- Counting Matchings of Size k Is $\sharp$ W[1-Hard]
- Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers
- Algebraic independence in positive characteristic: A $p$-adic calculus
- Advanced Algebra
- Quasi-polynomial hitting-set for set-depth-Δ formulas
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
