A 2.5n-Lower Bound on the Combinational Complexity of Boolean Functions
From MaRDI portal
Publication:4131019
DOI10.1137/0206030zbMATH Open0358.68081OpenAlexW2026399774MaRDI QIDQ4131019FDOQ4131019
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
Cited In (24)
- New lower bounds on circuit size of multi-output functions
- A 3n-lower bound on the network complexity of Boolean functions
- Lower bounds for depth-restricted branching programs
- Nonlinear lower bounds on the number of processors of circuits with sublinear separators
- Models of lower-bounds proofs
- Weighted Boolean formula games
- On the limits of gate elimination
- On Nečiporuk's theorem for branching programs
- On Negations in Boolean Networks
- Improving \(3N\) circuit complexity lower bounds
- Relativized circuit complexity
- Characterizing linear size circuits in terms of privacy
- Gate elimination for linear functions and new feebly secure constructions
- Circuit complexity of linear functions: gate elimination and feeble security
- Feebly secure cryptographic primitives
- On the complexity of planar Boolean circuits
- A Boolean function requiring 3n network size
- RelativizedNC
- Gate elimination: circuit size lower bounds and \#SAT upper bounds
- Characterization of all optimal networks for a simultaneous computation of AND and NOR
- Linear lower bounds on unbounded fan-in Boolean circuits
- The complexity of the standard multiplexer function in a class of switching 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 $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)
