@article{Allender:2023aa,
    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.},
    Author = {Allender, Eric and Balaji, Nikhil and Datta, Samir and Pratap, Rameshwar},
    File = {On the Complexity of Algebraic Numbers, and the Bit-Complexity of Straight-Line Programs - algebraic.pdf},
    ISBN = {2211-3576},
    Journal = {Computability},
    Keywords = {Threshold circuits; counting hierarchy; algebraic numbers},
    Number = {2},
    Pages = {145--173},
    Publisher = {IOS Press},
    Title = {On the complexity of algebraic numbers, and the bit-complexity of straight-line programs 1},
    Volume = {12},
    Year = {2023},
    bdsk-url-1 = {https://doi.org/10.3233/COM-220407},
    date-added = {2023-10-06 14:55:19 +0200},
    date-modified = {2023-10-06 14:55:19 +0200},
    doi = {10.3233/COM-220407}
}

@article{Allender:2023aa, 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.}, Author = {Allender, Eric and Balaji, Nikhil and Datta, Samir and Pratap, Rameshwar}, File = {On the Complexity of Algebraic Numbers, and the Bit-Complexity of Straight-Line Programs - algebraic.pdf}, ISBN = {2211-3576}, Journal = {Computability}, Keywords = {Threshold circuits; counting hierarchy; algebraic numbers}, Number = {2}, Pages = {145--173}, Publisher = {IOS Press}, Title = {On the complexity of algebraic numbers, and the bit-complexity of straight-line programs 1}, Volume = {12}, Year = {2023}, bdsk-url-1 = {https://doi.org/10.3233/COM-220407}, date-added = {2023-10-06 14:55:19 +0200}, date-modified = {2023-10-06 14:55:19 +0200}, doi = {10.3233/COM-220407} }