A class of Boolean functions with linear combinational complexity

DOI10.1016/0304-3975(75)90018-3MaRDI QIDQ1223937zbMATH OpenOpenAlexFDO

Authors W. N. Hsieh, Lawrence H. Harper, John 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)

Cites work

• scientific article; zbMATH DE number 3133387 (Why is no real title available?)
• scientific article; zbMATH DE number 3428536 (Why is no real title available?)
• scientific article; zbMATH DE number 3257409 (Why is no real title available?)
• scientific article; zbMATH DE number 3356467 (Why is no real title available?)
• Computational Work and Time on Finite Machines
• On the complexity of the marriage problem
• Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen

Cited in

(7)

• Linear lower bounds on unbounded fan-in Boolean circuits
• Interpolation of the discrete logarithm in \(\mathbb{F}_{q}\) by Boolean functions and by polynomials in several variables modulo a divisor of \(q-1\).
• On the combinational complexity of certain symmetric Boolean functions
• A nonlinear lower bound on the practical combinational complexity
• A nonlinear lower bound on the practical combinational complexity
• 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

This page was built for publication: A class of Boolean functions with linear combinational complexity

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