Read-once polynomial identity testing
From MaRDI portal
Publication:496300
DOI10.1007/s00037-015-0105-8zbMath1329.68147OpenAlexW2181660280MaRDI QIDQ496300
Publication date: 21 September 2015
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-015-0105-8
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (9)
Isomorphism testing of read-once functions and polynomials ⋮ Sums of read-once formulas: how many summands are necessary? ⋮ Sparse multivariate polynomial interpolation on the basis of Schubert polynomials ⋮ Unnamed Item ⋮ Sums of Read-Once Formulas: How Many Summands Suffice? ⋮ Unnamed Item ⋮ Characterizing Arithmetic Read-Once Formulae ⋮ Unnamed Item ⋮ Improved hitting set for orbit of ROABPs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bounds and separations for constant depth multilinear circuits
- Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
- Combinatorial characterization of read-once formulae
- The ideal membership problem and polynomial identity testing
- Matching is as easy as matrix inversion
- A probabilistic remark on algebraic program testing
- On interpolating arithmetic read-once formulas with exponentiation
- PRIMES is in P
- Deterministic polynomial identity testing in non-commutative models
- Learning Boolean read-once formulas over generalized bases
- Polynomial identity testing for depth 3 circuits
- Deterministic Black-Box Identity Testing $pi$-Ordered Algebraic Branching Programs
- An Almost Optimal Rank Bound for Depth-3 Identities
- Arithmetic Circuits: A survey of recent results and open questions
- A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
- Diagonal Circuit Identity Testing and Lower Bounds
- Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits
- Improved Polynomial Identity Testing for Read-Once Formulas
- Interpolation of Depth-3 Arithmetic Circuits with Two Multiplication Gates
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Learning read-once formulas with queries
- Combinatorial Nullstellensatz
- Interpolating Arithmetic Read-Once Formulas in Parallel
- Learning Arithmetic Read-Once Formulas
- Blackbox Identity Testing for Bounded Top-Fanin Depth-3 Circuits: The Field Doesn't Matter
- Blackbox Polynomial Identity Testing for Depth 3 Circuits
- Randomness efficient identity testing of multivariate polynomials
- Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
- Hitting sets for multilinear read-once algebraic branching programs, in any order
- From sylvester-gallai configurations to rank bounds
- Deterministic Identity Testing of Depth-4 Multilinear Circuits with Bounded Top Fan-in
- On identity testing of tensors, low-rank recovery and compressed sensing
- Jacobian hits circuits
- Black-box identity testing of depth-4 multilinear circuits
- Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
- Quasi-polynomial hitting-set for set-depth-Δ formulas
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Multi-linear formulas for permanent and determinant are of super-polynomial size
- Derandomizing polynomial identity tests means proving circuit lower bounds
This page was built for publication: Read-once polynomial identity testing