An exponential lower bound on the size of constant-depth threshold circuits with small energy complexity

Kei Uchizawa, Eiji Takimoto

研究成果: 書籍/レポート タイプへの寄稿会議への寄与

2 被引用数 (Scopus)

抄録

A complexity measure for threshold circuits, called the energy complexity, has been proposed to measure an amount of energy consumed during computation in the brain. Biological neurons need more energy to transmit a "spike" than not to transmit one, and hence the energy complexity of a threshold circuit is defined as the number of gates in the circuit that output "1" during computation. Since the firing activity of neurons in the brain is quite sparse, the following question arises: what Boolean functions can or cannot be computed by threshold circuits with small energy complexity. In the paper, we partially answer the question, that is, we show that there exists a tradeoff among three complexity measures of threshold circuits: the energy complexity, size, and depth. The tradeoff implies an exponential lower bound on the size of constant-depth threshold circuits with small energy complexity for a large class of Boolean functions.

本文言語英語
ホスト出版物のタイトルProceedings - Twenty-Second Annual IEEE Conference on Computational Complexity, CCC 2007
ページ169-178
ページ数10
DOI
出版ステータス出版済み - 2007
外部発表はい
イベント22nd Annual IEEE Conference on Computational Complexity, CCC 2007 - San Diego, CA, 米国
継続期間: 6月 13 20076月 16 2007

出版物シリーズ

名前Proceedings of the Annual IEEE Conference on Computational Complexity
ISSN(印刷版)1093-0159

その他

その他22nd Annual IEEE Conference on Computational Complexity, CCC 2007
国/地域米国
CitySan Diego, CA
Period6/13/076/16/07

!!!All Science Journal Classification (ASJC) codes

  • ソフトウェア
  • 理論的コンピュータサイエンス
  • 計算数学

フィンガープリント

「An exponential lower bound on the size of constant-depth threshold circuits with small energy complexity」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル