Some remarks on Boolean sums
From MaRDI portal
Publication:1133518
DOI10.1007/BF00268321zbMath0421.94022MaRDI QIDQ1133518
Publication date: 1979
Published in: Acta Informatica (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)
Related Items
Separating OR, SUM, and XOR circuits, \(\text{PI}_ k\) mass production and an optimal circuit for the Nečiporuk slice, A method for obtaining efficient lower bounds for monotone complexity, Boolean functions whose monotone complexity is of size \(n^ 2\) / log n, On algorithm complexity, Lower bounds for tropical circuits and dynamic programs, On a small class of Boolean sums, On Negations in Boolean Networks, A very simple function that requires exponential size read-once branching programs., Cancellation-free circuits in unbounded and bounded depth, An \(\Omega (n^{4/3})\) lower bound on the monotone network complexity of the \(n\)-th degree convolution
Cites Work
