BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1143
DTSTAMP:20230914T125952Z
SUMMARY:The Strahler Number of a Parity Game
DESCRIPTION:Speaker: Thejaswini Raghavan (University of Warwick)\n\nAbstrac
 t: \nThe Strahler number of a rooted tree is the largest height of a perfe
 ct binary tree that is its minor. The Strahler number of a parity game is 
 proposed to be defined as the smallest Strahler number of the tree of any 
 of its attractor decompositions. It is proved that parity games can be sol
 ved in quasi-linear space and in time that is polynomial in the number of 
 vertices n and linear in (d/2k)^k\, where d is the number of priorities an
 d k is the Strahler number. This complexity is quasi-polynomial because th
 e Strahler number is at most logarithmic in the number of vertices. The pr
 oof is based on a new construction of small Strahler-universal trees.\n\nI
 t is shown that the Strahler number of a parity game is a robust\, and hen
 ce arguably natural\, parameter: it coincides with its alternative version
  based on trees of progress measures and—remarkably—with the register 
 number defined by Lehtinen (2018). It follows that parity games can be sol
 ved in quasi-linear space and in time that is polynomial in the number of 
 vertices and linear in (d/2k)^k\, where k is the register number. This sig
 nificantly improves the running times and space achieved for parity games 
 of bounded register number by Lehtinen (2018) and by Parys(2020). The runn
 ing time of the algorithm based on small Strahler-universal trees yields a
  novel trade-off k.log(d/k) = O(log n) between the two natural parameters 
 that measure the structural complexity of a parity game\, which allows sol
 ving parity games in polynomial time. This includes as special cases the a
 symptotic settings of those parameters covered by the results of Calude\, 
 Jain\, Khoussainov\, Li\, and Stephan (2017)\, of Jurdzinski and Lazic (20
 17)\, and of Lehtinen (2018)\, and it significantly extends the range of s
 uch settings\, for example to d = 2^{O(\\sqrt{\\lg n})} and k = O(\\sqrt{\
 \lg n}).\n\nThis is joint work with Laure Daviaud and Marcin Jurdzinski.\n
 \nZoom link: https://zoom.us/j/93889521556?pwd=eEFJWVRtRHNpNlpZWmhNYTJGQTF
 6Zz09\n
URL:https://www.tcs.tifr.res.in/web/events/1143
DTSTART;TZID=Asia/Kolkata:20210723T171500
DTEND;TZID=Asia/Kolkata:20210723T181500
END:VEVENT
END:VCALENDAR