Deterministic polynomial identity testing in non-commutative models

DOI10.1007/s00037-005-0188-8zbMath1096.68070OpenAlexW2121894367MaRDI QIDQ1781113

Ran Raz, Amir Shpilka

Publication date: 16 June 2005

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-005-0188-8

zbMATH Keywords

polynomial identity testingarithmetic branching programsnon-commutative formulae

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Related Items

Fast exact algorithms using Hadamard product of polynomials, Subexponential size hitting sets for bounded depth multilinear formulas, Exact learning from an honest teacher that answers membership queries, Arithmetic Circuits, Monomial Algebras and Finite Automata, Spatial Isolation Implies Zero Knowledge Even in a Quantum World, Unnamed Item, Characterizing Propositional Proofs as Noncommutative Formulas, On testing monomials in multivariate polynomials, Deterministic identity testing for sum of read-once oblivious arithmetic branching programs, Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials, A case of depth-3 identity testing, sparse factorization and duality, Reconcilable differences, Algebraic proofs over noncommutative formulas, Algorithms for orbit closure separation for invariants and semi-invariants of matrices, Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in, Unnamed Item, Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size, Witnessing matrix identities and proof complexity, Efficient Black-Box Identity Testing for Free Group Algebras, Read-once polynomial identity testing, Recent Results on Polynomial Identity Testing, Improved Explicit Hitting-Sets for ROABPs, Unnamed Item, On the complexity of noncommutative polynomial factorization, On the hardness of the noncommutative determinant, Blackbox identity testing for sum of special ROABPs and its border class, Unnamed Item, Unnamed Item, Lower bounds for arithmetic circuits via the Hankel matrix, A Special Case of Rational Identity Testing and the Brešar-Klep Theorem., Operator scaling: theory and applications, Geometric complexity theory V: Efficient algorithms for Noether normalization, Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees, Improved hitting set for orbit of ROABPs, Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits