Theoretical Computer Science @ IIT Bombay

IIT Bombay has an active research programme in Theoretical Computer Science, spanning several areas including Algorithms, Combinatorial Optimization, Combinatorics, Complexity Theory, Cryptography and Graph Theory.

Theory Seminar and Reading Group

Click here to find out about the upcoming talks and browse through the past talks/events.


Faculty in the Theory Group

adsul Bharat Adsul
Formal methods in Concurrency, Logics and Games. Geometric Complexity Theory.
  • A generalization of the Łoś-Tarski preservation theorem. Ann. Pure Appl. Logic. 2016. With Abhisekh Sankaran and Supratik Chakraborty.
  • Incorporating Sharp Features in the General Solid Sweep Framework. Comput. Graph. Forum. 2016. With Jinesh Machchhar and Milind A. Sohoni.
  • Local and global analysis of parametric solid sweeps. Computer Aided Geometric Design. 2014. With Jinesh Machchhar and Milind A. Sohoni.
  • Rank-1 bimatrix games: a homeomorphism and a polynomial time algorithm. STOC 2011. With Jugal Garg, Ruta Mehta and Milind Sohoni
  • Complete and tractable local linear time temporal logics over traces. ICALP 2002. With Milind Sohoni.
DBLP    Google Scholar    Semantic Scholar
aad Ajit A Diwan
Graph theory and Combinatorics.
  • Four-Connected Triangulations of Planar Point Sets. Discrete & Computational Geometry. 2015. With Subir Kumar Ghosh and Bodhayan Roy.
  • The complexity of P4-decomposition of regular graphs and multigraphs. Discrete Mathematics & Theoretical Computer Science. 2015. With Justine E. Dion, David J. Mendell, Michael Plantholt and Shailesh K. Tipnis.
  • Balanced group-labeled graphs. Discrete Mathematics. 2012. With Manas Joglekar and Nisarg Shah.
  • Efficient inference with cardinality-based clique potentials. ICML 2007. With Rahul Gupta and Sunita Sarawagi.
  • Scheduling and caching in multi-query optimization. COMAD 2006. With S Sudarshan and Dilys Thomas.
DBLP    Google Scholar    Semantic Scholar
sujoy Sujoy Bhore
Discrete and Computational Geometry, Algorithms under Uncertainty, Graph Theory, Algorithmic Robotics
  • Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings. SODA 2024. With A. Filtser, C. Toth.
  • Euclidean Steiner Spanners: Light and Sparse. SIAM Journal of Discrete Math. 2022. With C. Tóth,
  • On Erdos-Szekeres-type Problems for k-Convex Point Sets, European Journal of Combinatorics, 2020. With M. Balko, L. Martínez-Sandoval, P. Valtr.
  • Extending Orthogonal Planar Graph Drawings Is Fixed-Parameter Tractable, SoCG 2023. With R. Ganian, L. Khazaliya, F. Montecchiani, M. Nöllenburg.
  • On the Upward Book Thickness Problem: Combinatorial and Complexity results. European Journal of Combinatorics 2022. With G. Lozzo, F. Montecchiani, M. Nöllenburg.
  • Planar Bichromatic Bottleneck Spanning Trees. Journal of Computational Geometry 2021. With K. Abu-Affash, P. Carmi, J. Mitchell.
  • Light Euclidean Steiner Spanners in the Plane. SoCG 2021. With C. Toth.
  • Online Spanners in Metric Spaces, SIAM Journal of Discrete Math. 2024, With Arnold Filtser, Hadi Khodabandeh, Csaba D. Tóth.
DBLP    Google Scholar    Semantic Scholar
rohit Rohit Gurjar
Algorithms and Complexity, specifically Derandomization, Parallel algorithms.
  • Bipartite Perfect Matching is in quasi-NC. STOC 2016. With Stephen Fenner, Thomas Thierauf.
  • Linear Matroid Intersection is in quasi-NC. STOC 2017. With Thomas Thierauf.
  • Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces. ICALP 2018. With Nisheeth K. Vishnoi, Thomas Thierauf.
  • Identity Testing for Constant-width, and Commutative, Read-once Oblivious ABPs. CCC 2016. With Arpita Korwar, Nitin Saxena.
DBLP    Google Scholar    Semantic Scholar
akash Akash Kumar
Property testing, Spectral graph theory, spectral algorithms, subgraph recovery.
  • Random walks and Forbidden minors I: An n^{1/2+o(1)}-Query one-sided tester for Minor Closed Properties on Bounded degree graphs. With C. Seshadhri, Andrew Stolman. FOCS 2018.
  • Random walks and Forbidden minors III: poly(d/ε)-time partition oracles for minor-free graph classes. With C. Seshadhri, Andrew Stolman. FOCS 2021.
  • The complexity of testing all properties of planar graphs, and the role of isomorphism. With Sabyasachi Basu, C. Seshadhri. SODA 2022.
  • Learning Hierarchical Cluster Structure of Graphs in Sublinear Time With Michael Kapralov, Silvio Lattanzi, Aida Mousavifar. SODA 2023.
D\ BLP    Google Scholar    Semantic Scholar
nutan Nutan Limaye (on leave)
Algorithms and Complexity Theory.
  • Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication. STOC 2014. With Hervé Fournier, Guillaume Malod, Srikanth Srinivasan.
  • Optimal Embedding of Functions for In-Network Computation: Complexity Analysis and Algorithms. IEEE/ACM Transactions on Networking, 2016. With Pooja Vyavahare, D. Manjunath.
  • The shifted partial derivative complexity of Elementary Symmetric Polynomials. MFCS 2015. With Hervé Fournier, Meena Mahajan, Srikanth Srinivasan.
  • Space-Efficient Approximations for Subset Sum. TOCT 2016. With Anna Gál, Jing-Tang Jang, Meena Mahajan, Karteek Sreenivasaiah.
  • Planar Graph Isomorphism is in Log-Space. CCC 2009. With Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner.
DBLP    Google Scholar    Semantic Scholar
Manoj Prabhakaran mp
Theoretical and Applied Cryptography. Other topics including information theory, coding theory and complexity theory.
  • Rényi Information Complexity and an Information Theoretic Characterization of the Partition Bound. ICALP 2016. With Vinod Prabhakaran.
  • Towards a Unified Theory of Cryptographic Agents. EUROCRYPT 2015. With Shashank Agrawal and Shweta Agrawal.
  • Circuits Resilient to Additive Attacks with Applications to Secure Computation. STOC 2014. With Daniel Genkin, Yuval Ishai, Amit Sahai and Eran Tromer.
  • On the Power of Public-key Encryption in Secure Computation. TCC 2014. With Mohammad Mahmoody and Hemanta Maji.
  • Dynamic Searchable Encryption via Blind Storage. IEEE S&P (Oakland) 2014. With Muhammad Naveed and Carl Gunter.
  • On Fair Exchange, Fair Coins and Fair Sampling. CRYPTO 2013. With Shashank Agrawal.
DBLP    Google Scholar    Semantic Scholar
ranade Abhiram Ranade
Algorithms and Combinatorial Optimization.
  • Fragmented coloring of proper interval and split graphs. Discrete Applied Mathematics. 2015. With Ajit Diwan and Soumitra Pal.
  • Scheduling light-trails on WDM rings. J. Parallel Distrib. Comput. 2012. With Soumitra Pal.
  • A variation on SVD based image compression. Image & Vision Computing. 2007. With Srikanth Mahabalarao and Satyen Kale.
  • An Improved Maximum Likelihood Formulation for Genome Assembly. In ICCABS 2011. With Aditya Varma and Srinivas Aluru.
  • Precedence Constrained Scheduling in (2-7⁄3p+1) × Optimal. Journal of Computer and System Sciences. 2008. With Devdatta Gangal.
DBLP    Google Scholar    Semantic Scholar
sohoni Milind Sohoni
Combinatorial Optimization, Mathematical Programming, Algorithms.
  • Towards Polynomial Simplex-Like Algorithms for Market Equlibria. SODA 2013. With Jugal Garg, Ruta Mehta and Nisheeth K. Vishnoi.
  • A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities. STOC 2012. With Jugal Garg, Ruta Mehta and Vijay V. Vazirani.
  • Rank-1 bimatrix games: a homeomorphism and a polynomial time algorithm. STOC 2011. With Bharat Adsul, Jugal Garg and Ruta Mehta.
  • Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties. SIAM J. Computing. 2008. With Ketan Mulmuley.
  • A theory of regular MSC languages. Information & Computation. 2005. With Jesper G. Henriksen, Madhavan Mukund, K. Narayan Kumar and P. S. Thiagarajan.
DBLP    Semantic Scholar
sundar Sundar Vishwanathan
Algorithms, Combinatorics, Complexity Theory.
  • On Randomized Algorithms for Matching in the Online Preemptive Model. ESA 2015. With Ashish Chiplunkar and Sumedh Tirodkar.
  • On the Approximability of the Minimum Rainbow Subgraph Problem and Other Related Problems. ISAAC 2015. With Sumedh Tirodkar.
  • On Randomized Memoryless Algorithms for the Weighted K-Server Problem. FOCS 2013. With Ashish Chiplunkar.
  • A counting proof of the Graham-Pollak Theorem. Discrete Mathematics. 2013.
  • Random walks, electric networks and the transience class problem of sandpiles. SODA 2012. With Ayush Choure.
DBLP    Google Scholar    Semantic Scholar

Visiting Faculty

madhusudan Madhu Sudan
Gordon McKay Professor at Harvard University.
NR Kamath Chair Professor at IIT Bombay.

Related Faculty

akshayss S Akshay
Formal methods.
supratik Supratik Chakraborty
Sampling and counting, Formal Methods, Logic and Automata.
krishnas Krishna S
Automata theory, Logics, Games.
siva G Sivakumar
Logic, Formal verification.


Postdocs



Ph.D. Students



Ph.D. Alumni