We prove that Parity requires $2^{n^{\Omega(1)}}$ size De Morgan circuits of constant depth using a new method which is completely “top-down” in the sense of [HJP95]. The proof relies crucially on the core ideas developed in a line of work [HJP95, PPZ99, MW19, GRSS24] which previously established top-down lower bounds ... more >>>

Robust Sunflower lemmas imply that any large enough monotone DNF of width $w$ contains a sunflower, i.e., a DNF equivalent to the conjunction of a common core with a DNF that is heavily biased towards $1$. While these lemmas are typically proved in the context of the uniform distribution or ... more >>>

We revisit the semantic size-cost-capacity technique (Beyersdorff, Blinkhorn & Hinde, 2019) for proof-size lower bounds in proof systems for quantified Boolean formulas (QBF). While the original technique is only applicable to weak proof systems with bounded capacity, we present a fine-grained generalisation of this technique that allows us to attack ... more >>>