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 GroupClick here to find out about the upcoming talks and browse through the past talks/events.
Faculty in the Theory Group
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 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.
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.
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
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.
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.
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.
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.
Srikanth Srinivasan (Dept. of Mathematics)
Computational Complexity theory. Especially, Circuit complexity, Pseudorandom objects, and related areas of mathematics.
- On Polynomial Approximations to AC^0. APPROX-RANDOM 2016. With Prahladh Harsha.
- Derandomized Graph Product Results Using the Low Degree Long Code. STACS 2015. With Irit Dinur, Prahladh Harsha and Girish Varma.
- An exponential lower bound for homogeneous depth four arithmetic formulas. FOCS 2014. With Neeraj Kayal, Nutan Limaye and Chandan Saha.
- Super-polylogarithmic hypergraph coloring hardness via low-degree long codes. STOC 2014. With Venkatesan Guruswami, Prahladh Harsha, Johan Håstad and Girish Varma.
- Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas. STOC 2014. With Neeraj Kayal, Nutan Limaye and Chandan Saha.
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.
Gordon McKay Professor at Harvard University.
NR Kamath Chair Professor at IIT Bombay.
NR Kamath Chair Professor at IIT Bombay.
Sampling and counting, Formal Methods, Logic and Automata.
Automata theory, Logics, Games.
Logic, Formal verification.
- Ashish Chiplunkar. Ph.D. 2016. Postdoc, Tel-Aviv University
- Sumedh Tirodkar. Visiting Fellow. TIFR.
- Jinesh Machchhar. Ph.D. 2015. Postdoc, Technion - Israel Institute of Technology
- Soumitra Pal. Ph.D. 2013. Post-doctoral Research Fellow. University of Connecticut.
- 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.