The monotone circuit complexity of quadratic Boolean functions

DOI10.1007/S00453-006-0073-0MaRDI QIDQ2509028zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

quadratic functionssingle level conjunctive complexity

Mathematics Subject Classification ID

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

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

Cited in

(11)

• Quadratic sequential computations of Boolean mappings
• The Knuth-Yao quadrangle-inequality speedup is a consequence of total monotonicity
• scientific article; zbMATH DE number 4074972 (Why is no real title available?)
• An ${\mathcal{N} \mathcal{C}}$ Algorithm for Evaluating Monotone Planar Circuits
• ON THE COMPLEXITY OF CIRCUITS IN BASES CONTAINING MONOTONE ELEMENTS WITH ZERO WEIGHTS
• THE COMPLEXITY OF IMPLEMENTATION OF A SYSTEM OF MONOMIALS IN TWO VARIABLES BY COMPOSITION CIRCUITS
• Evaluating Monotone Circuits on Cylinders, Planes and Tori
• Algorithms and Computation
• Lower bounds for monotone q-multilinear Boolean circuits
• The conjunctive complexity of quadratic Boolean functions
• Reductions for monotone Boolean circuits

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)