Published January 1, 1998 | Version public
Technical Report Open

Trading Weight Size for Circuit Depth: A Circuit for Comparison

Abstract

NOTE: Text or symbols not renderable in plain ASCII are indicated by [...]. Abstract included in .pdf document. We present an explicit construction of a circuit for the COMPARISON function in [...], the class of polynomial-size linear threshold circuits of depth two with polynomially growing weights. Goldmann and Karpinski proved that [...] in [4]. Hofmeister presented a simplified version of the same result in [6]. We have further simplified the results of these two papers by limiting ourselves to the simulation of COMPARISON. Our construction has size [...], a significant improvement on the general bound of [...] in [6].

Files

etr028.pdf

Files (996.7 kB)

Name Size Download all
md5:1307749da13326cbe8f3215a5641c928
614.6 kB Preview Download
md5:1379b1c0a5c377910a7fe87766bf6ec4
382.1 kB Download

Additional details

Identifiers

Eprint ID
26049
Resolver ID
CaltechPARADISE:1998.ETR028

Dates

Created
2002-09-03
Created from EPrint's datestamp field
Updated
2019-11-22
Created from EPrint's last_modified field

Caltech Custom Metadata

Caltech groups
Parallel and Distributed Systems Group