New bounds for energy complexity of Boolean functions
From MaRDI portal
Publication:5918995
DOI10.1016/j.tcs.2020.09.003zbMath1467.68053arXiv1808.07199OpenAlexW2952185983MaRDI QIDQ5918995
M. N. Jayalal Sarma, Samir Otiv, Krishnamoorthy Dinesh
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
sensitivityBoolean circuitsenergy complexitydecision tree complexityformula sizeKarchmer-Wigderson games
Switching theory, applications of Boolean algebras to circuits and networks (94C11) Networks and circuits as models of computation; circuit complexity (68Q06)
Related Items (3)
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 ⋮ On the relationship between energy complexity and other Boolean function measures
Cites Work
- Unnamed Item
- Energy and fan-in of logic circuits computing symmetric Boolean functions
- Energy and depth of threshold circuits
- Size-energy tradeoffs for unate circuits computing symmetric Boolean functions
- Boolean function complexity. Advances and frontiers.
- Negation-limited formulas
- Exponential lower bounds on the size of constant-depth threshold circuits with small energy complexity
- A topological approach to evasiveness
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Alternation, sparsity and sensitivity: combinatorial bounds and exponential gaps
- Almost All Functions Require Exponential Energy
- Energy-efficient circuit design
- On the Inversion Complexity of a System of Functions
- On the Computational Power of Threshold Circuits with Sparse Activity
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
- Limiting Negations in Constant Depth Circuits
- Monotone circuits for matching require linear depth
- Communication Complexity
- New bounds for energy complexity of Boolean functions
- On the relationship between energy complexity and other Boolean function measures
This page was built for publication: New bounds for energy complexity of Boolean functions
