scientific article; zbMATH DE number 7140484

DOI10.4086/TOC.2019.V015A007MaRDI QIDQ5204825zbMATH OpenOpenAlexFDO

Authors

Publication date 5 December 2019

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2019.v015a007

zbMATH Keywords

algebraic complexitynon-commutative computationpolynomial identity testingpolynomial indentity lemmarandomized algorithm

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Randomized algorithms (68W20)

Recommendations

• Randomized polynomial time identity testing for noncommutative circuits
• Deterministic polynomial identity testing in non-commutative models
• Non-commutative computations: lower bounds and polynomial identity testing
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Polynomial time deterministic identity testing algorithm for Σ ^[3] ΠΣΠ ^[2] circuits via Edelstein–Kelly type theorem for quadratic polynomials
• Identity testing for constant-width, and commutative, read-once oblivious ABPs
• Quantum query complexity of multilinear identity testing
• Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing
• Circuit complexity, proof complexity, and polynomial identity testing. The ideal proof system

Cited in

(12)

• Operator scaling: theory and applications
• The power of depth 2 circuits over algebras
• Recent results on polynomial identity testing
• Randomized polynomial time identity testing for noncommutative circuits
• scientific article; zbMATH DE number 7471587 (Why is no real title available?)
• scientific article; zbMATH DE number 7204375 (Why is no real title available?)
• Testing equivalence of polynomials under shifts
• Non-commutative computations: lower bounds and polynomial identity testing
• Near-optimal bootstrapping of hitting sets for algebraic circuits
• Schur polynomials do not have small formulas if the determinant does not
• New results on noncommutative and commutative polynomial identity testing
• A multivariate to bivariate reduction for noncommutative rank and related results

This page was built for publication:

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