Circuit complexity

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Circuit complexity: from the worst case to the average case

Full text

Pdf (1.03 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing table of contents

Montreal, Quebec, Canada

Pages: 58 - 67

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Andreas Jakoby	Institut für Theoretische Informatik, Alexanderstraβe 10, 64283 Darmstadt, Germany
Rüdiger Reischuk	Institut für Theoretische Informatik, Alexanderstraβe 10, 64283 Darmstadt, Germany
Christian Schindelhauer	Institut für Theoretische Informatik, Alexanderstraβe 10, 64283 Darmstadt, Germany

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 21, Citation Count: 1

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/195058.195106 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	BCGL92	Shai Ben-David , Benny Chor , Oded Goldreich , Michael Luby, On the theory of average case complexity, Journal of Computer and System Sciences, v.44 n.2, p.193-219, April 1992 [doi>10.1016/0022-0000(92)90019-F]
	DGY89	Llana David , Ran Ginosar , Michael Yoeli, An efficient implementation of Boolean functions nd finite state machine as self-timed circuit, ACM SIGARCH Computer Architecture News, v.17 n.6, p.91-104, Dec. 1989 [doi>10.1145/77254.77262]
	Krap78	V. Krapchenko, Depth and Delay in a Network, Soviet Math. Dokl. 19, 1978, 1006- lOO9.
	Gure91	Yuri Gurevich, Average case completeness, Journal of Computer and System Sciences, v.42 n.3, p.346-398, June 1991 [doi>10.1016/0022-0000(91)90007-R]
	JRS94	A. jakoby, R. Reischuk, C. Schindelhauer, Malign Distributions for Nonuniform Average Case Complexity, Technical Report, TH Darmstadt, 1994.
	JRSW93	A. Jakoby, R. Reischuk, C. Schindelhauer, S. Weis, The Average Case' Complexity of the Parallel Prefix Problem, Technical Report, TH Darmstadt, 1993, to be presented at ICALP, 1994.
	LaFi80	Richard E. Ladner , Michael J. Fischer, Parallel Prefix Computation, Journal of the ACM (JACM), v.27 n.4, p.831-838, Oct. 1980 [doi>10.1145/322217.322232]
	LBS93	William K. C. Lam , Robert K. Brayton , Alberto L. Sangiovanni-Vincentelli, Circuit delay models and their exact computation using Timed Boolean Functions, Proceedings of the 30th international conference on Design automation, p.128-134, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164625]
	Levi86	Leonid A Levin, Average case complete problems, SIAM Journal on Computing, v.15 n.1, p.285-286, Feb. 1986 [doi>10.1137/0215020]
	LiVi92	Ming Li , Paul M. B. Vitányi, Average case complexity under the universal distribution equals worst-case complexity, Information Processing Letters, v.42 n.3, p.145-149, May 25, 1992 [doi>10.1016/0020-0190(92)90138-L ]
	Milt91	Peter Bro Miltersen, The complexity of malign measures, SIAM Journal on Computing, v.22 n.1, p.147-156, Feb. 1993 [doi>10.1137/0222012]
	Reif93	J. Reif, Probabilistic Parallel Prefix Computation, Comp. Math. Applic. 26, 1993, 101-110.
	ReSc93a	Rüdiger Reischuk , Christian Schindelhauer, Precise Average Case Complexity, Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science, p.650-661, February 25-27, 1993
	ReSc93b	R. Reischuk, C. Schindelhauer, Precise Average Case Complexity Measures, Technical Report, ICSI Berkeley, TR-93-049, August 1993.