Succinct certification of monotone circuits

DOI10.1016/J.TCS.2021.07.032MaRDI QIDQ2232601zbMATH OpenOpenAlexFDO

Authors Mateus Rodrigues Alves, Mateus de Oliveira Oliveira, Janio Carlos Nascimento Silva, Uéverton dos Santos Souza

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

zbMATH Keywords

treewidthgenusplanarityFPTmonotone circuits

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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

• scientific article; zbMATH DE number 1256750 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• A New Pebble Game that Characterizes Parallel Complexity Classes
• A \(c^k n\) 5-approximation algorithm for treewidth
• Arithmetic Circuits and Polynomial Replacement Systems
• Circuit Definitions of Nondeterministic Complexity Classes
• Completely inapproximable monotone and antimonotone parameterized problems
• Contraction obstructions for treewidth
• Diameter and treewidth in minor-closed graph families
• Diameter and treewidth in minor-closed graph families, revisited
• Graph minors. III. Planar tree-width
• Improved bounds on the planar branchwidth with respect to the largest grid minor size
• Nondeterministic NC^1 computation
• On the Computational Power of Threshold Circuits with Sparse Activity
• On the complexity of planar Boolean circuits
• On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
• On the parameterized complexity of multiple-interval graph problems
• Parameterized algorithms
• Parameterized complexity of weighted satisfiability problems: decision, enumeration, counting
• Positive and negative proofs for circuits and branching programs
• Quickly excluding a planar graph
• Revisiting the complexity of and/or graph solution
• Succinct monotone circuit certification: planarity and parameterized complexity
• The complexity of polynomial-time approximation
• Theory and Applications of Satisfiability Testing
• Topological graph theory.
• Tractability, hardness, and kernelization lower bound for and/or graph solution
• Tree-size bounded alternation
• Upper bounds for monotone planar circuit value and variants

Cited in

(2)

• 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

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)