New bounds for energy complexity of Boolean functions

DOI10.1016/J.TCS.2020.09.003MaRDI QIDQ5918995zbMATH OpenOpenAlexFDO

Authors Krishnamoorthy Dinesh, Samir Otiv, Jayalal Sarma M. N.

Publication date 22 October 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.07199

zbMATH Keywords

Boolean circuitsdecision tree complexityenergy complexityformula sizeKarchmer-Wigderson gamessensitivity

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)

Abstract: $ewcommandECmathsfECewcommandKWmathsfKWewcommandDTmathsfDTewcommandpsensmathsfpsensewcommandcalBcalB$ For a Boolean function $f:{0,1}^{n}o0,1$ computed by a circuit $C$ over a finite basis $mathcalB$, the energy complexity of $C$ (denoted by $E{C}_{calB}(C)$) is the maximum over all inputs ${0,1}^n$ the numbers of gates of the circuit $C$ (excluding the inputs) that output a one. Energy Complexity of a Boolean function over a finite basis $calB$ denoted by $E{C}_{c}alB(f):=mi{n}_{C}E{C}_{calB}(C)$ where $C$ is a circuit over $calB$ computing $f$. We study the case when $calB=lan{d}_2,lo{r}_2,lnot$, the standard Boolean basis. It is known that any Boolean function can be computed by a circuit (with potentially large size) with an energy of at most $3n(1+epsilon(n))$ for a small $epsilon(n)$(which we observe is improvable to $3n-1$). We show several new results and connections between energy complexity and other well-studied parameters of Boolean functions. * For all Boolean functions $f$, $EC(f)leO(DT(f{)}^3)$ where $DT(f)$ is the optimal decision tree depth of $f$. * We define a parameter extit{positive sensitivity} (denoted by $psens$), a quantity that is smaller than sensitivity and defined in a similar way, and show that for any Boolean circuit $C$ computing a Boolean function $f$, $EC(C)gepsens(f)/3$. * For a monotone function $f$, we show that $EC(f)=Omega(K{W}^{+}(f))$ where $K{W}^{+}(f)$ is the cost of monotone Karchmer-Wigderson game of $f$. * Restricting the above notion of energy complexity to Boolean formulas, we show $EC(F)=Omegaleft(sqrtL(F)-depth(F)ight)$ where $L(F)$ is the size and $depth(F)$ is the depth of a formula $F$.

Recommendations

• New bounds for energy complexity of Boolean functions
• On the relationship between energy complexity and other Boolean function measures
• Energy Complexity and Depth of Threshold Circuits
• Energy and depth of threshold circuits
• Energy complexity of satisfying assignments in monotone circuits: on the complexity of computing the best case

Cites work

• A topological approach to evasiveness
• Almost all functions require exponential energy
• Alternation, sparsity and sensitivity: combinatorial bounds and exponential gaps
• Boolean function complexity. Advances and frontiers.
• Communication Complexity
• Energy and depth of threshold circuits
• Energy and fan-in of logic circuits computing symmetric Boolean functions
• Energy-efficient circuit design
• Exponential lower bounds on the size of constant-depth threshold circuits with small energy complexity
• scientific article; zbMATH DE number 609988 (Why is no real title available?)
• Limiting Negations in Constant Depth Circuits
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Monotone circuits for matching require linear depth
• Negation-limited formulas
• New bounds for energy complexity of Boolean functions
• On the Computational Power of Threshold Circuits with Sparse Activity
• On the Inversion Complexity of a System of Functions
• On the relationship between energy complexity and other Boolean function measures
• Size-energy tradeoffs for unate circuits computing symmetric Boolean functions
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes

Cited in

(12)

• Towards an energy complexity of computation
• A \(O(n\log ^2 n)\) checker and \(O(n^2\log n)\) filtering algorithm for the energetic reasoning
• Energy complexity of satisfying assignments in monotone circuits: on the complexity of computing the best case
• Computing the best-case energy complexity of satisfying assignments in monotone circuits
• Energy and fan-in of logic circuits computing symmetric Boolean functions
• New bounds for energy complexity of Boolean functions
• On the relationship between energy complexity and other Boolean function measures
• On the relationship between energy complexity and other Boolean function measures
• Relations between energy complexity measures of Boolean networks and positive sensitivity of Boolean functions
• Energy and output patterns in Boolean circuits
• On saving energy in Boolean circuits via negations
• Upper bound for output patterns of energy-bounded Boolean circuits, and its applications

This page was built for publication: New bounds for energy complexity of Boolean functions

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