The conjunctive complexity of quadratic Boolean functions
type: Item
instance of: scholarly article
title: The conjunctive complexity of quadratic Boolean functions
zbMATH Open document ID: 0731.68049
DOI: 10.1016/0304-3975(91)90194-7
author: Katja Lenz
author: Ingo Wegener
published in: Theoretical Computer Science
publication date: 1991-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 4209598
zbMATH Keywords: circuit complexity
zbMATH Keywords: monotone circuits
zbMATH Keywords: quadratic Boolean functions
zbMATH Keywords: single level complexity
zbMATH Keywords: NP complete
zbMATH Keywords: conjunctive complexity
MaRDI profile type: Publication
full work available at URL: 0304-3975(91)90194-7
OpenAlex ID: W2067227060
cites work: Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
cites work: The monotone circuit complexity of Boolean functions
cites work: Decomposition of graphs and monotone formula size of homogeneous functions
cites work: On the coverings of graphs
cites work: Q5759552
cites work: Constructing $O(n\log n)$ Size Monotone Formulae for the kth Threshold Function of n Boolean Variables
cites work: Q4198056
cites work: Approximation algorithms for combinatorial problems
cites work: The multiplicative complexity of quadratic boolean forms
cites work: Q4770411
cites work: Graph complexity
cites work: Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices
cites work: On the complexity of slice functions
cites work: Q3762226
description: scientific article; zbMATH DE number 4209598