A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions

DOI10.1137/0206030zbMath0358.68081OpenAlexW2026399774MaRDI QIDQ4131019

Wolfgang J. Paul

Publication date: 1977

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0206030

Mathematics Subject Classification ID

Related Items (24)

On the limits of gate elimination ⋮ Weighted Boolean Formula Games ⋮ Models of lower-bounds proofs ⋮ On Nečiporuk's theorem for branching programs ⋮ RelativizedNC ⋮ A 3n-lower bound on the network complexity of Boolean functions ⋮ Improving \(3N\) circuit complexity lower bounds ⋮ Feebly secure cryptographic primitives ⋮ Circuit complexity of linear functions: gate elimination and feeble security ⋮ Gate elimination: circuit size lower bounds and \#SAT upper bounds ⋮ Lower bounds for depth-restricted branching programs ⋮ Nonlinear lower bounds on the number of processors of circuits with sublinear separators ⋮ A nonlinear lower bound on the practical combinational complexity ⋮ Gate Elimination for Linear Functions and New Feebly Secure Constructions ⋮ A nonlinear lower bound on the practical combinational complexity ⋮ On Negations in Boolean Networks ⋮ On the complexity of planar Boolean circuits ⋮ A Boolean function requiring 3n network size ⋮ The complexity of the standard multiplexer function in a class of switching circuits ⋮ Characterizing linear size circuits in terms of privacy ⋮ Characterization of all optimal networks for a simultaneous computation of AND and NOR ⋮ Linear lower bounds on unbounded fan-in Boolean circuits ⋮ Relativized circuit complexity ⋮ New lower bounds on circuit size of multi-output functions

This page was built for publication: A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions