Toward Better Depth Lower
Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function
Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function
arXiv:2410.10189v1 Announce Type: new
Abstract: Proving formula depth lower bounds is a fundamental challenge in complexity theory, with the strongest known bound of $(3 – o(1))log n$ established by Hastad over 25 years ago. The Karchmer–Raz–Wigderson (KRW) conjecture offers a promising approach …
