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

Related Items (35)

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

This page was built for publication: Deterministic polynomial identity testing in non-commutative models