On the complexity of algebraic numbers, and the bit-complexity of straight-line programs

Eric Allender; Nikhil Balaji; Samir Datta; Rameshwar Pratap

doi:10.3233/COM-220407

On the complexity of algebraic numbers, and the bit-complexity of straight-line programs

Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap

School of Arts and Sciences, Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

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 TC 0 circuits for division, matrix powering, and related problems, where the improvement is in terms of 'majority depth' (initially studied by Maciel and Thérien). 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.

Original language	English (US)
Pages (from-to)	145-173
Number of pages	29
Journal	Computability
Volume	12
Issue number	2
DOIs	https://doi.org/10.3233/COM-220407
State	Published - Jun 21 2023

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science Applications
Computational Theory and Mathematics
Artificial Intelligence

Keywords

algebraic numbers
counting hierarchy
Threshold circuits

Access to Document

10.3233/COM-220407

Cite this

@article{c1be5c6bccac4f3882853bddf4397648,

title = "On the complexity of algebraic numbers, and the bit-complexity of straight-line programs",

abstract = "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 TC 0 circuits for division, matrix powering, and related problems, where the improvement is in terms of 'majority depth' (initially studied by Maciel and Th{\'e}rien). 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.",

keywords = "algebraic numbers, counting hierarchy, Threshold circuits",

author = "Eric Allender and Nikhil Balaji and Samir Datta and Rameshwar Pratap",

note = "Funding Information: The first author acknowledges the support of NSF grants CCF-1909216 and CCF-1909683. The second and the third authors were partially funded by a grant from Infosys Foundation. We would like to thank anonymous referees for help in improving the presentation of the paper, and we thank Howard Straubing and Bruno Grenet for helpful comments. Publisher Copyright: {\textcopyright} 2023 - IOS Press. All rights reserved.",

year = "2023",

month = jun,

day = "21",

doi = "10.3233/COM-220407",

language = "English (US)",

volume = "12",

pages = "145--173",

journal = "Computability",

issn = "2211-3568",

publisher = "IOS Press",

number = "2",

}

TY - JOUR

T1 - On the complexity of algebraic numbers, and the bit-complexity of straight-line programs

AU - Allender, Eric

AU - Balaji, Nikhil

AU - Datta, Samir

AU - Pratap, Rameshwar

N1 - Funding Information: The first author acknowledges the support of NSF grants CCF-1909216 and CCF-1909683. The second and the third authors were partially funded by a grant from Infosys Foundation. We would like to thank anonymous referees for help in improving the presentation of the paper, and we thank Howard Straubing and Bruno Grenet for helpful comments. Publisher Copyright: © 2023 - IOS Press. All rights reserved.

PY - 2023/6/21

Y1 - 2023/6/21

N2 - 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 TC 0 circuits for division, matrix powering, and related problems, where the improvement is in terms of 'majority depth' (initially studied by Maciel and Thérien). 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.

AB - 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 TC 0 circuits for division, matrix powering, and related problems, where the improvement is in terms of 'majority depth' (initially studied by Maciel and Thérien). 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.

KW - algebraic numbers

KW - counting hierarchy

KW - Threshold circuits

UR - http://www.scopus.com/inward/record.url?scp=85168335242&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85168335242&partnerID=8YFLogxK

U2 - 10.3233/COM-220407

DO - 10.3233/COM-220407

M3 - Article

AN - SCOPUS:85168335242

SN - 2211-3568

VL - 12

SP - 145

EP - 173

JO - Computability

JF - Computability

IS - 2

ER -

On the complexity of algebraic numbers, and the bit-complexity of straight-line programs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this