Given a circuit $C : \{0,1\}^n \to \{0,1\}^m$ from a circuit class $F$, with $m > n$, finding a $y \in \{0,1\}^m$ such that $\forall x \in \{0,1\}^n$, $C(x) \ne y$, is the range avoidance problem (denoted by $F$-AVOID). It is known that deterministic polynomial time algorithms (even with access ... more >>>

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 is obtained by combining results of Razborov (1989), Karchmer (1993), and Wigderson (1993) in the context of the fusion method for circuit lower bounds with the ... more >>>

We prove that polynomial calculus (and hence also Nullstellensatz) over any field requires linear degree to refute that sparse random regular graphs, as well as sparse Erd?s-Rényi random graphs, are 3-colourable. Using the known relation between size and degree for polynomial calculus proofs, this implies strongly exponential lower bounds on ... more >>>