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

• Ph.D. 2011, University of Nebraska - Lincoln, USA.
• M.S. 2007, University of Nebraska - Lincoln, USA.
• B.Sc. 2005, Chennai Mathematical Institute, India.

Employment

• Dec 2019 -- present, Associate Professor, Indian Institute of Technology, Kanpur.
• Dec 2011 -- Dec 2019, Assistant Professor, Indian Institute of Technology, Kanpur.
• Jul 2011 -- Dec 2011, Assistant Professor, Indian Institute of Technology, Kharagpur.
• Jun 2011 -- Jul 2011, Lecturer, University of Nebraska - Lincoln.
• Jun 2009 -- May 2011, Research Assistant, University of Nebraska - Lincoln.
• Aug 2005 -- May 2009, Teaching Assistant, University of Nebraska - Lincoln.

Publications

Journal

1. Space efficient algorithm for solving reachability using tree decomposition and separators (with Rahul Jain) Theoretical Computer Science, 982, 114251, 2024.
2. On Solving Reachability in Grid Digraphs using a Pseudoseparator (with Rahul Jain) Theory of Computing, 19, 1-23, 2023.
3. An $O(n^{\epsilon})$ Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs (with Diptarka Chakraborty) ACM Transactions on Computation Theory, 9(4), 19:1-19:11, 2018.
4. ReachFewL = ReachUL (with Brady Garvin, Derrick Stolee and N. V. Vinodchandran). Computational Complexity, 23(1), pages 85-98, 2014.
5. On the Power of Unambiguity in Logspace (with A. Pavan and N. V. Vinodchandran). Computational Complexity, 21(4), pages 643-670, December 2012.
6. Green's Theorem and Isolation in Planar Graphs (with N. V. Vinodchandran). Information and Computation, 215, pages 1-7, June 2012.
7. 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.
8. 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. Inductive Tracing and the Complexity of finding Hamiltonian Path in DAGs (with Ronak Bhadra) FCT 2025.
2. Dynamic Meta-Theorems for Distance and Matching (with Samir Datta, Chetan Gupta, Rahul Jain, Anish Mukherjee, Vimal Raj Sharma) ICALP 2022.
3. Reachability and Matching in Single Crossing Minor Free Graphs (with Samir Datta, Chetan Gupta, Rahul Jain, Anish Mukherjee, Vimal Raj Sharma) FSTTCS 2021.
4. Time Space Optimal Algorithm for Computing Separators in Bounded Genus Graphs (with Chetan Gupta, Rahul Jain) FSTTCS 2021.
5. Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs (with Chetan Gupta, Vimal Raj Sharma) MFCS 2020.
6. Randomized and Symmetric Catalytic Computation (with Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma) CSR 2020.
7. Reachability in High Treewidth Graphs (with Rahul Jain) ISAAC 2019.
8. Unambiguous Catalytic Computation (with Chetan Gupta, Rahul Jain, Vimal Raj Sharma) FSTTCS 2019.
9. An $O(n^{1/4 +\epsilon})$ Space and Polynomial Algorithm for Grid Graph Reachability (with Rahul Jain) FSTTCS 2019.
10. Reachability in O(log n) Genus Graphs is in Unambiguous Logspace (with Chetan Gupta, Vimal Raj Sharma) STACS 2019.
11. Trading Determinism for Time in Space Bounded Computations (with Vivek Anand T Kallampally) MFCS 2016.
12. Derandomizing Isolation Lemma for K_{3,3}-free and K_5-free Bipartite Graphs (with Rahul Arora, Ashu Gupta, Rohit Gurjar) STACS 2016.
13. An O(n^e) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs (with Diptarka Chakraborty) ISAAC 2015.
14. Simultaneous Time-Space Upper Bounds for Red-Blue Path Problem in Planar DAGs (with Diptarka Chakraborty) WALCOM 2015.
15. 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.
16. Improved bounds on Bipartite Matching on surfaces (with Samir Datta, Arjun Gopalan and Raghav Kulkarni) STACS 2012.
17. ReachFewL = ReachUL (with Brady Garvin, Derrick Stolee and N. V. Vinodchandran) COCOON 2011.
18. Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs (with Samir Datta, Raghav Kulkarni and N. V. Vinodchandran) STACS 2011.
19. Optimal Segment Size for Fixed-sized Segment Protection in Wavelength-routed Optical Networks (with Byrav Ramamurthy) ANTS 2009.
20. 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

• INSPIRE Faculty Award by the Department of Science and Technology, India
• Outstanding Ph.D. Student Award, Dept. of Computer Science and Engineering at University of Nebraska - Lincoln.
• Outstanding Master's Award, Dept. of Computer Science and Engineering at University of Nebraska - Lincoln.

Selected Presentations

• How powerful is logspace unambiguity? At the colloquium at Chennai Mathematical Institute, November 2011.
• Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs. At the 28th International Symposium on Theoretical Aspects of Computer Science, Dortmund, Germany, March 2011.
• Green?s Theorem and its Application to the Isolation Problem in Planar Graphs. At the Computer Science Departmental Colloquium, University of Massachusetts-Amherst, September 2010.
• Space Complexity of Directed Graph Reachability. At the Discrete Math Seminar in the Mathematics Department at UNL, September 2007.
• Directed Planar Reachability is in Unambiguous Logspace. At the 22nd Annual IEEE Conference on Computational Complexity, San Diego, USA, June 2007.

Professional Experience

• Reviewed papers for STOC, FOCS, CCC, STACS, ICALP, ISAAC, FSTTCS

Teaching

Currrent teaching

• Computational Complexity Theory

Past teaching

• Fundamentals of Computing
• Computational Complexity Theory
• Theory of Computation
• Small Space Bounded Computations
• Data Structures and Algorithms
• C Programming
• Unix Programming
• MATLAB Programming
• Advanced Complexity Theory (co-taught with Vinodchandran Variyam)