Saket Saurabh
Professor
Theoretical Computer Science
2254 3213
saket @ imsc . res . in
213 New Building
Research Interests:
- Parameterized Complexity
- Exact Exponential Algorithms
- Graph Algorithms and Graph Theory
- Algorithmic Game Theory
Education:
- PhD in TCS from IMSc (graduated december 2008).
Career History:
- September 2006 to May 2007 -- Research Assistant at University of Bergen
- September 2007 to Sep 2009 -- Post Doctoral Fellow at University of Bergen
- October 2009 -- Present -- Faculty at IMSc
- January 2013 -- Present -- Adjunct Faculty at University of Bergen
Courses Taught:
- Parameterized Complexity
- Exact Exponential Algorithms
- Kernelization
- Advance Graph Algorithms
- Graph Theory
- Algorithmic Game Theory
- Theoretical Foundations of Machine Learning
- Randomized Algorithms
- Algorithms for Big-Data
Selected publications:
-
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh:
Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms. J. ACM 63(4): 29:1-29:60 (2016) -
Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, Dimitrios M. Thilikos:
(Meta) Kernelization. J. ACM 63(5): 44:1-44:69 (2016) -
Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth.SIAM J. Comput. 46(1): 161-189 (2017) -
Pinar Heggernes, Dieter Kratsch, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh:
Fixed-parameter algorithms for Cochromatic Number and Disjoint Rectangle Stabbing via iterative localization. Inf. Comput. 231: 109-116 (2013) -
Michael Dom, Daniel Lokshtanov, Saket Saurabh:
Kernelization Lower Bounds Through Colors and IDs. ACM Trans. Algorithms 11(2): 13:1-13:20 (2014) -
Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh:
Faster Parameterized Algorithms Using Linear Programming. ACM Trans. Algorithms 11(2): 15:1-15:31 (2014) -
Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh:
Intractability of Clique-Width Parameterizations. SIAM J. Comput. 39(5): 1941-1956 (2010) -
Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, Saket Saurabh:
Exact algorithms via monotone local search. STOC 2016: 764-774 -
Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh:
Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width. SIAM J. Comput. 43(5): 1541-1563 (2014) -
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Minimum bisection is fixed parameter tractable. STOC 2014: 323-332 -
Daniel Lokshtanov, Dániel Marx, Saket Saurabh:
Known Algorithms on Graphs on Bounded Treewidth are Probably Optimal. SODA 2011: 777-789 -
Daniel Lokshtanov, Dániel Marx, Saket Saurabh:
Slightly Superexponential Parameterized Problems. SODA 2011: 760-776 -
Noga Alon, Daniel Lokshtanov, Saket Saurabh:
Fast FAST. ICALP (1) 2009: 49-58 -
Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, Saket Saurabh:
Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms. FOCS 2012: 470-479 -
Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Saket Saurabh:
Deterministic Truncation of Linear Matroids. ICALP (1) 2015: 922-934 -
Fedor V. Fomin, Daniel Lokshtanov, Michal Pilipczuk, Saket Saurabh, Marcin Wrochna:
Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. SODA 2017: 1419-1432 -
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh:
Representative Sets of Product Families. ESA 2014: 443-454