Lower bounds for the complexity of restrictions of Boolean functions

DOI10.1016/S0166-218X(00)00361-9zbMath1006.94035MaRDI QIDQ5954083

A. V. Chashkin

Publication date: 14 February 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

Boolean functioncircuit size complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (1)

Local complexity of Boolean functions

Cites Work

• Unnamed Item
• Unnamed Item
• On estimates on the complexity of restrictions of Boolean functions
• Average case complexity for finite Boolean functions

This page was built for publication: Lower bounds for the complexity of restrictions of Boolean functions