On the mystery of negations in circuits: structure vs power

DOI10.1007/978-3-030-58150-3_46OpenAlexW3081991160MaRDI QIDQ2019505

Prashanth Amireddy, Sai Jayasurya, M. N. Jayalal Sarma

Publication date: 21 April 2021

Full work available at URL: https://doi.org/10.1007/978-3-030-58150-3_46

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Boolean function complexity. Advances and frontiers.
• On the minimum number of negations leading to super-polynomial savings
• On the complexity of slice functions
• The monotone circuit complexity of Boolean functions
• On the Inversion Complexity of a System of Functions
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Limiting Negations in Formulas
• Limiting Negations in Constant Depth Circuits
• Monotone circuits for matching require linear depth
• Depth Lower Bounds against Circuits with Sparse Orientation*
• Lower Bounds for DeMorgan Circuits of Bounded Negation Width
• A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)log log n Negation Gates

This page was built for publication: On the mystery of negations in circuits: structure vs power