Events
FDS Postdoctoral Applicants
Parameterized Algorithms through the Lens of (Hyper)-Graph Decompositions
 |
Speaker: Vaishali Surianarayanan (UCSB) University of California, Santa Barbara Thursday, December 19, 2024 1:00PM - 2:00PM and via Webcast: https://yale.zoom.us/j/94654567520 |
“Parameterized Algorithms through the Lens of (Hyper)-Graph Decompositions“
Abstract: Optimization problems on graphs and hypergraphs—generalizations of graphs—are foundational in many practical applications. However, a huge portion of these problems are NP-hard. This means that, unless P=NP, no algorithm running in time polynomial in the size of the input instance can solve every instance optimally. Despite this, real-world instances often exhibit a lot of structure, enabling tailored solutions. Parameterized algorithms solve such structurally simple instances optimally using time polynomial in the size of the instance. These algorithms take as input an additional parameter, which represents some relevant secondary measurement of the input instance, such as maximum degree or solution size, and run in polynomial time in the input size when the parameter is small.
Graph decompositions also play a pivotal role in algorithm design, providing a way to break down graphs into manageable components. Simple decompositions, like separating graphs into connected components or directed graphs into strongly connected components, are fundamental in many graph algorithms. More advanced decompositions, such as tree decompositions, are central to modern graph theory and parameterized algorithms.
In this talk, I will provide an overview of my research on parameterized algorithms for (hyper)-graph optimization problems through the lens of (hyper)-graph decompositions. My work focuses both on using such decompositions to design algorithms for various problems and on developing algorithms to compute the decompositions themselves. I will begin by introducing the field of parameterized algorithms, give an overview of my contributions, and then highlight one of my recent works on computing hypergraph tree decompositions of bounded width. This work provides results in both theory and practice and has applications in database query optimization. Finally, I will conclude with my research vision for designing parameterized algorithms that are both theoretically sound and scalable in practice, for problems arising in data mining and database query optimization.
Bio: Vaishali Surianarayanan is a senior PhD candidate at UC Santa Barbara, advised by Daniel Lokshtanov. Her research focuses on the parameterization and approximability of graph and hypergraph optimization problems. Her work uncovers structural insights in problem instances and leverages small parameters to design theoretically sound algorithms that enable practically scalable solutions. Her research has been featured in top AI and CS theory venues such as FOCS, SODA, ESA, and IJCAI. Beyond research, she is committed to teaching, mentoring, and advocating for diversity, equity, and inclusion in CS. Her awards include the Best Outgoing Student and Academic Excellence awards during her undergraduate studies, as well as the Outstanding Teaching Assistant Award and the Neal Fenzi Resonant Fellowship for her contributions to UC Santa Barbara’s CS department. Before pursuing her PhD, Vaishali earned an integrated master’s degree from PSG College of Technology in India.
Add To: Google Calendar | Outlook | iCal File
Submit an Event
Interested in creating your own event, or have an event to share? Please fill the form if you’d like to send us an event you’d like to have added to the calendar.