BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1720
DTSTAMP:20260514T110600Z
SUMMARY:The Power of the Score Sequence of a Tournament
DESCRIPTION:Speaker: Prantar Ghosh (Tennessee Tech University)\n\nAbstract:
  \nA tournament is a directed graph where each pair of vertices shares exa
 ctly one directed edge. It might model a round-robin tournament where ever
 y game has a winner and a loser (no draws). The score sequence of a tourna
 ment is then given by its sequence of vertex indegrees\, i.e.\, the "score
 s" of the players. Over the years\, researchers have shown that the score 
 sequence suffices to solve multiple fundamental problems on tournaments\, 
 such as acyclicity testing\, topological sorting\, optimal linear arrangem
 ent\, and cutwidth. In this talk\, I shall first show a surprising power o
 f the sequence: it completely determines reachability between two nodes\, 
 strong connectivity\, and in general\, the decomposition of a tournament i
 nto strongly connected components (SCC). This makes one wonder: can we cha
 racterise the class of problems determined by the score sequence of a tour
 nament? The talk will answer this question in the affirmative to show tha
 t the class contains precisely all problems whose answers are invariant un
 der cycle reversals. The said characterization is a special case of a muc
 h more general result: for any arbitrary digraph\, the knowledge of its s
 keleton (underlying undirected graph) and the vertex indegrees completely 
 determines its properties that are invariant under cycle reversal. As a by
 product of these results\, one can obtain optimal algorithms (up to a loga
 rithmic factor) for a variety of connectivity-based\, cut-based\, and vert
 ex-ordering problems on tournaments and almost-tournaments in the streamin
 g\, the two-player communication\, and the cut-query models of computation
 . \n \nThis is based on a joint work with Sahil Kuchlous (ESA'24) and a 
 work under submission with Sahil\, Sagnik Mukhopadhyay\, and Shravan Mehra
 .\n
URL:https://www.tcs.tifr.res.in/web/events/1720
DTSTART;TZID=Asia/Kolkata:20260521T160000
DTEND;TZID=Asia/Kolkata:20260521T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR