ECCC-Report TR00-065https://eccc.weizmann.ac.il/report/2000/065Comments and Revisions published for TR00-065en-usFri, 11 May 2001 12:28:18 +0300
Comment 2
| This paper has been superceded. |
Eric Allender
https://eccc.weizmann.ac.il/report/2000/065#comment2This paper became obsolete shortly after it appeared in ECCC.
A new paper (with William Hesse as co-author) is now available
as ECCC report TR01-033.
Fri, 11 May 2001 12:28:18 +0300https://eccc.weizmann.ac.il/report/2000/065#comment2
Comment 1
| Update on Division: Uniform NC^1 Comment on: TR00-065 |
Eric Allender,
David Mix Barrington
https://eccc.weizmann.ac.il/report/2000/065#comment1The MS thesis of Andrew Chiu:
("Complexity of Parallel Arithmetic Using the
Chinese Remainder Representation"
University of Wisconsin-Milwaukee, August, 1995)
contains an algorithm for integer division, that
can be implemented in Atime(log n) (i.e., in the
most uniform version of NC^1). Our ECCC Submission
will be revised soon, to reflect this.
Fri, 11 May 2001 12:27:03 +0300https://eccc.weizmann.ac.il/report/2000/065#comment1
Paper TR00-065
| Uniform Circuits for Division: Consequences and Problems |
Eric Allender,
David Mix Barrington
https://eccc.weizmann.ac.il/report/2000/065The 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 all currently-known constructions of
efficient circuits rely on some sort of extra information or
non-uniformity; the major stumbling block has seemed to be the
difficulty of converting from CRR to binary. We give new bounds on
the nonuniformity required for division; it is necessary and
sufficient to be able to compute discrete logarithms modulo an
O(log n) bit number. In particular, we show that the necessary
uniformity predicates lie in a class that (provably) does not
contain L.
The fact that CRR operations can be carried out in log space has
interesting implications for small space classes. We define two
versions of s(n) space for s(n)=o(log n): dspace(s(n)) as the
traditional version where the worktape begins blank, and DSPACE(s(n))
where the space bound is established by endmarkers before the
computation starts. We present a new translational lemma, and
derive as a consequence that (for example), if one can improve the
result of [Hartmanis,Berman] that {0^n : n is prime} is not in
dspace(loglog n) to show that {0^n : n is prime} is not in
DSPACE(loglog n), it would follow that L is not equal to NP.
Fri, 08 Sep 2000 08:31:22 +0300https://eccc.weizmann.ac.il/report/2000/065