BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1130
DTSTAMP:20230914T125951Z
SUMMARY:Communication Complexity and Quantum Optimization Lower Bounds via
Query Complexity
DESCRIPTION:Speaker: Suhail Sherif\n\nAbstract: \nThe query model is a simp
le model of computation that has led to many deep results. One such class
of results relates computational complexity measures such as query complex
ity/communication complexity to algebraic measures such as degree/rank. Th
e first part of this thesis deals with such relations. The results of this
part of the thesis are given below.\n\n1. In the context of randomized co
mmunication complexity and randomized parity decision tree (RPDT) complexi
ty\, we prove that the relevant computational measures and algebraic measu
res are not closely related. This disproves multiple long-standing conject
ures in communication complexity.\n\n2. We try to quantitatively strengthe
n the above result. We do manage to do so in the context of RPDTs\, but th
ere are challenges in translating this strengthening to the context of ran
domized communication complexity. We pose a fundamental conjecture that wo
uld imply that the strengthening holds in the communication world as well.
\n\nIn the second part of the thesis\, we look at convex optimization. The
goal is to optimize a convex function in a bounded region when you can on
ly learn about the function through function value and gradient queries. W
e want to use as few queries as possible. Projected gradient descent (PGD)
is a well-known algorithm that optimally solves this task when the dimens
ion of the function's domain is large. In the second part of the thesis we
add to the optimality results of PGD.\n\n3. (a) In the case of quantum al
gorithms it was open whether there is a quadratic speedup over PGD when th
e dimension is large. We show that this is not so\, that PGD is optimal up
to constant factors.\n(b) In the case of randomized algorithms we show a
simple argument bettering the range of dimensions where PGD is known to be
optimal up to constant factors.\n\nWe end with a few open problems.\n\nJo
in Zoom Meeting\nhttps://zoom.us/j/93580606744?pwd=L1pCek1pSy91a0JOOXpXdjI
0Z2EyQT09\nMeeting ID: 935 8060 6744\nPasscode: 335095\n
URL:https://www.tcs.tifr.res.in/web/events/1130
DTSTART;TZID=Asia/Kolkata:20210517T170000
DTEND;TZID=Asia/Kolkata:20210517T180000
END:VEVENT
END:VCALENDAR