Characterizing arithmetic read-once formulae
From MaRDI portal
Publication:2828215
DOI10.1145/2858783zbMATH Open1347.68148arXiv1408.1995OpenAlexW1544226152MaRDI QIDQ2828215FDOQ2828215
Authors: Ilya Volkovich 
Publication date: 24 October 2016
Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1408.1995
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
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Learning read-once formulas with queries
- Combinatorial Nullstellensatz
- On the relation between polynomial identity testing and finding variable disjoint factors
- Arithmetic circuits: a survey of recent results and open questions
- Title not available (Why is that?)
- Combinatorial characterization of read-once formulae
- Randomness efficient identity testing of multivariate polynomials
- Improved low-degree testing and its applications
- Interpolating Arithmetic Read-Once Formulas in Parallel
- On interpolating arithmetic read-once formulas with exponentiation
- Learning Boolean read-once formulas over generalized bases
- Learning Arithmetic Read-Once Formulas
- Read-once polynomial identity testing
- Deterministic polynomial identity tests for multilinear bounded-read formulae
- On reconstruction and testing of read-once formulas
Cited In (12)
- Integer complexity: the integer defect
- How Do Read-Once Formulae Shrink?
- Testing Read-Once Formula Satisfaction
- Limitations of sums of bounded read formulas and ABPs
- 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)
