A Boolean function requiring 3n network size

DOI10.1016/0304-3975(83)90029-4zbMATH Open0539.94036OpenAlexW2023412106MaRDI QIDQ794625FDOQ794625

Authors: Norbert Blum 

Publication date: 1984

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(83)90029-4

Recommendations

• scientific article; zbMATH DE number 3867233
• A 2.5 n lower bound on the monotone network complexity of \(T^ n_ 3\)
• Explicit lower bound of 4.5n - o(n) for boolena circuits
• On Negations in Boolean Networks
• Lower bounds to the complexity of symmetric Boolean functions

zbMATH Keywords

lower boundBoolean functionnetwork complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
• On the combinational complexity of certain symmetric Boolean functions
• A 3n-lower bound on the network complexity of Boolean functions
• A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions

Cited In (52)

• Tradeoffs for language recognition on alternating machines
• The complexity of depth-3 circuits computing symmetric Boolean functions
• A Feebly Secure Trapdoor Function
• New lower bounds on circuit size of multi-output functions
• Correlation bounds and \#SAT algorithms for small linear-size circuits
• A super-quadratic lower bound for depth four arithmetic circuits
• Is there an oblivious RAM lower bound for online reads?
• Lower bounds for depth-restricted branching programs
• Nonlinear lower bounds on the number of processors of circuits with sublinear separators
• Almost-natural proofs
• On the complexity of encoding in analog circuits
• Models of lower-bounds proofs
• Construction of Very Hard Functions for Multiparty Communication Complexity
• Size-treewidth tradeoffs for circuits computing the element distinctness function
• New upper bounds on the Boolean circuit complexity of symmetric functions
• On the limits of gate elimination
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Local reduction
• Is there an oblivious RAM lower bound for online reads?
• Title not available (Why is that?)
• On Negations in Boolean Networks
• Improving \(3N\) circuit complexity lower bounds
• Relativized circuit complexity
• Characterizing linear size circuits in terms of privacy
• The monotone circuit complexity of Boolean functions
• A Gödel Theorem on Network Complexity Lower Bounds
• A well-mixed function with circuit complexity \(5n\): tightness of the Lachish-Raz-type bounds
• Algebraic cryptography: new constructions and their security against provable break
• Correlation bounds and \#SAT algorithms for small linear-size circuits
• Circuit lower bounds from learning-theoretic approaches
• Reviewing bounds on the circuit size of the hardest functions
• Gate elimination for linear functions and new feebly secure constructions
• Notes on Boolean read-\(k\) and multilinear circuits
• Circuit complexity of linear functions: gate elimination and feeble security
• Feebly secure cryptographic primitives
• Complex Boolean networks obtained by diagonalization
• RelativizedNC
• Lower bounds for the size of nondeterministic circuits
• Hay from the haystack: explicit examples of exponential quantum circuit complexity
• Gate elimination: circuit size lower bounds and \#SAT upper bounds
• Nearly optimal hierarchies for network and formula size
• Linear lower bounds on unbounded fan-in Boolean circuits
• The complexity of central slice functions
• On shifting networks
• Title not available (Why is that?)
• Circuit lower bounds for average-case MA
• The complexity of contract negotiation
• Local reductions
• The multiplicative complexity of quadratic boolean forms
• On monotone simulations on nonmonotone networks
• 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 Boolean function requiring 3n network size

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