{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T02:52:31Z","timestamp":1777517551093,"version":"3.51.4"},"reference-count":76,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[2023,3,14]],"date-time":"2023-03-14T00:00:00Z","timestamp":1678752000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Computability"],"published-print":{"date-parts":[[2023,6,21]]},"abstract":"<jats:p>We investigate the complexity of languages that correspond to algebraic real numbers, and we present improved upper bounds on the complexity of these languages. Our key technical contribution is the presentation of improved uniform [Formula: see text] circuits for division, matrix powering, and related problems, where the improvement is in terms of \u201cmajority depth\u201d (initially studied by Maciel and Th\u00e9rien). As a corollary, we obtain improved bounds on the complexity of certain problems involving arithmetic circuits, which are known to lie in the counting hierarchy, and we answer a question posed by Yap.<\/jats:p>","DOI":"10.3233\/com-220407","type":"journal-article","created":{"date-parts":[[2023,3,14]],"date-time":"2023-03-14T12:08:25Z","timestamp":1678795705000},"page":"145-173","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["On the complexity of algebraic numbers, and the bit-complexity of straight-line programs"],"prefix":"10.1177","volume":"12","author":[{"given":"Eric","family":"Allender","sequence":"first","affiliation":[{"name":"Department of Computer Science, Rutgers University, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikhil","family":"Balaji","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology, Delhi, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Samir","family":"Datta","sequence":"additional","affiliation":[{"name":"Chennai Mathematical Institute & UMI-ReLaX, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rameshwar","family":"Pratap","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology, Hyderabad, Telangana, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2023,3,14]]},"reference":[{"key":"ref001","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2007.165.547"},{"key":"ref002","doi-asserted-by":"publisher","DOI":"10.1016\/j.crma.2004.04.012"},{"key":"ref003","doi-asserted-by":"publisher","DOI":"10.1090\/tran\/7915"},{"key":"ref004","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1675"},{"key":"ref005","doi-asserted-by":"publisher","DOI":"10.4086\/cjtcs.1999.007"},{"key":"ref006","doi-asserted-by":"publisher","DOI":"10.1142\/9789812562494_0011"},{"key":"ref007","doi-asserted-by":"crossref","unstructured":"E.\u00a0Allender, N.\u00a0Balaji and S.\u00a0Datta, Low-depth uniform threshold circuits and the bit-complexity of straight line programs, in: Mathematical Foundations of Computer Science (MFCS), Vol.\u00a08635, Springer, 2014, pp.\u00a013\u201324.","DOI":"10.1007\/978-3-662-44465-8_2"},{"key":"ref008","doi-asserted-by":"publisher","DOI":"10.1137\/070697926"},{"key":"ref009","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1725"},{"key":"ref010","unstructured":"E.\u00a0Allender and H.\u00a0Schnorr, The complexity of the BitSLP problem, 2005, Unpublished Manuscript."},{"key":"ref011","doi-asserted-by":"crossref","unstructured":"J.P.\u00a0Allouche and J.\u00a0Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2003. ISBN 0521823323.","DOI":"10.1017\/CBO9780511546563"},{"key":"ref012","doi-asserted-by":"crossref","unstructured":"S.\u00a0Arora and B.\u00a0Barak, Computational Complexity: A Modern Approach, Vol.\u00a01, Cambridge University Press, 2009.","DOI":"10.1017\/CBO9780511804090"},{"key":"ref013","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-97-00856-9"},{"key":"ref014","unstructured":"D.H.\u00a0Bailey, A Compendium of BBP-Type Formulas for Mathematical Constants, Report, Lawrence, Berkeley National Laboratory, Berkeley, CA, USA, 2017."},{"key":"ref015","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90014-A"},{"key":"ref016","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90357-8"},{"key":"ref017","doi-asserted-by":"publisher","DOI":"10.1137\/0215070"},{"key":"ref018","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(87)90022-8"},{"key":"ref019","unstructured":"J.M.\u00a0Borwein and P.B.\u00a0Borwein, Pi and the AGM: A Study in the Analytic Number Theory and Computational Complexity, Wiley-Interscience, 1987."},{"key":"ref020","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-59234-9"},{"key":"ref021","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1588"},{"key":"ref022","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2001119"},{"key":"ref023","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488728"},{"key":"ref024","unstructured":"K.J.\u00a0Compton and H.\u00a0Straubing, Characterizations of regular languages in low level complexity classes, in: Current Trends in Theoretical Computer Science, Entering the 21th Century, G.\u00a0Paun, G.\u00a0Rozenberg and A.\u00a0Salomaa, eds, World Scientific, 2001, pp.\u00a0235\u2013246."},{"key":"ref025","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29952-0_22"},{"key":"ref026","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00021-2"},{"key":"ref027","doi-asserted-by":"publisher","DOI":"10.1142\/9789812705815_0005"},{"key":"ref028","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0661(05)80166-5"},{"key":"ref029","doi-asserted-by":"publisher","DOI":"10.1137\/080720826"},{"key":"ref030","unstructured":"P.\u00a0Etessami Probability, Recursion, Games, and Fixed Points, 2013, Talk presented at Horizons in TCS: A\u00a0Celebration of Mihalis Yannakakis\u2019 60th Birthday."},{"key":"ref031","unstructured":"J.D.\u00a0Faires and R.L.\u00a0Burden, Numerical Methods, PWS Publishing, Boston, 1993. ISBN 0-534-93136-7."},{"key":"ref032","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27654-5_9"},{"key":"ref033","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2015.329"},{"key":"ref034","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794274519"},{"key":"ref035","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1965-0170805-7"},{"key":"ref036","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_55"},{"key":"ref037","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00025-9"},{"key":"ref038","doi-asserted-by":"publisher","DOI":"10.1016\/j.jnt.2009.08.009"},{"key":"ref039","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.09.001"},{"key":"ref040","unstructured":"G.\u00a0Jindal and T.\u00a0Saranurak, Subtraction makes computing integers faster, 2012, CoRR arXiv:1212.2549."},{"key":"ref041","doi-asserted-by":"publisher","DOI":"10.1145\/2382559.2382560"},{"key":"ref042","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744572"},{"key":"ref043","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(82)80003-0"},{"key":"ref044","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.08.008"},{"key":"ref045","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-011-0002-8"},{"key":"ref046","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2015.67"},{"key":"ref047","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41422-0"},{"key":"ref048","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1998.2732"},{"issue":"1","key":"ref049","first-page":"39","volume":"34","author":"Mereghetti C.","year":"2000","journal-title":"ITA"},{"key":"ref050","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1096901774"},{"key":"ref051","doi-asserted-by":"publisher","DOI":"10.1137\/18M1195887"},{"key":"ref052","unstructured":"M.\u00a0Nakanishi and M.\u00a0Villagra, Computational Complexity of Space-Bounded Real Numbers, 2018, CoRR, arXiv:1805.02572."},{"key":"ref053","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1120224726"},{"key":"ref054","doi-asserted-by":"crossref","unstructured":"J.\u00a0Ouaknine and J.\u00a0Worrell, Positivity problems for low-order linear recurrence sequences, in: Proceedings of the Twenty-Fifth Annual ACM-Siam Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2014, pp.\u00a0366\u2013379.","DOI":"10.1137\/1.9781611973402.27"},{"key":"ref055","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43951-7_27"},{"key":"ref056","unstructured":"P.M.\u00a0Potts, Efficient on-line computation of real functions using exact floating point, in: Manuscript, Dept. of Computing, Imperial College, London, 1997."},{"key":"ref057","unstructured":"P.M.\u00a0Potts, Exact Real Arithmetic using M\u00f6bius Transformations, PhD thesis, Imperial College, University of London, 1999."},{"key":"ref058","first-page":"598","volume":"41","author":"Razborov A.A.","year":"1987","journal-title":"Matematicheskie Zametki"},{"key":"ref059","doi-asserted-by":"publisher","DOI":"10.1137\/0221053"},{"key":"ref060","first-page":"1","volume":"2","author":"Roth K.F.","year":"1955","journal-title":"Mathematika. A Journal of Pure and Applied Mathematics"},{"key":"ref061","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.11.003"},{"key":"ref062","doi-asserted-by":"crossref","unstructured":"A.B.\u00a0Shidlovskii, Transcendental Numbers, de Gruyter, New York, 1989.","DOI":"10.1515\/9783110889055"},{"key":"ref063","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480192228619"},{"key":"ref064","doi-asserted-by":"crossref","unstructured":"R.\u00a0Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, in: Proceedings, 19th ACM Symposium on Theory of Computing, 1987, pp.\u00a077\u201382.","DOI":"10.1145\/28395.28404"},{"key":"ref065","unstructured":"P.\u00a0Stark, Introduction to Numerical Methods, Macmillan, 1970."},{"key":"ref066","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(92)90003-T"},{"key":"ref067","doi-asserted-by":"publisher","DOI":"10.1137\/0220053"},{"issue":"42","key":"ref068","first-page":"230","volume":"2","author":"Turing A.M.","year":"1936","journal-title":"Proc. London Math. Soc."},{"key":"ref069","doi-asserted-by":"crossref","unstructured":"H.\u00a0Vollmer, Introduction to Circuit Complexity, Springer-Verlag, 1999.","DOI":"10.1007\/978-3-662-03927-4"},{"key":"ref070","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90202-K"},{"key":"ref071","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-56999-9"},{"key":"ref072","unstructured":"C.\u00a0Yap, Fundamental Problems in Algorithmic Algebra, Oxford University Press, 2000."},{"key":"ref073","unstructured":"C.\u00a0Yap, Pi is in Log Space, 2010, manuscript available at: https:\/\/cs.nyu.edu\/exact\/doc\/pi-log.pdf."},{"key":"ref074","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.10.004"},{"key":"ref075","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2004.01.006"},{"key":"ref076","doi-asserted-by":"publisher","DOI":"10.2140\/moscow.2020.9.407"}],"container-title":["Computability"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-220407","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/COM-220407","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-220407","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T16:02:56Z","timestamp":1777392176000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/COM-220407"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,14]]},"references-count":76,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,21]]}},"alternative-id":["10.3233\/COM-220407"],"URL":"https:\/\/doi.org\/10.3233\/com-220407","relation":{},"ISSN":["2211-3568","2211-3576"],"issn-type":[{"value":"2211-3568","type":"print"},{"value":"2211-3576","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,14]]}}}