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