Lower bounds for the complexity of restrictions of Boolean functions

DOI10.1016/S0166-218X(00)00361-9MaRDI QIDQ5954083zbMATH OpenFDO

Authors A. V. Chashkin

Publication date 14 February 2003

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

Full work available at URL https://doi.org/10.1016/S0166-218X(00)00361-9

zbMATH Keywords

Boolean functioncircuit size complexity

Mathematics Subject Classification ID

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

Review text

Given a Boolean function \(f\) and a set \(M\) of domains, the circuit size complexity of the most complicated restriction of \(f\) to some domain in \(M\) is studied. Upper and lower bounds, depending on the domain size, are established for wide classes of Boolean functions. Similar results for other complexity measures (e.g., formula size) are given.

Recommendations

• On the complexity of restrictions of Boolean functions
• On estimates on the complexity of restrictions of Boolean functions
• Circuit complexity and multiplicative complexity of Boolean functions
• scientific article; zbMATH DE number 1256716
• Stochastic Algorithms: Foundations and Applications

Cites work

• Average case complexity for finite Boolean functions
• scientific article; zbMATH DE number 4095387 (Why is no real title available?)
• scientific article; zbMATH DE number 4187721 (Why is no real title available?)
• On estimates on the complexity of restrictions of Boolean functions

Cited in

(15)

• Reviewing bounds on the circuit size of the hardest functions
• Lower bounds on the area complexity of Boolean circuits
• Exact lower time bounds for computing Boolean functions on CREW PRAMs
• On estimates on the complexity of restrictions of Boolean functions
• Lower estimate for the cardinality of the domain of universal functions for the class of linear Boolean functions
• Upper Bounds on Boolean-Width with Applications to Exact Algorithms
• On the complexity of restrictions of Boolean functions
• A lower bound for the affinity level for almost all Boolean functions
• scientific article; zbMATH DE number 3867233 (Why is no real title available?)
• scientific article; zbMATH DE number 4095386 (Why is no real title available?)
• Local complexity of Boolean functions
• On domains completely specifying Boolean functions
• scientific article; zbMATH DE number 1746571 (Why is no real title available?)
• scientific article; zbMATH DE number 2174392 (Why is no real title available?)
• Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity

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

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