Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > CHINESE REMAINDER REPRESENTATION:
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 >>>




ISSN 1433-8092 | Imprint