Raghunath Tewari

Associate Professor
Computer Science and Engineering
Indian Institute of Technology, Kanpur

Office:
Room 514, Rajeev Motwani Building
Department of Computer Science and Engineering
Indian Institute of Technology, Kanpur
Kanpur - 208 016, UP, India.

+91 (512) 259 7174
rtewari at cse dot iitk dot ac dot in

Education

Employment

Publications

Journal

  1. On the Power of Unambiguity in Logspace (with A. Pavan and N. V. Vinodchandran). Computational Complexity, 21(4), pages 643-670, December 2012.
  2. ReachFewL = ReachUL (with Brady Garvin, Derrick Stolee and N. V. Vinodchandran). Computational Complexity, November 2012.
  3. Green's Theorem and Isolation in Planar Graphs (with N. V. Vinodchandran). Information and Computation, 215, pages 1-7, June 2012.
  4. Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs (with Samir Datta, Raghav Kulkarni and N. V. Vinodchandran). Journal of Computer and System Sciences, 78(3), pages 765-779, May 2012.
  5. Directed Planar Reachability is in Unambiguous Logspace (with Chris Bourke and N. V. Vinodchandran). ACM Transactions on Computation Theory, 1(1), pages 1-17, 2009.

Conference

  1. Dynamic Meta-Theorems for Distance and Matching (with Samir Datta, Chetan Gupta, Rahul Jain, Anish Mukherjee, Vimal Raj Sharma) ICALP 2022.
  2. Reachability and Matching in Single Crossing Minor Free Graphs (with Samir Datta, Chetan Gupta, Rahul Jain, Anish Mukherjee, Vimal Raj Sharma) FSTTCS 2021.
  3. Time Space Optimal Algorithm for Computing Separators in Bounded Genus Graphs (with Chetan Gupta, Rahul Jain) FSTTCS 2021.
  4. Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs (with Chetan Gupta, Vimal Raj Sharma) MFCS 2020.
  5. Randomized and Symmetric Catalytic Computation (with Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma) CSR 2020.
  6. Reachability in High Treewidth Graphs (with Rahul Jain) ISAAC 2019.
  7. Unambiguous Catalytic Computation (with Chetan Gupta, Rahul Jain, Vimal Raj Sharma) FSTTCS 2019.
  8. An $O(n^{1/4 +\epsilon})$ Space and Polynomial Algorithm for Grid Graph Reachability (with Rahul Jain) FSTTCS 2019.
  9. Reachability in O(log n) Genus Graphs is in Unambiguous Logspace (with Chetan Gupta, Vimal Raj Sharma) STACS 2019.
  10. Trading Determinism for Time in Space Bounded Computations (with Vivek Anand T Kallampally) MFCS 2016.
  11. Derandomizing Isolation Lemma for K_{3,3}-free and K_5-free Bipartite Graphs (with Rahul Arora, Ashu Gupta, Rohit Gurjar) STACS 2016.
  12. An O(n^e) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs (with Diptarka Chakraborty) ISAAC 2015.
  13. Simultaneous Time-Space Upper Bounds for Red-Blue Path Problem in Planar DAGs (with Diptarka Chakraborty) WALCOM 2015.
  14. New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs (with Diptarka Chakraborty, A. Pavan, N. V. Vinodchandran and Lin Yang) FSTTCS 2014.
  15. Improved bounds on Bipartite Matching on surfaces (with Samir Datta, Arjun Gopalan and Raghav Kulkarni) STACS 2012.
  16. ReachFewL = ReachUL (with Brady Garvin, Derrick Stolee and N. V. Vinodchandran) COCOON 2011.
  17. Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs (with Samir Datta, Raghav Kulkarni and N. V. Vinodchandran) STACS 2011.
  18. Optimal Segment Size for Fixed-sized Segment Protection in Wavelength-routed Optical Networks (with Byrav Ramamurthy) ANTS 2009.
  19. Directed Planar Reachability is in Unambiguous Logspace (with Chris Bourke and N. V. Vinodchandran) CCC 2007

Technical Reports

  1. Unambiguous Logarithmic Space Bounded Computations. Doctoral Dissertation, University of Nebraska - Lincoln, March 2011.
  2. On the Space Complexity of Directed Graph Reachability. Master's Thesis, University of Nebraska - Lincoln, May 2007.

Honors and Awards

Selected Presentations

Professional Experience

Teaching

Currrent teaching

Past teaching