Information theoretic approach to Boolean formula complexity.

Abstract: We will discuss the information-theoretic approach to proving lower bounds on the formula complexity of Boolean functions. In the late 80s, Karchmer and Wigderson discovered that Boolean formulas could be characterized using the language of communication complexity. This observation allowed us to apply communication complexity methods to prove lower and upper bounds on the Boolean formula complexity. In particular, we can use information-theoretic methods from communication complexity to prove formula complexity lower bounds. This talk is a brief introduction to these techniques, as well as to some applications.

Computer scienceMathematics

Audience: researchers in the discipline

Seminar on Algorithmic Aspects of Information Theory

Series comments: This online seminar is a follow up of the Dagstuhl Seminar 22301, www.dagstuhl.de/en/program/calendar/semhp/?semnr=22301.