Computing the best-case energy complexity of satisfying assignments in monotone circuits
From MaRDI portal
Publication:2674710
DOI10.1016/j.tcs.2022.08.005OpenAlexW4292381393MaRDI QIDQ2674710
Uéverton S. Souza, Janio Carlos Nascimento Silva
Publication date: 14 September 2022
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2210.06739
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Revisiting the complexity of and/or graph solution
- Graph minors. III. Planar tree-width
- Positive and negative proofs for circuits and branching programs
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Quickly excluding a planar graph
- And/or-convexity: a graph convexity based on processes and deadlock models
- On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
- Succinct monotone circuit certification: planarity and parameterized complexity
- Energy complexity of satisfying assignments in monotone circuits: on the complexity of computing the best case
- Succinct certification of monotone circuits
- Contraction obstructions for treewidth
- Tractability, hardness, and kernelization lower bound for and/or graph solution
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- Almost All Functions Require Exponential Energy
- Energy-efficient circuit design
- Nonuniform ACC Circuit Lower Bounds
- On the Computational Power of Threshold Circuits with Sparse Activity
- Amplifying lower bounds by means of self-reducibility
- Circuit Definitions of Nondeterministic Complexity Classes
- Energy Complexity of Recurrent Neural Networks
- Parameterized Algorithms
- New bounds for energy complexity of Boolean functions
This page was built for publication: Computing the best-case energy complexity of satisfying assignments in monotone circuits
