{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T06:07:28Z","timestamp":1774591648095,"version":"3.50.1"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,2,3]],"date-time":"2016-02-03T00:00:00Z","timestamp":1454457600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF 0832797"],"award-info":[{"award-number":["CCF 0832797"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2016,2,3]]},"abstract":"<jats:p>\n            An\n            <jats:italic>arithmetic Read-Once Formula<\/jats:italic>\n            (ROF for short) is a formula (i.e., a tree of computation) in which the operations are { +, \u00d7} 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.\n          <\/jats:p>","DOI":"10.1145\/2858783","type":"journal-article","created":{"date-parts":[[2016,2,3]],"date-time":"2016-02-03T16:29:01Z","timestamp":1454516941000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Characterizing Arithmetic Read-Once Formulae"],"prefix":"10.1145","volume":"8","author":[{"given":"Ilya","family":"Volkovich","sequence":"first","affiliation":[{"name":"Princeton University, Princeton, NJ"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,2,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/971651.971653"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2011.18"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/138027.138061"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-003-0025-0"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1550"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979528812X"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979223664X"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1042"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185341"},{"key":"e_1_2_1_10_1","first-page":"183","article-title":"On repetition-free boolean functions","volume":"32","author":"Gurvich V. A.","year":"1977","unstructured":"V. A. Gurvich . 1977 . On repetition-free boolean functions . Uspekhi Matematicheskikh Nauk 32 , 1 (1977), 183 -- 184 . (in Russian). V. A. Gurvich. 1977. On repetition-free boolean functions. Uspekhi Matematicheskikh Nauk 32, 1 (1977), 183--184. (in Russian).","journal-title":"Uspekhi Matematicheskikh Nauk"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 4th Annual Workshop on Computational Learning Theory (COLT). 326--336","author":"Hancock T. R.","unstructured":"T. R. Hancock and L. Hellerstein . 1991. Learning read-once formulas over fields and extended bases . In Proceedings of the 4th Annual Workshop on Computational Learning Theory (COLT). 326--336 . T. R. Hancock and L. Hellerstein. 1991. Learning read-once formulas over fields and extended bases. In Proceedings of the 4th Annual Workshop on Computational Learning Theory (COLT). 326--336."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)90372-Z"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380801"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_2_1_15_1","volume-title":"37th International Colloquium (ICALP). 408--419","author":"Shpilka A.","year":"2010","unstructured":"A. Shpilka and I. Volkovich . 2010. On the relation between polynomial identity testing and finding variable disjoint factors. In Automata, Languages and Programming , 37th International Colloquium (ICALP). 408--419 . Full version at http:\/\/eccc.hpi-web.de\/report\/ 2010 \/036. A. Shpilka and I. Volkovich. 2010. On the relation between polynomial identity testing and finding variable disjoint factors. In Automata, Languages and Programming, 37th International Colloquium (ICALP). 408--419. Full version at http:\/\/eccc.hpi-web.de\/report\/2010\/036."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2014.v010a018"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0105-8"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000039"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/646670.698972"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2858783","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2858783","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:48:43Z","timestamp":1750225723000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2858783"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,3]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,2,3]]}},"alternative-id":["10.1145\/2858783"],"URL":"https:\/\/doi.org\/10.1145\/2858783","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2,3]]},"assertion":[{"value":"2014-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-02-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}