2 papers
cs.CC2026
Top-Down Lower Bounds for All Depths
Oliver Korten
We prove that Parity requires size De Morgan circuits of constant depth using a new method which is completely "top-down" in the sense of [HJP95]. The proof relies c…
cs.CC2021
The Hardest Explicit Construction
Oliver Korten
We investigate the complexity of explicit construction problems, where the goal is to produce a particular object of size possessing some pseudorandom property in time polynomi…