Building above read-once polynomials: identity testing and hardness of representation

DOI10.1007/s00453-015-0101-zzbMath1356.68082OpenAlexW2282342427MaRDI QIDQ727964

Karteek Sreenivasaiah, Meena Mahajan, B. V. Raghavendra Rao

Publication date: 21 December 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-015-0101-z

zbMATH Keywords

algebraic algorithmsarithmetic circuitspolynomial identity testing

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Unnamed Item

Cites Work

• Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
• Combinatorial characterization of read-once formulae
• Negation can be exponentially powerful
• A probabilistic remark on algebraic program testing
• Polynomial identity testing for depth 3 circuits
• Monomials, multilinearity and identity testing in simple read-restricted circuits
• Arithmetic Circuits: A Chasm at Depth 3
• Progress on Polynomial Identity Testing-II
• Characterizing Arithmetic Read-Once Formulae
• Arithmetic Circuits: A survey of recent results and open questions
• Asymptotically Optimal Hitting Sets Against Polynomials
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Combinatorial Nullstellensatz
• Randomness efficient identity testing of multivariate polynomials
• Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Building above read-once polynomials: identity testing and hardness of representation