A 5n - o(n) lower bound on the circuit size over U _2 of a linear Boolean function

DOI10.1007/978-3-642-30870-3_44MaRDI QIDQ2904438zbMATH OpenOpenAlexFDO

Authors O. Melanich, Ivan Mihajlin, Alexander S. Kulikov

Publication date 14 August 2012

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-30870-3_44

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• New lower bounds on circuit size of multi-output functions
• A lower bound on circuit complexity of vector function in \(U _{2}\)
• Explicit lower bound of 4.5n - o(n) for boolena circuits
• Lower bounds on the formula complexity of a linear Boolean function
• Linear Circuits over $\operatorname{GF}(2)$

Cited in

(11)

• Local reduction
• 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
• A lower bound on circuit complexity of vector function in \(U _{2}\)
• A note on the quasi-additive bound for Boolean functions
• Lower bounds for the size of nondeterministic circuits
• Local reductions
• Linear Circuits over $\operatorname{GF}(2)$
• A Well-Mixed Function with Circuit Complexity 5n ±o(n): Tightness of the Lachish-Raz-Type Bounds
• A super-quadratic lower bound for depth four arithmetic circuits
• Explicit lower bound of 4.5n - o(n) for boolena circuits

This page was built for publication: A \(5n - o(n)\) lower bound on the circuit size over \(U _{2}\) of a linear Boolean function

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