A class of Boolean functions with linear combinational complexity

DOI10.1016/0304-3975(75)90018-3zbMath0322.68027OpenAlexW2055144305MaRDI QIDQ1223937

W. N. Hsieh, Lawrence H. Harper, John E. Savage

Publication date: 1975

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(75)90018-3

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Factorials, binomial coefficients, combinatorial functions (05A10) Algorithms in computer science (68W99)

Related Items

Lower bound on the complexity of finding polynomials of Boolean functions in the class of circuits with separated variables ⋮ Nonlinear lower bounds on the number of processors of circuits with sublinear separators ⋮ A nonlinear lower bound on the practical combinational complexity ⋮ On the combinational complexity of certain symmetric Boolean functions ⋮ A nonlinear lower bound on the practical combinational complexity ⋮ Interpolation of the discrete logarithm in \(\mathbb{F}_{q}\) by Boolean functions and by polynomials in several variables modulo a divisor of \(q-1\). ⋮ Linear lower bounds on unbounded fan-in Boolean circuits

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
• On the complexity of the marriage problem
• Computational Work and Time on Finite Machines