BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Alexander V. Smal (Technion\, Israel\; PDMI\, Russia)
DTSTART:20230621T150000Z
DTEND:20230621T161500Z
DTSTAMP:20260423T035958Z
UID:AAIT/19
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/AAIT/19/">In
 formation theoretic approach to Boolean formula complexity.</a>\nby Alexan
 der V. Smal (Technion\, Israel\; PDMI\, Russia) as part of Seminar on Algo
 rithmic Aspects of Information Theory\n\n\nAbstract\nWe will discuss the i
 nformation-theoretic approach to proving lower bounds on the formula compl
 exity of Boolean functions. In the late 80s\, Karchmer and Wigderson disco
 vered that Boolean formulas could be characterized using the language of c
 ommunication complexity. This observation allowed us to apply communicatio
 n complexity methods to prove lower and upper bounds on the Boolean formul
 a complexity. In particular\, we can use information-theoretic methods fro
 m communication complexity to prove formula complexity lower bounds. This 
 talk is a brief introduction to these techniques\, as well as to some appl
 ications.\n
LOCATION:https://researchseminars.org/talk/AAIT/19/
END:VEVENT
END:VCALENDAR