Energy and Fan-In of Threshold Circuits Computing Mod Functions | SpringerLink
Skip to main content

Energy and Fan-In of Threshold Circuits Computing Mod Functions

  • Conference paper
Theory and Applications of Models of Computation (TAMC 2011)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 6648))

Abstract

In this paper, we consider a threshold circuit C computing the modulus function MOD m , and investigate a relationship between two complexity measures, fan-in l and energy e of C, where the fan-in l is defined to be the maximum number of inputs of every gate in C, and the energy e to be the maximum number of gates outputting “1” over all inputs to C. We first prove that MOD m of n variables can be computed by a threshold circuit of fan-in l and energy e = O ( n/l ), and then provide an almost tight lower bound e = Ω((n − m)/l). Our results imply that there exists a tradeoff between the fan-in and energy of threshold circuits computing the modulus function.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Franco, L., Cannas, S.A.: Solving arithmetic problems using feed-forward neural networks. Neurocomputing 18, 61–79 (1998)

    Article  Google Scholar 

  2. Håstad, J., Goldmann, M.: On the power of small-depth threshold circuits. Computational Complexity 1, 113–129 (1993)

    Article  MathSciNet  Google Scholar 

  3. Laughlin, S.B., Sejnowski, T.J.: Communication in neuronal networks. Science 301(5641), 1870–1874 (2003)

    Article  Google Scholar 

  4. Lennie, P.: The cost of cortical computation. Current Biology 13, 493–497 (2003)

    Article  Google Scholar 

  5. Margrie, T.W., Brecht, M., Sakmann, B.: In vivo, low-resistance, whole-cell recordings from neurons in the anaesthetized and awake mammalian brain. Pflugers Arch. 444(4), 491–498 (2002)

    Article  Google Scholar 

  6. Shawe-Taylor, J.S., Anthony, M.H.G., Kern, W.: Classes of feedforward neural networks and their circuit complexity. Neural Networks 5, 971–977 (1992)

    Article  Google Scholar 

  7. Siu, K.Y., Roychowdhury, V., Kailath, T.: Toward massively parallel design of multipliers. Journal of Parallel and Distributed Computing 24, 86–93 (1995)

    Article  Google Scholar 

  8. Suzuki, A., Uchizawa, K., Zhou, X.: Energy-efficient threshold circuits computing mod functions. In: Potanin, A., Viglas, T. (eds.) Proceedings of the 17th Computing: The Australasian Theory Symposium, CRPIT, Perth, Australia, vol. 119, pp. 105–110. ACS (2011)

    Google Scholar 

  9. Uchizawa, K., Douglas, R., Maass, W.: On the computational power of threshold circuits with sparse activity. Neural Computation 18(12), 2994–3008 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  10. Uchizawa, K., Nishizeki, T., Takimoto, E.: Energy and depth of threshold circuits. Theoretical Computer Science (to appear)

    Google Scholar 

  11. Uchizawa, K., Takimoto, E.: Exponential lower bounds on the size of constant-depth threshold circuits with small energy complexity. Theoretical Computer Science 407(1-3), 474–487 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  12. Uchizawa, K., Takimoto, E., Nishizeki, T.: Size-energy tradeoffs of unate circuits computing symmetric Boolean functions. Theoretical Computer Science 412, 773–782 (2011)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2011 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Suzuki, A., Uchizawa, K., Zhou, X. (2011). Energy and Fan-In of Threshold Circuits Computing Mod Functions. In: Ogihara, M., Tarui, J. (eds) Theory and Applications of Models of Computation. TAMC 2011. Lecture Notes in Computer Science, vol 6648. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-20877-5_16

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-20877-5_16

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-20876-8

  • Online ISBN: 978-3-642-20877-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics