New lower bounds on circuit size of multi-output functions
From MaRDI portal
Publication:2354591
DOI10.1007/s00224-014-9590-4zbMath1331.68084OpenAlexW2084301310MaRDI QIDQ2354591
O. Melanich, Evgeny Demenkov, Ivan Mihajlin, Alexander S. Kulikov
Publication date: 20 July 2015
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-014-9590-4
Related Items
Improving \(3N\) circuit complexity lower bounds, Gate elimination: circuit size lower bounds and \#SAT upper bounds
Cites Work
- Unnamed Item
- Unnamed Item
- A Boolean function requiring 3n network size
- Characterization of all optimal networks for a simultaneous computation of AND and NOR
- Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
- The combinational complexity of equivalence
- A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
- An Elementary Proof of a 3n − o(n) Lower Bound on the Circuit Complexity of Affine Dispersers
- A $4n$ Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions
- Circuit Complexity and Multiplicative Complexity of Boolean Functions
- A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
- On the combinational complexity of certain symmetric Boolean functions
- Explicit lower bound of 4.5n - o(n) for boolena circuits
