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
Computational and Discrete Geometry, Algorithms, Graph Theory, Graph Drawing & Network Visualization
  • Euclidean Steiner Spanners: Light and Sparse, with Csaba D. Tóth, SIAM J. Discret. Math. 2022.
  • Online Spanners in Metric Spaces, With Arnold Filtser, Hadi Khodabandeh, Csaba D. Tóth, ESA 2022.
  • On Erdos-Szekeres-type Problems for k-Convex Point Sets, with Martin Balko, Leonardo Martínez-Sandoval, Pavel Valtr, Eur. J. Combinatorics, 2020.
  • Planar Bichromatic Bottleneck Spanning Trees, with A. Karim Abu-Affash, Paz Carmi, Joseph S.B. Mitchell, J. Comput. Geom., 2021.
  • Parameterized Study of Steiner Tree on Unit Disk Graphs, with Paz Carmi, Sudeshna Kolay, Meirav Zehavi, Algorithmica 2022.
  • An Algorithmic Study of Fully Dynamic Independent Sets for Map Labeling, with Guangping Li, Martin Nöllenburg, ACM J. Exp. Algorithmics, 2022.
  • Worbel: Aggregating Point Labels into Word Clouds, with Robert Ganian, Guangping Li, Martin Nöllenburg, Jules Wulms, SIGSPATIAL/GIS, 2021.
DBLP    Google Scholar   
nutan 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
mrinal Mrinal Kumar
Computational Complexity, Algebraic Complexity, Algebra & Computation, and Error Correcting Codes
  • A quadratic lower bound for homogeneous algebraic branching programs. Computational Complexity 2019.
  • The Computational Power of Depth Five Arithmetic Circuits. With Ramprasad Saptharishi. SIAM J. Comput. 2019.
  • Derandomization from Algebraic Hardness: Treading the Borders. With Zeyu Guo, Ramprasad Saptharishi, Noam Solomon. FOCS 2019
  • Hardness vs Randomness for Bounded Depth Arithmetic Circuits. With Chi-Ning Chou, Noam Solomon. CCC 2018.
  • On the Power of Homogeneous Depth 4 Arithmetic Circuits. With Shubhangi Saraf. FOCS 2014
  • Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields. With Swastik Kopparty, Michael E. Saks. ICALP 2014
DBLP    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