BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1050
DTSTAMP:20230914T125948Z
SUMMARY:Quantum versus Randomized Communication Complexity\, with Efficient
Players
DESCRIPTION:Speaker: Uma Girish (Princeton University\nUnited States)\n\nAb
stract: \nAbstract: We study a new type of separation between quantum a
nd classical communication complexity\, a separation which is obtained usi
ng quantum protocols where all parties are efficient\, in the sense that t
hey can be implemented by small quantum circuits with oracle access to the
ir inputs. More precisely\, we give an explicit partial Boolean function t
hat can be computed in the quantum-simultaneous-with-entanglement model of
communication\, however\, every interactive randomized protocol is of exp
onentially larger cost. Furthermore\, all the parties in the quantum proto
col can be implemented by quantum circuits of small size with blackbox acc
ess to the inputs. Our result qualitatively matches the strongest known se
paration between quantum and classical communication complexity and is obt
ained using a quantum protocol where all parties are efficient. Our proof
technique is new in the context of communication complexity and is based o
n techniques from the recent oracle separation of BQP and PH.\nThis is a j
oint work with Ran Raz and Avishay Tal.\n
URL:https://www.tcs.tifr.res.in/web/events/1050
DTSTART;TZID=Asia/Kolkata:20200207T113000
DTEND;TZID=Asia/Kolkata:20200207T123000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR