A Boolean function requiring 3n network size
One of the most difficult problems in complexity theory is proving a nonlinear lower bound for the network complexity of an explicit Boolean function. Although it is well known by a counting argument that relative to the full basis most Boolean functions need exponentially many operations, only linear lower bounds with small constant factor are known for explicit Boolean functions. \textit{W. J. Paul} [SIAM J. Comput. 6, 427- 443 (1977; Zbl 0358.68081)] has proved a 2.5n-lower bound over the complete basis over all binary functions for an explicit Boolean function. We modify the definition of Paul's function slightly and prove a 3n-lower bound for the network complexity of that function. This is the best known lower bound over the complete basis of all binary Boolean functions.
- Reviewing bounds on the circuit size of the hardest functions
- Complex Boolean networks obtained by diagonalization
- Nearly optimal hierarchies for network and formula size
- Linear lower bounds on unbounded fan-in Boolean circuits
- Relativized circuit complexity
- The complexity of central slice functions
- The monotone circuit complexity of Boolean functions
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Models of lower-bounds proofs
- Tradeoffs for language recognition on alternating machines
- On monotone simulations on nonmonotone networks
- Lower bounds for depth-restricted branching programs
- Nonlinear lower bounds on the number of processors of circuits with sublinear separators
- The multiplicative complexity of quadratic boolean forms
- Characterizing linear size circuits in terms of privacy
- On the complexity of encoding in analog circuits
- On the limits of gate elimination
- Local reduction
- Size-treewidth tradeoffs for circuits computing the element distinctness function
- Gate elimination: circuit size lower bounds and \#SAT upper bounds
- Feebly secure cryptographic primitives
- Circuit complexity of linear functions: gate elimination and feeble security
- New lower bounds on circuit size of multi-output functions
- A well-mixed function with circuit complexity \(5n\): tightness of the Lachish-Raz-type bounds
- The complexity of contract negotiation
- Circuit lower bounds from learning-theoretic approaches
- Gate elimination for linear functions and new feebly secure constructions
- Algebraic cryptography: new constructions and their security against provable break
- Circuit lower bounds for average-case MA
- Correlation bounds and \#SAT algorithms for small linear-size circuits
- Lower bounds for the size of nondeterministic circuits
- A Feebly Secure Trapdoor Function
- Correlation bounds and \#SAT algorithms for small linear-size circuits
- Local reductions
- On Negations in Boolean Networks
- A Gödel Theorem on Network Complexity Lower Bounds
- scientific article; zbMATH DE number 3937107 (Why is no real title available?)
- RelativizedNC
- scientific article; zbMATH DE number 176876 (Why is no real title available?)
- Construction of Very Hard Functions for Multiparty Communication Complexity
- A super-quadratic lower bound for depth four arithmetic circuits
- A nonlinear lower bound on the practical combinational complexity
- Is there an oblivious RAM lower bound for online reads?
- Is there an oblivious RAM lower bound for online reads?
- Hay from the haystack: explicit examples of exponential quantum circuit complexity
- Improving \(3N\) circuit complexity lower bounds
- Notes on Boolean read-k and multilinear circuits
- A nonlinear lower bound on the practical combinational complexity
- On shifting networks
- Linear-size Boolean circuits for multiselection
- Almost-natural proofs
- The complexity of depth-3 circuits computing symmetric Boolean functions
- New upper bounds on the Boolean circuit complexity of symmetric functions
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)