Boolean Circuit Complexity and Two-Dimensional Cover Problems

Bruno P. Cavalar, Igor C. Oliveira

We reduce the problem of proving deterministic and nondeterministic Boolean circuit size lower bounds to the analysis of certain two-dimensional combinatorial cover problems. This…