[Proof Complexity] MIAO seminar Wed Apr 17 at 14:00 CE(S)T with Or Meir: Toward better depth lower bounds: A KRW-like theorem for strong composition

[Jakob Nordström]

Dear all,

On Wednesday April 17 at 14:00 CE(S)T we will have the opportunity to enjoy a seminar with Or Meir from the University of Haifa, who will give a talk titled "Toward better depth lower bounds: A KRW-like theorem for strong composition". You find the abstract at the bottom of this message.

This will be a video seminar at https://lu-se.zoom.us/j/61925271827. Please feel free to share this information with colleagues who you think might be interested. We are also hoping to record the seminar and post on the MIAO Research YouTube channel https://youtube.com/@MIAOresearch for people who would like to hear the talk but cannot attend.

Most of our seminars consist of two parts: first a 50-55-minute regular talk, and then after a break a ca-1-hour in-depth technical presentation with (hopefully) a lot of interaction. The intention is that the first part of the seminar will give all listeners a self-contained overview of some exciting research results, and after the break people who have the time and interest will get an opportunity to really get into the technical details. (However, for those who feel that the first part was enough, it is perfectly fine to just discretely drop out during the break. No questions asked; no excuses needed.)

More information about upcoming MIAO seminars can be found at https://jakobnordstrom.se/miao-seminars/. If you do not wish to receive these announcements, or receive several copies of them, please send a message to jn at di.ku.dk.

Best regards,
Jakob Nordström

**********

Wednesday Apr 17 at 14:00 CET on Zoom
Toward better depth lower bounds: A KRW-like theorem for strong composition
(Or Meir, University of Haifa)

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits. Karchmer, Raz, and Wigderson (Computational Complexity 5(3/4), 1995) suggested approaching this problem by proving that depth complexity of a composition of two functions is roughly the sum of their individual depth complexities. They showed that the validity of this conjecture would imply the desired lower bounds.

The intuition that underlies the KRW conjecture is that composition should behave like a "direct-sum problem", in a certain sense, and therefore the depth complexity of the composition should be the sum of the individual depth complexities. Nevertheless, there are two obstacles toward turning this intuition into a proof: first, we do not know how to prove that the composition must behave like a direct-sum problem; second, we do not know how to prove that the complexity of the latter direct-sum problem is indeed the sum of the individual complexities.

In this talk, we will describe a new work that tackles the second obstacle. We will consider a notion of "strong composition" that is forced to behave like a direct-sum problem, and see that a variant of the KRW conjecture holds for this notion. This result demonstrates that the first obstacle above is the crucial barrier toward resolving the KRW conjecture. Along the way, we will discuss some general techniques that might be of independent interest.


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +45 28 78 38 11 / +46 70 742 21 98
https://jakobnordstrom.se