# 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

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.

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 P
_{4}-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.

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.

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.

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

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.

Manoj Prabhakaran

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.

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.

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.

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.

### Visiting Faculty

### Related Faculty

## Postdocs

- Nikhil Balaji [October 2015 -- January 2017]
- Suryajith Chillara [October 2017 -- October 2019]
- Deepesh Data [October 2017 -- March 2018]
- Christian Engels [September 2017 -- October 2019]
- Bodhayan Roy [December 2015 -- March 2017]
- Sumanta Ghosh [December 2019 -- September 2021]
- Abhranil Chatterjee [October 2021 -- October 2022]

## Ph.D. Students

- Anand Babu
- Apoorv Garg
- Monu Y
- Rajeevalochana MR
- Kaartik Bhushan
- Prasad Chaugule
- Chandra Kanta Mohapatra
- Vaibhav Krishan
- Roshan Raj
- Sarfaraz Equbal

## Ph.D. Alumni

- Ashish Chiplunkar. Ph.D. 2016. Assistant Professor, IIT Delhi
- Sumedh Tirodkar. Ph.D. 2017. Post-doctoral Researcher, SUPSI-IDSIA, Switzerland.
- Jinesh Machchhar. Ph.D. 2015. Assistant Professor, IIT Mandi
- Soumitra Pal. Ph.D. 2013. Research Fellow, National Center for Biotechnology Information, National Library of Medicine
- Ruta Mehta. Ph.D. 2012. Assistant Professor, University of Illinois at Urbana-Champaign
- Jugal Garg. Ph.D. 2012. Research Assistant Professor, University of Illinois at Urbana-Champaign
- Ayush Choure. Ph.D. 2012. Senior Applied Scientist. Microsoft Research Bangalore.
- Sreyash Kenkre. Ph.D. 2010. Research Scientist. IBM India Research Labs, Bangalore.
- Sudeep K S. Ph.D. 2007. Assistant Professor. NIT Calicut.

## Undergraduate Alumni

*(This is an incomplete list of alumni of our undergraduate programme who have made notable contributions to Theoretical Computer Science. Please let us know if you notice any errors or omissions.)*

Aditi Laddha '17 (Georgia Tech)

Aditya Bhaskara '07 (Utah)

Ajay Nerurkar '93

Akash Nanavati '97

Amit Chakrabarti '97 (Dartmouth)

Anish Das Sarma '04 (Google)

Apurva Mudgal '02 (IIT Ropar)

Aranyak Mehta '00 (Google)

Ashok Kumar Ponnusami '02 (Microsoft)

Ashwin Rao '93 (Adj. Faculty, Stanford)

Atish Das Sarma '05

B. Srivathsan '09 (CMI)

Bharat Adsul '97 (IITB)

Chinmay Karande '06

Deeparnab Chakrabarti '03 (Dartmouth)

Devavrat Shah '99 (M.I.T)

Dilys Thomas '02

Divakar Vishwanath '92 (U.Mich)

Gopi Sivakanth '13 (MSR)

Jaydeep Chipalkatti '91 (Math U. Manitoba)

Jugal Garg '01 (UIUC)

K.V. Subramanian '86 (CMI)

Kuldeep Meel '12 (NUS)

Kunal Mittal '19 (Princeton)

M.V. Kameshwar '98 (Duke University)

Madhavan Mukund '86 (CMI)

Manik Dhar '16 (Princeton)

Manoj Prabhakaran '00 (IITB)

Mayur Datar '98 (Flipkart)

Meena Mahajan '86 (IMSc)

Milind Sohoni '86 (IITB)

Moses Charikar '95 (Stanford)

Navin Goyal '98 (MSR Bangalore)

Nikhil Bansal '99 (U. Mich.)

Nikhil Devanur '01 (Amazon)

Nikhil Vyas '17 (MIT)

Nisarg Shah '11 (Toronto)

Nisheet Vishnoi '99 (Yale)

Parikshit Gopalan '00 (VMWare)

Pradyut Shah '94

Pranab Sen '94 (TIFR)

Pritish Kamath '12 (Google Research)

Rahul Sami '98 (U.Mich)

Rahul Shah '97 (Louisiana State University)

Rajat Mittal '04 (IIT Kanpur)

Rajneesh Hegde '97 (Microsoft)

Rakesh Venkat '08 (IIT Hyderabad)

Rina Panigrahy '95 (Google Research)

Sachin Lodha '96 (TCS Labs)

Sachin Patkar '86 (IITB)

Sai Sandeep Reddy '17 (CMU)

Sanjit Seshia '98 (UC Berkley).

Satyen Kale '02 (Google Research)

Shourya Pandey '20 (U.Texas)

Subhash Khot '99 (NYU)

Sundar Vishwanathan '85 (IITB)

Suresh Nayak '91 (ISI Bangalore)

Sushant Sachdeva '08 (Toronto)

Swapneel Mahajan '96 (IITB)

Tarun Kathuria '15 (Berkeley)

Upendra Kulkarni '92 (CMI Math)

Varun Kanade '06 (Oxford)

Vijaykrishna Gurunathan '21 (Stanford)

Vishwanath Nagarajan '03 (U. Mich)

Vivek Madan '12 (Amazon)