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