Lower bounds for the complexity of restrictions of Boolean functions (Q5954083)

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.