A Boolean function requiring 3n network size

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

Cites work

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

Cited in

(52)

A nonlinear lower bound on the practical combinational complexity
Tradeoffs for language recognition on alternating machines
The complexity of depth-3 circuits computing symmetric Boolean functions
New lower bounds on circuit size of multi-output functions
A Feebly Secure Trapdoor Function
Correlation bounds and \#SAT algorithms for small linear-size circuits
Lower bounds for depth-restricted branching programs
Nonlinear lower bounds on the number of processors of circuits with sublinear separators
A super-quadratic lower bound for depth four arithmetic circuits
Is there an oblivious RAM lower bound for online reads?
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
scientific article; zbMATH DE number 176876 (Why is no real title available?)
On Negations in Boolean Networks
Is there an oblivious RAM lower bound for online reads?
Relativized circuit complexity
Characterizing linear size circuits in terms of privacy
The monotone circuit complexity of Boolean functions
Improving $3N$ circuit complexity lower bounds
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
Gate elimination: circuit size lower bounds and \#SAT upper bounds
Lower bounds for the size of nondeterministic circuits
Nearly optimal hierarchies for network and formula size
Linear lower bounds on unbounded fan-in Boolean circuits
The complexity of central slice functions
Hay from the haystack: explicit examples of exponential quantum circuit complexity
On shifting networks
scientific article; zbMATH DE number 3937107 (Why is no real title available?)
Circuit lower bounds for average-case MA
The complexity of contract negotiation
Local reductions
The multiplicative complexity of quadratic boolean forms
A nonlinear lower bound on the practical combinational complexity
On monotone simulations on nonmonotone networks

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)