BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/230
DTSTAMP:20230914T125915Z
SUMMARY:Depth-Independent Lower Bounds on the Communication Complexity of R
 ead-Once Boolean Formulas
DESCRIPTION:Speaker: Sagnik  Mukhopadhyay\n\nAbstract: \nWe show lower boun
 ds of $\\Omega(\\sqrt{n})$ on the randomized communication complexity\, re
 spectively\, of all $n$-variable read-once Boolean formulas. Our results c
 omplement the recent lower bound of $\\Omega(n/8^d)$ by Leonardos and Saks
  and $\\Omega(n/2^{\\Omega(d\\log d)})$ by Jayram\, Kopparty and Raghavend
 ra for randomized communication complexity of read-once Boolean formulas w
 ith depth $d$. We obtain our result by "embedding" either the Disjointness
  problem or its complement in any given read-once Boolean formula.\n\nIt i
 s a small paper. I will try to present some additional results proofs of w
 hich is not included in this paper. I will need 40 mins to complete the pr
 esentation.\n\n(Author: Rahul Jain\, Hartmut Klauck\, Shengyu Zhang)\n
URL:https://www.tcs.tifr.res.in/web/events/230
DTSTART;TZID=Asia/Kolkata:20111210T110000
DTEND;TZID=Asia/Kolkata:20111210T120000
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR