A class of Boolean functions with linear combinational complexity

DOI10.1016/0304-3975(75)90018-3zbMATH Open0322.68027OpenAlexW2055144305MaRDI QIDQ1223937FDOQ1223937

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

• Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computational Work and Time on Finite Machines
• On the complexity of the marriage problem
• Title not available (Why is that?)

Cited In (7)

• Nonlinear lower bounds on the number of processors of circuits with sublinear separators
• 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
• Lower bound on the complexity of finding polynomials of Boolean functions in the class of circuits with separated variables
• Linear lower bounds on unbounded fan-in Boolean circuits
• A nonlinear lower bound on the practical combinational complexity
• A nonlinear lower bound on the practical combinational complexity

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)