Trading Weight Size for Circuit Depth: A Circuit for Comparison

Bohossian, V. and Riedel, M. and Bruck, J. (1998) Trading Weight Size for Circuit Depth: A Circuit for Comparison. Technical Report. California Institute of Technology. [CaltechPARADISE:1998.ETR028]

Full text available as:

	PDF (Adobe PDF (614KB)) - Requires Adobe Acrobat Reader or other PDF viewer.
	Postscript - Requires a viewer, such as GhostView

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

EPrint Type:	Monograph (Technical Report)
Additional Information:	[Alternate URL: http://www.paradise.caltech.edu/papers/etr028.ps]
Subjects:	All Records
ID Code:	25
Deposited By:	Jehoshua Bruck
Deposited On:	03 September 2002
Record Number:	CaltechPARADISE:1998.ETR028
Official Persistent URL:	http://resolver.caltech.edu/CaltechPARADISE:1998.ETR028
Usage Policy:	You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.

Archive Staff Only: edit this record