Revision #3 Authors: Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap

Accepted on: 30th January 2023 17:31

Downloads: 108

Keywords:

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.

Simplified proof of Theorem 40. Several other minor corrections.

Revision #2 Authors: Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap

Accepted on: 5th October 2022 16:02

Downloads: 149

Keywords:

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.

Several minor corrections.

Revision #1 Authors: Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap

Accepted on: 5th October 2022 16:02

Downloads: 126

Keywords:

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.

Several minor corrections.

TR22-053 Authors: Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap

Publication: 24th April 2022 01:56

Downloads: 471

Keywords:

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.

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