BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:The Karchmer-Raz-Wigderson Conjecture - Or Meir (Sheffield)
DTSTART:20251104T140000Z
DTEND:20251104T150000Z
UID:TALK235222@talks.cam.ac.uk
CONTACT:Tom Gur
DESCRIPTION:Proving super-logarithmic lower bounds on the depth of circuit
 s is one of the main frontiers of circuit complexity. In 1991\, Karchmer\,
  Raz and Wigderson observed that we could resolve this question by proving
  the following conjecture: Given two boolean functions f\,g\, the depth co
 mplexity of their composition is about the sum of their individual depth c
 omplexities. While we cannot prove the conjecture yet\, there has been som
 e exciting progress toward such a proof\, some of it in the last few years
 . In this talk\, I will survey the known results and propose future direct
 ions for research on the KRW conjecture.
LOCATION:Computer Laboratory\, William Gates Building\, Room SS03
END:VEVENT
END:VCALENDAR