scientific article; zbMATH DE number 7561311

DOI10.4230/LIPIcs.FSTTCS.2018.6MaRDI QIDQ5090938

Anamay Tengse, Ramprasad Saptharishi

Publication date: 21 July 2022

Full work available at URL: https://arxiv.org/abs/1709.03068

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

lower boundspolynomial identity testingalgebraic circuit complexityRead-once oblivious ABPsunambiguous circuits

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Related Items

Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Read-once polynomial identity testing
• The complexity of partial derivatives
• Pseudorandom generators for space-bounded computation
• A probabilistic remark on algebraic program testing
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• Deterministic polynomial identity testing in non-commutative models
• Fast Parallel Computation of Polynomials Using Few Processors
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• On the Parallel Evaluation of Multivariate Polynomials
• Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
• Quasi-polynomial hitting-set for set-depth-Δ formulas
• Non-commutative circuits and the sum-of-squares problem
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Derandomizing polynomial identity tests means proving circuit lower bounds