Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > IRRATIONAL NUMBERS:
Reports tagged with Irrational Numbers:
TR22-053 | 24th April 2022
Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap

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

Revisions: 3 , Comments: 1

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 ... more >>>




ISSN 1433-8092 | Imprint