BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1199
DTSTAMP:20230914T125954Z
SUMMARY:Improved Quantum Query Upper Bounds Based on Classical Decision Tre
 es
DESCRIPTION:Speaker: Nikhil S. Mande (CWI\, Amsterdam.)\n\nAbstract: \nIn t
 he first part of this talk we will discuss the notion of rank of decision 
 trees\, which is essentially the largest depth of a complete subtree embed
 ded in the initial tree. We observe the equivalence of rank and "guessing 
 complexity\," a measure of decision trees used by Lin and Lin [Theory of C
 omputing'16] and Beigi and Taghavi [Quantum'20] to give upper bounds on qu
 antum query complexity of functions based on classical query algorithms fo
 r them.\n\nIn the second part of the talk we will first note that the best
  speed-up obtainable using the approach of Beigi and Taghavi is captured b
 y a polynomial optimization program on assignments of real weights to edge
 s of the underlying classical decision tree. We then give a recursive expr
 ession for the optimal solution to this program and bound the optimum from
  above in terms of natural measures of the decision tree.\n\nBased on join
 t work with Arjan Cornelissen and Subhasree Patro (https://arxiv.org/abs/2
 203.02968).\n
URL:https://www.tcs.tifr.res.in/web/events/1199
DTSTART;TZID=Asia/Kolkata:20220426T160000
DTEND;TZID=Asia/Kolkata:20220426T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR