Subscribe to RSS FeedCS Events
Computer Science Department ColloquiumIdentifying Hardness of Covering and Coloring in Clustering and Steiner Tree |
|
||
Tuesday, December 05, 2023, 10:30am - 12:00pm |
|||
Speaker: Karthik C.S.
Bio
Karthik C. S. is an Assistant Professor in the Department of Computer Science at Rutgers University supported by a Simons Foundation Junior Faculty Fellowship and a grant from the National Science Foundation. He received his Ph.D. in 2019 from Weizmann Institute of Science where he was advised by Irit Dinur and his M.S. in 2014 from École Normale Supérieure de Lyon. He has held postdoctoral appointments at Tel Aviv University (hosted by Amir Shpilka) and New York University (hosted by Subhash Khot). He is broadly interested in complexity theory and discrete geometry with an emphasis on hardness of approximation, fine-grained complexity, and parameterized complexity.
Location : CoRE 301
:
Event Type: Computer Science Department Colloquium
Abstract: In this talk, I will discuss my recent efforts in revitalizing the subarea of inapproximability of geometric optimization problems, which lies at the confluence of hardness of approximation and geometric optimization, with the main aim of determining the boundaries of efficient approximation. My work is motivated by a lack of explanations as to why algorithmics are unable to exploit the structure of L_p-metrics, and in particular the Euclidean metric, to design efficient algorithms with better approximation guarantees compared to arbitrary metric spaces. I will focus on inapproximability results of clustering objectives and Steiner tree computation. A recurring technical motif in these results are graph embedding to L_p-metrics of hard instances of set cover and graph coloring problems.
:
Contact Professor Ulrich Kremer
Join Zoom Meeting
https://rutgers.zoom.us/j/2014444359?pwd=WW9ybFNCNVFrUWlycHowSHdNZjhzUT09
Meeting ID: 201 444 4359
Password: 550978
