The monotone circuit complexity of quadratic Boolean functions

DOI10.1007/S00453-006-0073-0zbMATH Open1100.68040OpenAlexW2056263286MaRDI QIDQ2509028FDOQ2509028

Authors: Kazuyuki Amano, A. Maruoka 

Publication date: 16 October 2006

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-006-0073-0

Recommendations

• Algorithms and Computation
• The conjunctive complexity of quadratic Boolean functions
• scientific article; zbMATH DE number 4074972
• Disproving the Single Level Conjecture
• scientific article; zbMATH DE number 3867233

zbMATH Keywords

quadratic functionssingle level conjunctive complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (9)

• Evaluating Monotone Circuits on Cylinders, Planes and Tori
• Reductions for monotone Boolean circuits
• ON THE COMPLEXITY OF CIRCUITS IN BASES CONTAINING MONOTONE ELEMENTS WITH ZERO WEIGHTS
• Algorithms and Computation
• An ${\mathcal{N} \mathcal{C}}$ Algorithm for Evaluating Monotone Planar Circuits
• The Knuth-Yao quadrangle-inequality speedup is a consequence of total monotonicity
• Title not available (Why is that?)
• THE COMPLEXITY OF IMPLEMENTATION OF A SYSTEM OF MONOMIALS IN TWO VARIABLES BY COMPOSITION CIRCUITS
• Quadratic sequential computations of Boolean mappings

This page was built for publication: The monotone circuit complexity of quadratic Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2509028)