Characterizing arithmetic read-once formulae
From MaRDI portal
Publication:2828215
Abstract: An emph{arithmetic read-once formula} (ROF for short) is a formula (i.e. a tree of computation) in which the operations are and such that every input variable labels at most one leaf. We give a simple characterization of such formulae. Other than being interesting in its own right, our characterization gives rise to a property testing algorithm for functions computable by such formulae. To the best of our knowledge, prior to our work no characterization and/or property testing algorithm was known for this kind of formulae.
Recommendations
- Combinatorial characterization of read-once formulae
- On interpolating arithmetic read-once formulas with exponentiation
- On reconstruction and testing of read-once formulas
- Interpolating Arithmetic Read-Once Formulas in Parallel
- Learning Arithmetic Read-Once Formulas
- On the Expressive Power of Read-Once Determinants
- Exact Identification of Read-Once Formulas Using Fixed Points of Amplification Functions
- An efficient representation of arithmetic for term rewriting
- On the shrinkage exponent for read-once formulae
- Amplification by Read-Once Formulas
Cites work
- scientific article; zbMATH DE number 3545568 (Why is no real title available?)
- Arithmetic circuits: a survey of recent results and open questions
- Combinatorial Nullstellensatz
- Combinatorial characterization of read-once formulae
- Deterministic polynomial identity tests for multilinear bounded-read formulae
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Improved low-degree testing and its applications
- Interpolating Arithmetic Read-Once Formulas in Parallel
- Learning Arithmetic Read-Once Formulas
- Learning Boolean read-once formulas over generalized bases
- Learning read-once formulas with queries
- On interpolating arithmetic read-once formulas with exponentiation
- On reconstruction and testing of read-once formulas
- On the relation between polynomial identity testing and finding variable disjoint factors
- Randomness efficient identity testing of multivariate polynomials
- Read-once polynomial identity testing
Cited in
(12)- Integer complexity: the integer defect
- How Do Read-Once Formulae Shrink?
- Limitations of sums of bounded read formulas and ABPs
- Testing Read-Once Formula Satisfaction
- On read-once functions over \(\mathbb{Z}_3\)
- Integer complexity: algorithms and computational results
- Building above read-once polynomials: identity testing and hardness of representation
- On the Expressive Power of Read-Once Determinants
- On some computations on sparse polynomials
- Integer complexity: representing numbers of bounded defect
- Sums of read-once formulas: how many summands are necessary?
- Sums of read-once formulas: how many summands suffice?
This page was built for publication: Characterizing arithmetic read-once formulae
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2828215)
