AG 1, AG 2, AG 3, INET, AG 4, AG 5, D6, SWS, RG1, MMCI   Info

AG Audience

English

30 Minutes

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 Håstad over 25 years ago. The Karchmer-Raz-Wigderson conjecture offers a promising approach to advance these bounds and separate P from NC1. It suggests that the depth complexity of a function composition f \diamond g approximates the sum of the depth complexities of f and g.

Using the Karchmer-Wigderson (KW) relation framework, which translates formula depth into communication complexity, prior work has supported the conjecture under various relaxations—often replacing one or both KW relations with the universal relation or restricting the communication game through strong composition.

In my talk, I will provide an overview of these known results and present findings from our recent work. Specifically, we examine the strong composition of the parity function and a random Boolean function f.
We demonstrate that with probability 1-o(1), any protocol solving this composition requires depth at least (3 - o(1)) log n. This matches Håstad's bound while extending applicability to a broader class of inner functions, even when the outer function is simple.

Ina Geisler

+49 681 9325 1802

--email hidden

Zoom

passcode not visible

logged in users only