{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:37:53Z","timestamp":1787337473808,"version":"build-2736575974"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>\n                    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 algorithm for the exact interpolation of arithmetic read-once formulas over sufficiently large fields. More specifically, for n-variable read-once formulas and fields of size at least 3(n\n                    <jats:sup>2<\/jats:sup>\n                    +3n-2), our algorithm runs in $O(\\log^2 n)$ parallel steps using O(n\n                    <jats:sup>4<\/jats:sup>\n                    ) processors (where the field operations are charged unit cost). This complements some results from [N.H. Bshouty and R. Cleve, Proc. 33rd Annual Symposium on the Foundations of Computer Science, IEEE Computer Science Press, Los Alamitos, CA, 1992, pp. 24--27] which imply that other classes of read-once formulas cannot be interpolated---or even learned with membership and equivalence queries---in polylogarithmic time with polynomially many processors (even though they can be learned sequentially in polynomial time). These classes include boolean read-once formulas and arithmetic read-once formulas over fields of size $o(n \/ \\log n)$ (for n variable read-once formulas).\n                  <\/jats:p>","DOI":"10.1137\/s009753979528812x","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"401-413","source":"Crossref","is-referenced-by-count":16,"title":["Interpolating Arithmetic Read-Once Formulas in Parallel"],"prefix":"10.1137","volume":"27","author":[{"given":"Nader H.","family":"Bshouty","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard","family":"Cleve","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00116828"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/138027.138061"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1026"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321815"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979223664X"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"N. H. Bshouty and R. Cleve,\n                      On the exact learning of formulas in parallel\n                      , Proc. of the 33rd Annual Symposium on Foundations of Computer Science, 1992, pp. 24\u201327.","DOI":"10.1109\/SFCS.1992.267800"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1042"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"N. H. Bshouty, S. Goldman, T. Hancock, and S. Matar,\n                      Asking questions to minimize errors\n                      , in The 1993 Workshop on Computational Learning Theory, 1993, pp. 41\u201350.","DOI":"10.1145\/168304.168310"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01205054"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"M. Ben\u2010Or and P. Tiwari,\n                      A deterministic algorithm for sparse multivariate polynomial interpolation\n                      , in Proc. of the 20th Annual ACM Symposium on the Theory of Computing, 1988, pp. 301\u2013309.","DOI":"10.1145\/62212.62241"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200058"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/0222047"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/0219073"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"T. Hancock,\n                      Identifying \u03bc\u2010formula decision trees with queries\n                      , in The 1990 Workshop on Computational Learning Theory, 1990, pp. 23\u201337.","DOI":"10.1016\/B978-1-55860-146-8.50005-9"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"T. Hancock and L. Hellerstein,\n                      Learning read\u2010once formulas over fields and extended bases\n                      , in The 1991 Workshop on Computational Learning Theory, 1991.","DOI":"10.1016\/B978-1-55860-213-7.50033-X"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"J. Heintz and C. P. Schnorr,\n                      Testing polynomials that are easy to compute\n                      , in Proc. of the 12th Annual Symposium on the Theory of Computing, 1980, pp. 262\u2013272.","DOI":"10.1145\/800141.804674"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322232"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/BF00116827"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792239291"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"Wolfgang Maass, Gy\u00f6rgy Tur\u00e1n, On the complexity of learning from counterexamples and membership queries, IEEE Comput. Soc. Press, Los Alamitos, CA, 1990, 203\u20132101150698","DOI":"10.1109\/FSCS.1990.89539"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/0220019"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"R. E. Schapire and L. M. Sellie,\n                      Learning sparse multivariate polynomials over a field with queries and counterexamples\n                      , in Proc. of the Sixth Annual Workshop on Computational Learning Theory, 1993, pp. 17\u201326.","DOI":"10.1145\/168304.168307"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90047-J"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S009753979528812X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:06Z","timestamp":1787335926000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S009753979528812X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S009753979528812X"],"URL":"https:\/\/doi.org\/10.1137\/s009753979528812x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}