Limiting Negations in Constant Depth Circuits
From MaRDI portal
Publication:4032939
DOI10.1137/0222022zbMATH Open0770.68057OpenAlexW2038272454MaRDI QIDQ4032939FDOQ4032939
Authors:
Publication date: 17 May 1993
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0222022
Recommendations
- Limiting negations in non-deterministic circuits
- scientific article; zbMATH DE number 176507
- Algorithms and Computation
- Limiting negations in bounded-depth circuits: an extension of Markov's theorem
- scientific article; zbMATH DE number 1263235
- Limiting negations in bounded treewidth and upward planar circuits
- Negation-limited complexity of parity and inverters
- Negation-Limited Complexity of Parity and Inverters
- A logic for constant-depth circuits
- scientific article; zbMATH DE number 1379306
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cited In (18)
- Limiting negations in non-deterministic circuits
- A logic for constant-depth circuits
- On the minimum number of negations leading to super-polynomial savings
- Title not available (Why is that?)
- On the mystery of negations in circuits: structure vs power
- The average sensitivity of bounded-depth circuits
- Learning circuits with few negations
- Negation-limited formulas
- On negation complexity of injections, surjections and collision-resistance in cryptography
- Inhibited Effects in CP-Logic
- Algorithms and Computation
- Cancellation-free circuits in unbounded and bounded depth
- Limiting negations in bounded-depth circuits: an extension of Markov's theorem
- Lower bounds for Boolean circuits of bounded negation width
- Negation-Limited Inverters of Linear Size
- Limiting negations in bounded treewidth and upward planar circuits
- New bounds for energy complexity of Boolean functions
- Negation-limited circuit complexity of symmetric functions
This page was built for publication: Limiting Negations in Constant Depth Circuits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4032939)
