Circuit Complexity and Multiplicative Complexity of Boolean Functions

DOI10.1007/978-3-642-13962-8_27zbMath1286.68200OpenAlexW1481719945MaRDI QIDQ3576211

Alexander S. Kulikov, Arist Kojevnikov

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

Mathematics Subject Classification ID

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

Related Items (7)

Polynomial-time algorithms for checking some properties of Boolean functions given by polynomials ⋮ Improving \(3N\) circuit complexity lower bounds ⋮ Gate elimination: circuit size lower bounds and \#SAT upper bounds ⋮ On the decision tree complexity of threshold functions ⋮ On the multiplicative complexity of some Boolean functions ⋮ New lower bounds on circuit size of multi-output functions ⋮ On the multiplicative complexity of quasi-quadratic Boolean functions

This page was built for publication: Circuit Complexity and Multiplicative Complexity of Boolean Functions