Circuit complexity and multiplicative complexity of Boolean functions

DOI10.1007/978-3-642-13962-8_27zbMATH Open1286.68200OpenAlexW1481719945MaRDI QIDQ3576211FDOQ3576211

Authors: Arist Kojevnikov, Alexander S. Kulikov 

Publication date: 29 July 2010

Published in: Programs, Proofs, Processes (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-13962-8_27

Recommendations

• On the multiplicative complexity of Boolean functions over the basis (\(\land,\oplus,1)\).
• On the multiplicative complexity of Boolean functions
• On the multiplicative complexity of some Boolean functions
• Multiplicative complexity of some Boolean functions
• Explicit lower bound of 4.5n - o(n) for boolena circuits

Mathematics Subject Classification ID

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

Cited In (22)

• On a hierarchy of Boolean functions hard to compute in constant depth
• New lower bounds on circuit size of multi-output functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Polynomial-time algorithms for checking some properties of Boolean functions given by polynomials
• Complexity of self-correcting circuits for some sequence of Boolean functions
• The minimal circuits for linear Boolean functions
• Shallow circuits and concise formulae for multiple addition and multiplication
• On the multiplicative complexity of quasi-quadratic Boolean functions
• The complexity and depth of Boolean circuits for multiplication and inversion in some fields \(\mathrm{GF}(2^{n})\)
• On the Complexity of Input/Output Logic
• Multiplicative complexity of some Boolean functions
• Improving \(3N\) circuit complexity lower bounds
• Lower bounds for the complexity of restrictions of Boolean functions
• The complexity of the descriptiveness of Boolean circuits over different sets of gates
• Complexity of fixed-size bit-vector logics
• On the multiplicative complexity of Boolean functions and bitsliced higher-order masking
• Gate elimination: circuit size lower bounds and \#SAT upper bounds
• The Power of Negative Thinking in Multiplying Boolean Matrices
• On the multiplicative complexity of some Boolean functions
• On the decision tree complexity of threshold functions

This page was built for publication: Circuit complexity and multiplicative complexity of Boolean functions

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