BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1754
DTSTAMP:20260902T045824Z
SUMMARY:Matching in general graphs is in catalytic logspace
DESCRIPTION:Speaker: Amit Kumar Sinhababu (Chennai Mathematical Institute)\
 n\nAbstract: \nThe study of space-bounded computation is a central theme i
 n complexity theory\, with a long line of work investigating the power and
  limitations of logarithmic-space algorithms. A recent direction in this a
 rea focuses on models that augment classical space bounds with auxiliary r
 esources\, such as catalytic space\, where a large workspace is available 
 but must be returned to its initial state at the end of the computation. T
 his model\, introduced by Buhrman\, Cleve\, Koucký\, Loff\, and Speelman 
 [STOC 2014]\, has led to surprising algorithmic developments and a refined
  understanding of the role of reversibility and space reuse in computation
 . One of the striking algorithmic results in this area is that bipartite m
 aximum matching can be computed in catalytic logspace (CL) [Aggarwala and 
 Mertz\, FOCS 25].\n We show that the size of a maximum matching in genera
 l graphs can be determined in CL. Our algorithm is based on a linear-algeb
 raic algorithm for maximum matching by Geelen [2000]. We then show that th
 is algorithm\, along with some new ideas\, can be used to find (in CL) a m
 aximum matching in general graphs."This is joint work with Samir Datta\, S
 rijan Chakraborty\, Aryan Kusre and Partha Mukhopadhyay."\nBio: Amit Sinha
 babu is an assistant professor in Chennai Mathematical Institute. He did P
 hD from IIT Kanpur under the supervision of Nitin Saxena and was a postdoc
 toral fellow at University of Aalen and Ulm mentored by Thomas Thierauf. A
 mit's research interests are broadly in algebraic techniques in complexity
  theory and algorithms.\n \n \n
URL:https://www.tcs.tifr.res.in/web/events/1754
DTSTART;TZID=Asia/Kolkata:20260908T160000
DTEND;TZID=Asia/Kolkata:20260908T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR