University of Cambridge > Talks.cam > Algorithms and Complexity Seminar > The Karchmer-Raz-Wigderson Conjecture

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

The Karchmer-Raz-Wigderson Conjecture

Download to your calendar using vCal

If you have a question about this talk, please contact Tom Gur .

Proving super-logarithmic lower bounds on the depth of circuits 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 complexity of their composition is about the sum of their individual depth complexities. While we cannot prove the conjecture yet, there has been some 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 directions for research on the KRW conjecture.

This talk is part of the Algorithms and Complexity Seminar series.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Cambridge University Women in Science Society Rainbow Interaction Seminars Please get in touch at compbiomphil@maths.cam.ac.uk for joining information

Other talks

Why people with schizophrenia die earlier? Mortality and accelerated ageing Title to follow External Seminar - Michael Raissig TBC Dinner Coming soon CONFERENCE: Chemical and material sciences enabled by AI and automation
 

Š 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity