Roshan Raj

I am a postdoctoral fellow at CSE department, The Ohio State University, working with Zeyu Guo. Previously, I was a posdoctoral fellow at School of Technology and Computer Science, TIFR Mumbai, where I worked with Mrinal Kumar. I completed my PhD at CSE department, IIT Bombay where I worked under the supervision of Rohit Gurjar. I obtained my bachelor's degree in Computer Science and Engineering from IIT Varanasi (BHU).

I am currently working in the field of Theoretical Computer Science. My research interests lie in Algebraic Computational Complexity, Matroids and Parallel Algorithms.

Email: raj[dot]144[at]osu[dot]edu

Publications

Bipartite Matching is in NC
with Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar and Thomas Thierauf.
To be submitted. [eccc]
Explicit Rank Extractors and Subspace Designs via Function Fields, with Applications to Strong Blocking Sets
with Zeyu Guo, Chong Shangguan and Zihan Zhang.
To appear at IEEE Symposium on Foundations of Computer Science (FOCS) 2026. [ arxiv]
Learning Read-Once Determinants and the Principal Minor Assignment Problem
with Abhiram Aravind, Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar and Chandan Saha.
To appear at ACM Symposium on Theory of Computing (STOC) 2026. [ pdf ]
Matroids are Equitable
with Hannaneh Akrami and László Végh.
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2026. [ arxiv ]
Characterizing and Testing Principal Minor Equivalence of Matrices
with Abhranil Chatterjee, Sumanta Ghosh and Rohit Gurjar.
ACM Symposium on Theory of Computing (STOC) 2025. [ arxiv ]
Fractional Linear Matroid Matching is in quasi-NC
with Rohit Gurjar and Taihei Oki
European Symposium on Algorithms (ESA) 2024. [ arxiv ]
Border Complexity of Symbolic Determinant under Rank One Restriction
with Abhranil Chatterjee, Sumanta Ghosh and Rohit Gurjar
Computational Complexity Conference (CCC) 2023. [ pdf ]
A Deterministic Parallel Reduction from Weighted Matroid Intersection Search to Decision
with Sumanta Ghosh and Rohit Gurjar
Algorithmica 2024, ACM-SIAM Symposium on Discrete Algorithms (SODA) 2022. [ pdf ]

Professional Activities

Teaching Assistant at IIT Bombay for courses Algorithms and Complexity, Topics in Computational Complexity, Applied Algorithms, Design and Analysis of Algorithms and Extremal Combinatorics.
Teaching Assistant for NPTEL course Randomized Methods in Complexity.