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