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

DOI10.1137/0206030MaRDI QIDQ4131019zbMATH OpenOpenAlexFDO

Authors 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

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Cited in

(24)

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

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

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