Depth-4 identity testing and Noether's normalization lemma

DOI10.1007/978-3-319-34171-2_22MaRDI QIDQ5740194zbMATH OpenOpenAlexFDO

Authors Partha Mukhopadhyay

Publication date 25 July 2016

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-34171-2_22

Mathematics Subject Classification ID

Polynomials, factorization in commutative rings (13P05) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Networks and circuits as models of computation; circuit complexity (68Q06) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Black-box identity testing of depth-4 multilinear circuits
• Black-box identity testing of depth-4 multilinear circuits
• Explicit Noether normalization for simultaneous conjugation via polynomial identity testing
• Deterministic identity testing of depth-\(4\) multilinear circuits with bounded top fan-in
• Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in

Cites work

• Algebraic independence and blackbox identity testing
• Approaching the chasm at depth four
• Arithmetic circuits: a chasm at depth 3
• Arithmetic circuits: a survey of recent results and open questions
• Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
• Black-box identity testing of depth-4 multilinear circuits
• Blackbox identity testing for bounded top-fanin depth-3 circuits: the field doesn't matter
• Blackbox Polynomial Identity Testing for Depth 3 Circuits
• Combinatorial Nullstellensatz
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in
• Explicit Noether normalization for simultaneous conjugation via polynomial identity testing
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• scientific article; zbMATH DE number 3698383 (Why is no real title available?)
• Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
• Jacobian hits circuits: hitting-sets, lower bounds for depth-\(D\) occur-\(k\) formulas \& depth-\(3\) transcendence degree-\(k\) circuits
• Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
• Matching is as easy as matrix inversion
• Polynomial identity testing for depth 3 circuits
• PRIMES is in P
• Proof verification and the hardness of approximation problems
• Randomness efficient identity testing of multivariate polynomials
• The ideal membership problem and polynomial identity testing

Cited in

(2)

• Explicit Noether normalization for simultaneous conjugation via polynomial identity testing
• Variety evasive subspace families

This page was built for publication: Depth-4 identity testing and Noether's normalization lemma

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