Saket Saurabh

Saket Saurabh

Professor
Theoretical Computer Science
2254 3213
saket @ imsc . res . in
213 New Building
Research Interests: 
  1. Parameterized Complexity 
  2. Exact Exponential Algorithms
  3. Graph Algorithms and Graph Theory
  4. Algorithmic Game Theory
Education: 
  1. PhD in TCS from IMSc (graduated december 2008).
Career History: 
  1. September 2006 to May 2007 -- Research Assistant at University of Bergen
  2. September 2007 to Sep 2009 -- Post Doctoral Fellow at University of Bergen
  3. October 2009  -- Present -- Faculty at IMSc 
  4. January 2013 -- Present  -- Adjunct Faculty at University of Bergen 
Courses Taught: 
  1. Parameterized Complexity
  2. Exact Exponential Algorithms
  3. Kernelization
  4. Advance Graph Algorithms
  5. Graph Theory
  6. Algorithmic Game Theory
Selected publications: 

 

  1. , Saket Saurabh:
    Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms. J. ACM 63(4): 29:1-29:60 (2016)
  2. , Saket Saurabh, :
    (Meta) Kernelization. J. ACM 63(5): 44:1-44:69 (2016)
  3. , Saket Saurabh:
    Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth.SIAM J. Comput. 46(1): 161-189 (2017)
  4. , Saket Saurabh:
    Fixed-parameter algorithms for Cochromatic Number and Disjoint Rectangle Stabbing via iterative localization. Inf. Comput. 231: 109-116 (2013)
  5.  , Saket Saurabh:
    Kernelization Lower Bounds Through Colors and IDs. ACM Trans. Algorithms 11(2): 13:1-13:20 (2014)
  6.  , Saket Saurabh:
    Faster Parameterized Algorithms Using Linear Programming. ACM Trans. Algorithms 11(2): 15:1-15:31 (2014)
  7. F, Saket Saurabh:
    Intractability of Clique-Width Parameterizations. SIAM J. Comput. 39(5): 1941-1956 (2010)
  8. , Saket Saurabh:
    Exact algorithms via monotone local search. STOC 2016: 764-774
  9. , Saket Saurabh:
    Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width. SIAM J. Comput. 43(5): 1541-1563 (2014)
  10. , Saket Saurabh:
    Minimum bisection is fixed parameter tractable. STOC 2014: 323-332
  11. , Saket Saurabh:
    Known Algorithms on Graphs on Bounded Treewidth are Probably Optimal. SODA 2011: 777-789
  12.  , Saket Saurabh:
    Slightly Superexponential Parameterized Problems. SODA 2011: 760-776
  13. , Saket Saurabh:
    Fast FAST. ICALP (1) 2009: 49-58
  14. , Saket Saurabh:
    Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms. FOCS 2012: 470-479
  15. , Saket Saurabh:
    Deterministic Truncation of Linear Matroids. ICALP (1) 2015: 922-934
  16. , Saket Saurabh, :
    Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. SODA 2017: 1419-1432
  17. , Saket Saurabh:
    Representative Sets of Product Families. ESA 2014: 443-454