Almost all functions require exponential energy

DOI10.1007/978-3-662-48054-0_8MaRDI QIDQ2946379zbMATH OpenOpenAlexFDO

Authors Neal Barcelo, Michael Nugent, Michele Scquizzato, Kirk Pruhs

Publication date 16 September 2015

Published in Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-48054-0_8

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Switching theory, applications of Boolean algebras to circuits and networks (94C11) Fault detection; testing in circuits and networks (94C12)

Recommendations

• Energy-efficient circuit design
• Energy-efficient threshold circuits computing MOD functions
• Energy and depth of threshold circuits
• Energy and fan-in of logic circuits computing symmetric Boolean functions
• Exponential lower bounds on the size of constant-depth threshold circuits with small energy complexity

Cited in

(3)

• Computing the best-case energy complexity of satisfying assignments in monotone circuits
• On the relationship between energy complexity and other Boolean function measures
• New bounds for energy complexity of Boolean functions

This page was built for publication: Almost all functions require exponential energy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946379)