Succinct certification of monotone circuits
From MaRDI portal
Publication:2232601
DOI10.1016/J.TCS.2021.07.032OpenAlexW3191986066MaRDI QIDQ2232601FDOQ2232601
Mateus Rodrigues Alves, Uéverton dos Santos Souza, Janio Carlos Nascimento Silva, Mateus de Oliveira Oliveira
Publication date: 6 October 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2021.07.032
Recommendations
- On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
- Lower bounds for Boolean circuits of bounded negation width
- On the planar monotone computation of Boolean functions
- Energy complexity of satisfying assignments in monotone circuits: on the complexity of computing the best case
- The monotone circuit complexity of Boolean functions
Cites Work
- Nondeterministic \(NC^1\) computation
- Parameterized Algorithms
- Quickly excluding a planar graph
- Title not available (Why is that?)
- Topological graph theory.
- Theory and Applications of Satisfiability Testing
- Title not available (Why is that?)
- On the parameterized complexity of multiple-interval graph problems
- Graph minors. III. Planar tree-width
- Diameter and treewidth in minor-closed graph families
- Improved bounds on the planar branchwidth with respect to the largest grid minor size
- Upper bounds for monotone planar circuit value and variants
- Contraction obstructions for treewidth
- On the Computational Power of Threshold Circuits with Sparse Activity
- Revisiting the complexity of and/or graph solution
- Diameter and treewidth in minor-closed graph families, revisited
- The complexity of polynomial-time approximation
- A \(c^k n\) 5-approximation algorithm for treewidth
- Tree-size bounded alternation
- Completely inapproximable monotone and antimonotone parameterized problems
- A New Pebble Game that Characterizes Parallel Complexity Classes
- Circuit Definitions of Nondeterministic Complexity Classes
- Positive and negative proofs for circuits and branching programs
- On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
- On the complexity of planar Boolean circuits
- Succinct monotone circuit certification: planarity and parameterized complexity
- Tractability, hardness, and kernelization lower bound for and/or graph solution
- Parameterized complexity of weighted satisfiability problems: decision, enumeration, counting
- Arithmetic Circuits and Polynomial Replacement Systems
Cited In (2)
This page was built for publication: Succinct certification of monotone circuits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2232601)
