ICTS

Research Interests

Theoretical computer science, complexity theory, randomness and computing, quantum information and computation, combinatorics, information theory

Education

BTech (1985), Computer Science and Engineering, IIT Kharagpur

MS and PhD (1991), Rutgers University, New Jersey, USA

Employment

• Associate Systems Engineer, CMC Ltd, Kolkata, Jun1985 to Jun 1986
• Visiting Fellow, Theoretical Computer Science Group, Tata Institute of Fundamental Research, Sep 1991 to Jan 1992
• Visiting Associate Professor, School of Information Science,  Japan Advanced Institute of Science and Technology (JAIST), Hokuriku, Japan, Oct 1992 to Sep 1993 (on leave from TIFR) 
• Fellow, Theoretical Computer Science Group, Tata Institute of Fundamental Research, Feb 1992 to Jan 1997 
• Postdoctoral visitor, School of Computer Science and Engineering, The Hebrew University of Jerusalem, Oct 1996 to Oct 1997 (on leave from TIFR)
• Reader, School of Technology and Computer Science, Tata Institute of Fundamental Research, Feb 1997 to Aug 2000
• Associate Professor, School of Technology and Computer Science, Tata Institute of Fundamental Research, Aug 2000 to Feb 2007
• Professor, School of Technology and Computer Science, Tata Institute of Fundamental Research, Feb 2007 to Dec 2017
• Senior Professor, School of Technology and Computer Science, Tata Institute of Fundamental Research, Jan 2017 onwards

Selected Publications (complete list at DBLP)

• Shyam Dhamapurkar, Shubham Vivek Pawar, Jaikumar Radhakrishnan: Set Membership with Two Classical and Quantum Bit Probes. ICALP 2022: 52:1-52:19
• Siddharth Bhandari, Jaikumar Radhakrishnan: Bounds on the Zero-Error List-Decoding Capacity of the q/(q - 1) Channel. IEEE Trans. Inf. Theory 68(1): 238-247 (2022)
• Marco Dalai, Venkatesan Guruswami, Jaikumar Radhakrishnan: An Improved Bound on the Zero-Error List-Decoding Capacity of the 4/3 Channel. IEEE Trans. Inf. Theory 66(2): 749-756 (2020)
• Kshitij Gajjar, Jaikumar Radhakrishnan: Parametric Shortest Paths in Planar Graphs. FOCS 2019: 876-895
• Sagnik Mukhopadhyay, Jaikumar Radhakrishnan, Swagato Sanyal: Separation Between Deterministic and Randomized Query Complexity. SIAM J. Comput. 47(4): 1644-1666 (2018)
• Jaikumar Radhakrishnan, Pranab Sen, Naqueeb Ahmad Warsi: One-Shot Marton Inner Bound for Classical-Quantum Broadcast Channel. IEEE Trans. Inf. Theory 62(5): 2836-2848 (2016)
• Mohit Garg, Jaikumar Radhakrishnan: Set membership with a few bit probes. SODA 2015: 776-784
• Eli Ben-Sasson, Swastik Kopparty, Jaikumar Radhakrishnan: Subspace polynomials and limits to list decoding of Reed-Solomon codes. IEEE Trans. Inf. Theory 56(1): 113-120 (2010)
• Prahladh Harsha, Rahul Jain, David A. McAllester, Jaikumar Radhakrishnan: The communication complexity of correlation. IEEE Trans. Inf. Theory 56(1): 438-449 (2010)
• Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen: A property of quantum relative entropy with an application to privacy in quantum communication. J. ACM 56(6): 33:1-33:32 (2009)
• Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, Srinivasan Venkatesh: Are Bitvectors Optimal? SIAM J. Comput. 31(6): 1723-1744 (2002)
• Jaikumar Radhakrishnan, Aravind Srinivasan: Improved bounds and algorithms for hypergraph 2-coloring. Random Struct. Algorithms 16(1): 4-32 (2000)
• Jaikumar Radhakrishnan, Amnon Ta-Shma: Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators. SIAM J. Discret. Math. 13(1): 2-24 (2000)
• Magnús M. Halldórsson, Jaikumar Radhakrishnan: Greed is Good: Approximating Independent Sets in Sparse and Bounded-Degree Graphs. Algorithmica 18(1): 145-163 (1997)
• Jaikumar Radhakrishnan: Better Lower Bounds for Monotone Threshold Formulas. J. Comput. Syst. Sci. 54(2): 221-226 (1997)