Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Chinese Remainder Representation:
TR00-065 | 7th September 2000
Eric Allender, David Mix Barrington

Uniform Circuits for Division: Consequences and Problems

Comments: 2

The essential idea in the fast parallel computation of division and
related problems is that of Chinese remainder representation
(CRR) -- storing a number in the form of its residues modulo many
small primes. Integer division provides one of the few natural
examples of problems for which ... more >>>

TR01-033 | 27th April 2001
Eric Allender, David Mix Barrington, William Hesse

Uniform Circuits for Division: Consequences and Problems

Integer division has been known to lie in P-uniform TC^0 since
the mid-1980's, and recently this was improved to DLOG-uniform
TC^0. At the time that the results in this paper were proved and
submitted for conference presentation, it was unknown whether division
lay in DLOGTIME-uniform TC^0 (also known as ... more >>>

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

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