research-article

On Interpolating Arithmetic Read-Once Formulas with Exponentiation

Authors:

Daoud Bshouty,

Nader H BshoutyAuthors Info & Claims

Journal of Computer and System Sciences, Volume 56, Issue 1

Pages 112 - 124

https://doi.org/10.1006/jcss.1997.1550

Published: 01 February 1998 Publication History

Abstract

A formula is a read-once formula if each variable appears at most once in it. An arithmetic read-once formula (AROF) with exponentiation is one in which the operations are addition, substraction, multiplication, division and exponentiation to an arbitrary integer. We present a polynomial time algorithm for interpolating AROF withexponentiationusing randomized substitutions. Interpolating AROF without exponentiation is studied in (Bshouty, Hancock, and Hellerstein,SIAM J. Comput.24, No. 4, 1995). To add the exponentiation operation to the basis we develop a new technique.

References

[1]

M. Ben-Or, P. Tiwari, A deterministic algorithm for sparse multivariate polynomial interpolation, Proceedings, 20th Annual ACM Symposium on the Theory of Computing, 1988, 301, 309

Digital Library

Google Scholar

[2]

A. Borodin, P. Tiwari, On the decidability of sparse univariate polynomials, Proceedings, 31st Symposium on the Foundations of Computer Science, 1990

Google Scholar

[3]

N.H. Bshouty, T.R. Hancock, L. Hellerstein, SIAM J. Comput., 24 (1995).

Google Scholar

[4]

D. Y. Grigoriev, M. Karpinski, M. F. Singer, Interpolation of sparse rational functions without knowing bounds on the exponent, Proceedings, 31st Symposium on Foundations of Computer Science, 1990

Digital Library

Google Scholar

[5]

D.Y. Grigoriev, M. Karpinski, M.F. Singer, Research Report (1988).

Google Scholar

[6]

J. Heintz, C. P. Schnorr, Testing polynomials that are easy to compute, Proceedings, 12th Annual ACM Symposium on the Theory of Computing, 1980, 262, 272

Google Scholar

[7]

M. Ron Roth, G. Benedek, Interpolation and approximation of sparse multivariate polynomials overGF, SIAM J. Comput., 20 (1991) 291-314.

Digital Library

Google Scholar

[8]

R. E. Shapire, L. M. Sellie, Learning sparse multivariate polynomials over a field with queries and counterexamples, Proceedings, Sixth Annual Workshop on Computational learning Theory, 1993, 17, 26

Google Scholar

[9]

J.T. Schwartz, Fast polynomial algorithms for verification of polynomial identities, J. Assoc. Comput. Mach., 27 (1980) 701-707.

Digital Library

Google Scholar

[10]

Y. Mansour, Randomized approximation and interpolation of sparse polynomials, SIAM J. Comput.

Google Scholar

[11]

A.K. Lenstra, Factoring multivariate polynomials over algebraic number fields, SIAM J. Comput., 16 (1987) 591-598.

Digital Library

Google Scholar

[12]

A.K. Lenstra, H.W. Lenstra, L. Lovász, Factoring polynomials with rational coefficients, Math. Ann., 261 (1982) 515-534.

Crossref

Google Scholar

Cited By

View all

Medini DShpilka A(2021)Hitting sets and reconstruction for dense orbits in VPe and ΣΠΣ circuitsProceedings of the 36th Computational Complexity Conference10.4230/LIPIcs.CCC.2021.19Online publication date: 20-Jul-2021
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2021.19
Lorenz J(2019)On the Complexity of RestartingComputer Science – Theory and Applications10.1007/978-3-030-19955-5_22(250-261)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1007/978-3-030-19955-5_22
Minahan DVolkovich I(2018)Complete Derandomization of Identity Testing and Reconstruction of Read-Once FormulasACM Transactions on Computation Theory10.1145/319683610:3(1-11)Online publication date: 23-May-2018
https://dl.acm.org/doi/10.1145/3196836
Show More Cited By

Index Terms

On Interpolating Arithmetic Read-Once Formulas with Exponentiation
1. Mathematics of computing

Recommendations

Interpolating Arithmetic Read-Once Formulas in Parallel

A formula is read-once if each variable appears in it at most once. An arithmetic formula is one in which the operations are addition, subtraction, multiplication, and division (and constants are allowed). We present a randomized (Las Vegas) parallel ...
On learning arithmetic read-once formulas with exponentiation (extended abstract)
COLT '94: Proceedings of the seventh annual conference on Computational learning theory

A formula is a read-once formula if each variable appears at most once in it. An arithmetic read-once formula (AROF) with exponentiation is one in which the operations are addition, subtraction, multiplication, division and exponentiation to an ...
Learning Arithmetic Read-Once Formulas

A formula is read-once if each variable appears at most once in it. An arithmetic read-once formula is one in which the operators are addition, subtraction, multiplication, and division. We present polynomial time algorithms for exact learning of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Computer and System Sciences

Journal of Computer and System Sciences Volume 56, Issue 1

Feb. 1998

129 pages

ISSN:0022-0000

Editor:
E. K. Blum
Univ. of Southern California, Los Angeles

Issue’s Table of Contents

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 February 1998

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Medini DShpilka A(2021)Hitting sets and reconstruction for dense orbits in VPe and ΣΠΣ circuitsProceedings of the 36th Computational Complexity Conference10.4230/LIPIcs.CCC.2021.19Online publication date: 20-Jul-2021
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2021.19
Lorenz J(2019)On the Complexity of RestartingComputer Science – Theory and Applications10.1007/978-3-030-19955-5_22(250-261)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1007/978-3-030-19955-5_22
Minahan DVolkovich I(2018)Complete Derandomization of Identity Testing and Reconstruction of Read-Once FormulasACM Transactions on Computation Theory10.1145/319683610:3(1-11)Online publication date: 23-May-2018
https://dl.acm.org/doi/10.1145/3196836
Minahan DVolkovich I(2017)Complete derandomization of identity testing and reconstruction of read-once formulasProceedings of the 32nd Computational Complexity Conference10.5555/3135595.3135627(1-13)Online publication date: 9-Jul-2017
https://dl.acm.org/doi/10.5555/3135595.3135627
Volkovich I(2016)Characterizing Arithmetic Read-Once FormulaeACM Transactions on Computation Theory10.1145/28587838:1(1-19)Online publication date: 3-Feb-2016
https://dl.acm.org/doi/10.1145/2858783
Mahajan MTawari A(2016)Sums of Read-Once FormulasProceedings of the 11th International Computer Science Symposium on Computer Science --- Theory and Applications - Volume 969110.1007/978-3-319-34171-2_19(266-279)Online publication date: 9-Jun-2016
https://dl.acm.org/doi/10.1007/978-3-319-34171-2_19
Shpilka AVolkovich I(2015)Read-once polynomial identity testingComputational Complexity10.1007/s00037-015-0105-824:3(477-532)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1007/s00037-015-0105-8
Shpilka AYehudayoff A(2010)Arithmetic CircuitsFoundations and Trends® in Theoretical Computer Science10.1561/04000000395:3–4(207-388)Online publication date: 1-Mar-2010
https://dl.acm.org/doi/10.1561/0400000039
Shpilka AVolkovich I(2009)Improved Polynomial Identity Testing for Read-Once FormulasProceedings of the 12th International Workshop and 13th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques10.1007/978-3-642-03685-9_52(700-713)Online publication date: 21-Aug-2009
https://dl.acm.org/doi/10.1007/978-3-642-03685-9_52
Shpilka AVolkovich ILadner RDwork C(2008)Read-once polynomial identity testingProceedings of the fortieth annual ACM symposium on Theory of computing10.1145/1374376.1374448(507-516)Online publication date: 17-May-2008
https://dl.acm.org/doi/10.1145/1374376.1374448
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Interpolating Arithmetic Read-Once Formulas in Parallel

On learning arithmetic read-once formulas with exponentiation (extended abstract)

Learning Arithmetic Read-Once Formulas

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations