BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/998
DTSTAMP:20230914T125946Z
SUMMARY:Sign-Rank Can Increase Under Intersection
DESCRIPTION:Speaker: Nikhil Mande (Georgetown University\nWashington\, USA)
 \n\nAbstract: \nAbstract: The communication class UPP^{cc} is a communicat
 ion analog of the Turing Machine complexity class PP. It is characterized 
 by a matrix-analytic complexity measure called sign-rank (also called dime
 nsion complexity)\, and is essentially the most powerful communication cla
 ss against which we know how to prove lower bounds. For a communication pr
 oblem f\, let "f AND f" denote the function that evaluates f on two disjo
 int inputs and outputs the AND of the results. We exhibit a communication 
 problem f with UPP^{cc}(f) = O(log n)\, and UPP^{cc}(f AND f) = Theta(log^
 2 n). This is the first result showing that UPP communication complexity c
 an increase by more than a constant factor under intersection. We view thi
 s as a first step toward showing that UPP^{cc}\, the class of problems wit
 h polylogarithmic-cost UPP communication protocols\, is not closed under i
 ntersection.  Based on joint work (ICALP'19) with Mark Bun (Boston Univer
 sity) and Justin Thaler (Georgetown University).\n
URL:https://www.tcs.tifr.res.in/web/events/998
DTSTART;TZID=Asia/Kolkata:20190924T161500
DTEND;TZID=Asia/Kolkata:20190924T171500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR