A Boolean function requiring 3n network size
From MaRDI portal
Publication:794625
DOI10.1016/0304-3975(83)90029-4zbMath0539.94036OpenAlexW2023412106MaRDI QIDQ794625
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
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (45)
The complexity of central slice functions ⋮ Local Reductions ⋮ On the limits of gate elimination ⋮ The monotone circuit complexity of Boolean functions ⋮ Lower bounds on the size of bounded depth circuits over a complete basis with logical addition ⋮ The complexity of depth-3 circuits computing symmetric Boolean functions ⋮ On the complexity of encoding in analog circuits ⋮ Local reduction ⋮ Circuit lower bounds from learning-theoretic approaches ⋮ Models of lower-bounds proofs ⋮ Correlation bounds and \#SAT algorithms for small linear-size circuits ⋮ 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 ⋮ Tradeoffs for language recognition on alternating machines ⋮ On monotone simulations on nonmonotone networks ⋮ RelativizedNC ⋮ Hay from the haystack: explicit examples of exponential quantum circuit complexity ⋮ Improving \(3N\) circuit complexity lower bounds ⋮ A well-mixed function with circuit complexity \(5n\): tightness of the Lachish-Raz-type bounds ⋮ Feebly secure cryptographic primitives ⋮ Circuit complexity of linear functions: gate elimination and feeble security ⋮ Size-treewidth tradeoffs for circuits computing the element distinctness function ⋮ Gate elimination: circuit size lower bounds and \#SAT upper bounds ⋮ Lower bounds for depth-restricted branching programs ⋮ The complexity of contract negotiation ⋮ Nonlinear lower bounds on the number of processors of circuits with sublinear separators ⋮ A nonlinear lower bound on the practical combinational complexity ⋮ Gate Elimination for Linear Functions and New Feebly Secure Constructions ⋮ The multiplicative complexity of quadratic boolean forms ⋮ Almost-natural proofs ⋮ Is there an oblivious RAM lower bound for online reads? ⋮ Is there an oblivious RAM lower bound for online reads? ⋮ New upper bounds on the Boolean circuit complexity of symmetric functions ⋮ A nonlinear lower bound on the practical combinational complexity ⋮ Algebraic cryptography: new constructions and their security against provable break ⋮ A Feebly Secure Trapdoor Function ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ On Negations in Boolean Networks ⋮ Construction of Very Hard Functions for Multiparty Communication Complexity ⋮ Characterizing linear size circuits in terms of privacy ⋮ Complex Boolean networks obtained by diagonalization ⋮ Linear lower bounds on unbounded fan-in Boolean circuits ⋮ Relativized circuit complexity ⋮ New lower bounds on circuit size of multi-output functions
Cites Work
This page was built for publication: A Boolean function requiring 3n network size
