Read-once polynomial identity testing
From MaRDI portal
Publication:496300
DOI10.1007/S00037-015-0105-8zbMATH Open1329.68147OpenAlexW2181660280MaRDI QIDQ496300FDOQ496300
Authors: Amir Shpilka, Ilya Volkovich 
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
Recommendations
- Improved Polynomial Identity Testing for Read-Once Formulas
- On reconstruction and testing of read-once formulas
- Read-once polynomial identity testing
- Building above read-once polynomials: identity testing and hardness of representation
- Building above read-once polynomials: identity testing and hardness of representation
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)
Cites Work
- A probabilistic remark on algebraic program testing
- Title not available (Why is that?)
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Learning read-once formulas with queries
- Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
- PRIMES is in P
- Combinatorial Nullstellensatz
- Hitting sets for multilinear read-once algebraic branching programs, in any order
- On identity testing of tensors, low-rank recovery and compressed sensing
- Matching is as easy as matrix inversion
- Deterministic polynomial identity testing in non-commutative models
- Polynomial identity testing for depth 3 circuits
- Separation of multilinear circuit and formula size
- Arithmetic circuits: a survey of recent results and open questions
- A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
- Hardness-randomness tradeoffs for bounded depth arithmetic circuits
- Improved Polynomial Identity Testing for Read-Once Formulas
- Blackbox Polynomial Identity Testing for Depth 3 Circuits
- Read-once polynomial identity testing
- Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in
- Jacobian hits circuits: hitting-sets, lower bounds for depth-\(D\) occur-\(k\) formulas \& depth-\(3\) transcendence degree-\(k\) 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-\({\Delta}\) 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
- 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
- An almost optimal rank bound for depth-3 identities
- Randomness efficient identity testing of multivariate polynomials
- Title not available (Why is that?)
- Interpolation of depth-3 arithmetic circuits with two multiplication gates
- Interpolating Arithmetic Read-Once Formulas in Parallel
- On interpolating arithmetic read-once formulas with exponentiation
- Learning Boolean read-once formulas over generalized bases
- Deterministic black-box identity testing \(\pi\)-ordered algebraic branching programs
- Diagonal Circuit Identity Testing and Lower Bounds
- Title not available (Why is that?)
- Learning Arithmetic Read-Once Formulas
- Blackbox identity testing for bounded top-fanin depth-3 circuits: the field doesn't matter
- From sylvester-gallai configurations to rank bounds
- The ideal membership problem and polynomial identity testing
Cited In (22)
- Improved Polynomial Identity Testing for Read-Once Formulas
- Characterizing arithmetic read-once formulae
- Building above read-once polynomials: identity testing and hardness of representation
- Read-once polynomial identity testing
- On some computations on sparse polynomials
- Title not available (Why is that?)
- Isomorphism testing of read-once functions and polynomials
- Title not available (Why is that?)
- Deterministic polynomial identity tests for multilinear bounded-read formulae
- Beyond the Existential Theory of the Reals
- Sums of products of polynomials in few variables: lower bounds and polynomial identity testing
- Building above read-once polynomials: identity testing and hardness of representation
- Linear independence, alternants, and applications
- Sums of read-once formulas: how many summands are necessary?
- Sparse multivariate polynomial interpolation on the basis of Schubert polynomials
- On reconstruction and testing of read-once formulas
- Sums of read-once formulas: how many summands suffice?
- Title not available (Why is that?)
- Equivalence of polynomial identity testing and polynomial factorization
- Polynomial identity testing for depth 3 circuits
- Improved hitting set for orbit of ROABPs
- Complete derandomization of identity testing and reconstruction of read-once formulas
This page was built for publication: Read-once polynomial identity testing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q496300)
