Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR22-053 | 30th January 2023 17:31

On the Complexity of Algebraic Numbers, and the Bit-Complexity of Straight-Line Programs

RSS-Feed




Revision #3
Authors: Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap
Accepted on: 30th January 2023 17:31
Downloads: 108
Keywords: 


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 Therien). 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.



Changes to previous version:

Simplified proof of Theorem 40. Several other minor corrections.


Revision #2 to TR22-053 | 5th October 2022 16:02

On the Complexity of Algebraic Numbers, and the Bit-Complexity of Straight-Line Programs





Revision #2
Authors: Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap
Accepted on: 5th October 2022 16:02
Downloads: 149
Keywords: 


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 Therien). 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.



Changes to previous version:

Several minor corrections.


Revision #1 to TR22-053 | 5th October 2022 16:02

On the Complexity of Algebraic Numbers, and the Bit-Complexity of Straight-Line Programs





Revision #1
Authors: Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap
Accepted on: 5th October 2022 16:02
Downloads: 126
Keywords: 


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 Therien). 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.



Changes to previous version:

Several minor corrections.


Paper:

TR22-053 | 24th April 2022 01:24

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 Therien). 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.


Comment(s):

Comment #1 to TR22-053 | 6th October 2022 13:22

Revision #2 is identical to Revision #1

Authors: Eric Allender
Accepted on: 6th October 2022 13:22
Keywords: 


Comment:

Somehow 2 revisions were processed, although there is only one revision. Don't bother trying to find a difference between the two revisions.




ISSN 1433-8092 | Imprint