Note on the power of threshold circuits

Research output: Chapter in Book/Report/Conference proceedingConference contribution

62 Scopus citations

Abstract

The author presents a very simple proof of the fact that any language accepted by polynomial-size depth-k unbounded-fan-in circuits of AND and OR gates is accepted by depth-three threshold circuits of size n raised to the power O(logkn). The proof uses much of the intuition of S. Toda's result that the polynomial hierarchy is contained in P#P (30th Ann. Symp. Foundations Comput. Sci., pp. 514-519, 1989).

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science - Proceedings
PublisherPubl by IEEE
Pages580-584
Number of pages5
ISBN (Print)0818619821, 9780818619823
StatePublished - Nov 1989
Event30th Annual Symposium on Foundations of Computer Science - Research Triangle Park, NC, USA
Duration: Oct 30 1989Nov 1 1989

Publication series

NameAnnual Symposium on Foundations of Computer Science - Proceedings
ISSN (Print)0272-5428

Other

Other30th Annual Symposium on Foundations of Computer Science
CityResearch Triangle Park, NC, USA
Period10/30/8911/1/89

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Note on the power of threshold circuits'. Together they form a unique fingerprint.

Cite this