Jaikumar Radhakrishnan

Yuval Emek, Magnús M. Halldórsson, Yishay Mansour, Boaz Patt-Shamir, Jaikumar Radhakrishnan, Dror Rawitz: Online Set Packing. SIAM J. Comput. 41(4): 728-746 (2012)

Alessandro Panconesi, Jaikumar Radhakrishnan: Expansion properties of (secure) wireless networks. ACM Transactions on Algorithms 8(3): 21 (2012)

Costas Busch, Chinmoy Dutta, Jaikumar Radhakrishnan, Rajmohan Rajaraman, Srinivasagopalan Srivathsan: Split and Join: Strong Partitions and Universal Steiner Trees for Graphs. FOCS 2012: 81-90

Chinmoy Dutta, Jaikumar Radhakrishnan: More on a Problem of Zarankiewicz. ISAAC 2012: 257-266

Deepak D'Souza, Telikepalli Kavitha, Jaikumar Radhakrishnan (Eds.): IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2012, December 15-17, 2012, Hyderabad, India. LIPIcs 18, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 2012, isbn 978-3-939897-47-7

Chinmoy Dutta, Jaikumar Radhakrishnan: More on a Problem of Zarankiewicz. CoRR abs/1201.1377 (2012)

Jaikumar Radhakrishnan, Saswata Shannigrahi: Streaming Algorithms for 2-Coloring Uniform Hypergraphs. WADS 2011: 667-678

Ajesh Babu, Nutan Limaye, Jaikumar Radhakrishnan, Girish Varma: Streaming algorithms for language recognition problems. CoRR abs/1104.0848 (2011)

Costas Busch, Chinmoy Dutta, Jaikumar Radhakrishnan, Rajmohan Rajaraman, Srinivasagopalan Srivathsan: Split and Join: Strong Partitions and Universal Steiner Trees for Graphs. CoRR abs/1111.4766 (2011)

Eli Ben-Sasson, Swastik Kopparty, Jaikumar Radhakrishnan: Subspace polynomials and limits to list decoding of Reed-Solomon codes. IEEE Transactions on Information Theory 56(1): 113-120 (2010)

Prahladh Harsha, Rahul Jain, David A. McAllester, Jaikumar Radhakrishnan: The communication complexity of correlation. IEEE Transactions on Information Theory 56(1): 438-449 (2010)

Jaikumar Radhakrishnan, Smit Shah, Saswata Shannigrahi: Data Structures for Storing Small Sets in the Bitprobe Model. ESA (2) 2010: 159-170

Yuval Emek, Magnús M. Halldórsson, Yishay Mansour, Boaz Patt-Shamir, Jaikumar Radhakrishnan, Dror Rawitz: Online set packing and competitive scheduling of multi-part tasks. PODC 2010: 440-449

Ajesh Babu, Jaikumar Radhakrishnan: An entropy based proof of the Moore bound for irregular graphs. CoRR abs/1011.1058 (2010)

Jaikumar Radhakrishnan, Martin Rötteler, Pranab Sen: Random Measurement Bases, Quantum State Distinction and Applications to the Hidden Subgroup Problem. Algorithmica 55(3): 490-516 (2009)

Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen: A property of quantum relative entropy with an application to privacy in quantum communication. J. ACM 56(6) (2009)

Parikshit Gopalan, Jaikumar Radhakrishnan: Finding duplicates in a data stream. SODA 2009: 402-411

Roberto Di Pietro, Luigi V. Mancini, Alessandro Mei, Alessandro Panconesi, Jaikumar Radhakrishnan: Redoubtable Sensor Networks. ACM Trans. Inf. Syst. Secur. 11(3) (2008)

Chinmoy Dutta, Jaikumar Radhakrishnan: Lower Bounds for Noisy Wireless Networks using Sampling Algorithms. FOCS 2008: 394-402

Prahladh Harsha, Thomas P. Hayes, Hariharan Narayanan, Harald Räcke, Jaikumar Radhakrishnan: Minimizing average latency in oblivious routing. SODA 2008: 200-207

Chinmoy Dutta, Yashodhan Kanoria, D. Manjunath, Jaikumar Radhakrishnan: A tight lower bound for parity in noisy communication networks. SODA 2008: 1056-1065

Rahul Jain, Pranab Sen, Jaikumar Radhakrishnan: Optimal Direct Sum and Privacy Trade-off Results for Quantum and Classical Communication Complexity. CoRR abs/0807.1267 (2008)

Magnús M. Halldórsson, Guy Kortsarz, Jaikumar Radhakrishnan, Sivaramakrishnan Sivasubramanian: Complete partitions of graphs. Combinatorica 27(5): 519-550 (2007)

Prahladh Harsha, Rahul Jain, David A. McAllester, Jaikumar Radhakrishnan: The Communication Complexity of Correlation. IEEE Conference on Computational Complexity 2007: 10-23

Eli Ben-Sasson, Swastik Kopparty, Jaikumar Radhakrishnan: Subspace Polynomials and List Decoding of Reed-Solomon Codes. FOCS 2006: 207-216

Sourav Chakraborty, Jaikumar Radhakrishnan, Nandakumar Raghunathan, Prashant Sasatte: Zero Error List-Decoding Capacity of the q/(q-1) Channel. FSTTCS 2006: 129-138

Jaikumar Radhakrishnan: Gap Amplification in PCPs Using Lazy Random Walks. ICALP (1) 2006: 96-107

Roberto Di Pietro, Luigi V. Mancini, Alessandro Mei, Alessandro Panconesi, Jaikumar Radhakrishnan: Sensor Networks that Are Provably Resilient. SecureComm 2006: 1-10

Chinmoy Dutta, Jaikumar Radhakrishnan: Tradeoffs in Depth-Two Superconcentrators. STACS 2006: 372-383

Prahladh Harsha, Rahul Jain, David A. McAllester, Jaikumar Radhakrishnan: The communication complexity of correlation. Electronic Colloquium on Computational Complexity (ECCC) 13(151) (2006)

Devdatt P. Dubhashi, Alessandro Mei, Alessandro Panconesi, Jaikumar Radhakrishnan, Aravind Srinivasan: Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons. J. Comput. Syst. Sci. 71(4): 467-479 (2005)

Nathan Linial, Jaikumar Radhakrishnan: Essential covers of the cube by hyperplanes. J. Comb. Theory, Ser. A 109(2): 331-338 (2005)

Amit Deshpande, Rahul Jain, Telikepalli Kavitha, Satyanarayana V. Lokam, Jaikumar Radhakrishnan: Lower bounds for adaptive locally decodable codes. Random Struct. Algorithms 27(3): 358-378 (2005)

Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener: On converting CNF to DNF. Theor. Comput. Sci. 347(1-2): 325-335 (2005)

Sourav Chakraborty, Jaikumar Radhakrishnan, Nandakumar Raghunathan: Bounds for Error Reduction with Few Quantum Queries. APPROX-RANDOM 2005: 245-256

Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen: Prior Entanglement, Message Compression and Privacy in Quantum Communication. IEEE Conference on Computational Complexity 2005: 285-296

Jaikumar Radhakrishnan, Martin Rötteler, Pranab Sen: On the Power of Random Bases in Fourier Sampling: Hidden Subgroup Problem in the Heisenberg Group. ICALP 2005: 1399-1411

Guy Kortsarz, Jaikumar Radhakrishnan, Sivaramakrishnan Sivasubramanian: Complete partitions of graphs. SODA 2005: 860-869

Lov K. Grover, Jaikumar Radhakrishnan: Is partial quantum search of a database any easier? SPAA 2005: 186-194

Roberto Di Pietro, Luigi V. Mancini, Alessandro Mei, Alessandro Panconesi, Jaikumar Radhakrishnan: Connectivity properties of secure wireless sensor networks. SASN 2004: 53-58

Alessandro Panconesi, Jaikumar Radhakrishnan: Expansion properties of (secure) wireless networks. SPAA 2004: 281-285

Jaikumar Radhakrishnan: A note on scrambling permutations. Random Struct. Algorithms 22(4): 435-439 (2003)

Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen: A Lower Bound for the Bounded Round Quantum Communication Complexity of Set Disjointness. FOCS 2003: 220-229

Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen: A Direct Sum Theorem in Communication Complexity via Message Compression. ICALP 2003: 300-315

Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener: On Converting CNF to DNF. MFCS 2003: 612-621

Devdatt P. Dubhashi, Alessandro Mei, Alessandro Panconesi, Jaikumar Radhakrishnan, Aravind Srinivasan: Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons. SODA 2003: 717-724

Paritosh K. Pandya, Jaikumar Radhakrishnan (Eds.): FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 23rd Conference, Mumbai, India, December 15-17, 2003, Proceedings. Lecture Notes in Computer Science 2914, Springer 2003, isbn 3-540-20680-9

Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen: A direct sum theorem in communication complexity via message compression. CoRR cs.CC/0304020 (2003)

Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener: On Converting CNF to DNF. Electronic Colloquium on Computational Complexity (ECCC) 10(017) (2003)

Jaikumar Radhakrishnan, Pranab Sen, Srinivasan Venkatesh: The Quantum Complexity of Set Membership. Algorithmica 34(4): 462-479 (2002)

Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, Srinivasan Venkatesh: Are Bitvectors Optimal? SIAM J. Comput. 31(6): 1723-1744 (2002)

Amit Deshpande, Rahul Jain, Telikepalli Kavitha, Jaikumar Radhakrishnan, Satyanarayana V. Lokam: Better Lower Bounds for Locally Decodable Codes. IEEE Conference on Computational Complexity 2002: 184-193

Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen: Privacy and Interaction in Quantum Communication Complexity and a Theorem about the Relative Entropy of Quantum States. FOCS 2002: 429-438

Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen: The Quantum Communication Complexity of the Pointer Chasing Problem: The Bit Version. FSTTCS 2002: 218-229

S. Mishra, Jaikumar Radhakrishnan, Sivaramakrishnan Sivasubramanian: On the Hardness of Approximating Minimum Monopoly Problems. FSTTCS 2002: 277-288

Jaikumar Radhakrishnan, Venkatesh Raman: A tradeoff between search and update in dictionaries. Inf. Process. Lett. 80(5): 243-247 (2001)

Stephen Ponzio, Jaikumar Radhakrishnan, Srinivasan Venkatesh: The Communication Complexity of Pointer Chasing. J. Comput. Syst. Sci. 62(2): 323-355 (2001)

Jaikumar Radhakrishnan, Venkatesh Raman, S. Srinivasa Rao: Explicit Deterministic Constructions for Membership in the Bitprobe Model. ESA 2001: 290-299

Jaikumar Radhakrishnan, Pranab Sen, Sundar Vishwanathan: Depth-3 Arithmetic Circuits for S^2_n(X) and Extensions of the Graham-Pollack Theorem. CoRR cs.DM/0110031 (2001)

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. Discrete Math. 13(1): 2-24 (2000)

Jaikumar Radhakrishnan, Pranab Sen, Srinivasan Venkatesh: The Quantum Complexity of Set Membership. FOCS 2000: 554-562

Jaikumar Radhakrishnan, Pranab Sen, Sundar Vishwanathan: Depth-3 Arithmetic Circuits for S_n²(X) and Extensions of the Graham-Pollack Theorem. FSTTCS 2000: 176-187

Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, Srinivasan Venkatesh: Are bitvectors optimal? STOC 2000: 449-458

Jaikumar Radhakrishnan, Pranab Sen, Srinivasan Venkatesh: The Quantum Complexity of Set Membership. CoRR quant-ph/0007021 (2000)

Stephen Ponzio, Jaikumar Radhakrishnan, Srinivasan Venkatesh: The Communication Complexity of Pointer Chasing Applications of Entropy and Sampling (Abstract). IEEE Conference on Computational Complexity 1999: 7

Stephen Ponzio, Jaikumar Radhakrishnan, Srinivasan Venkatesh: The Communication Complexity of Pointer Chasing: Applications of Entropy and Sampling. STOC 1999: 602-611

Madhavan Mukund, K. Narayan Kumar, Jaikumar Radhakrishnan, Milind A. Sohoni: Towards a Characterisation of Finite-State Message-Passing Systems. ASIAN 1998: 282-299

Jaikumar Radhakrishnan, Aravind Srinivasan: Improved Bounds and Algorithms for Hypergraph Two-Coloring. FOCS 1998: 684-693

Madhavan Mukund, K. Narayan Kumar, Jaikumar Radhakrishnan, Milind A. Sohoni: Robust Asynchronous Protocols Are Finite-State. ICALP 1998: 188-199

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)

Shiva Chaudhuri, Jaikumar Radhakrishnan: The Complexity of Parallel Prefix Problems on Small Domains. Inf. Comput. 138(1): 1-22 (1997)

Jaikumar Radhakrishnan: Better Lower Bounds for Monotone Threshold Formulas. J. Comput. Syst. Sci. 54(2): 221-226 (1997)

Jaikumar Radhakrishnan: An Entropy Proof of Bregman's Theorem. J. Comb. Theory, Ser. A 77(1): 161-164 (1997)

Jaikumar Radhakrishnan, Amnon Ta-Shma: Tight Bounds for Depth-two Superconcentrators. FOCS 1997: 585-594

Jaikumar Radhakrishnan: Pi-Sigma-Pi Threshold Formulas. Mathematical Systems Theory 29(4): 357-374 (1996)

Gerth Stølting Brodal, Shiva Chaudhuri, Jaikumar Radhakrishnan: The Randomized Complexity of Maintaining the Minimum. Nord. J. Comput. 3(4): 337-351 (1996)

Shiva Chaudhuri, Jaikumar Radhakrishnan: Deterministic Restrictions in Circuit Complexity. STOC 1996: 30-36

Gerth Stølting Brodal, Shiva Chaudhuri, Jaikumar Radhakrishnan: The Randomized Complexity of Maintaining the Minimum. SWAT 1996: 4-15

Shiva Chaudhuri, Jaikumar Radhakrishnan: Deterministic Restrictions in Circuit Complexity. Electronic Colloquium on Computational Complexity (ECCC) 3(4) (1996)

Tetsuro Nishino, Jaikumar Radhakrishnan: On the Number of Negations Needed to Compute Parity Functions. IEICE Transactions 78-D(1): 90-91 (1995)

Jaikumar Radhakrishnan: Sigma Pi Sigma Threshold Formulas. Combinatorica 14(3): 345-374 (1994)

Jaikumar Radhakrishnan, K. V. Subrahmanyam: Directed Monotone Contact Networks for Threshold Functions. Inf. Process. Lett. 50(4): 199-203 (1994)

Magnús M. Halldórsson, Jaikumar Radhakrishnan: Improved Approximations of Independent Sets in Bounded-Degree Graphs via Subgraph Removal. Nord. J. Comput. 1(4): 475-492 (1994)

Magnús M. Halldórsson, Jaikumar Radhakrishnan: Greed is good: approximating independent sets in sparse and bounded-degree graphs. STOC 1994: 439-448

Magnús M. Halldórsson, Jaikumar Radhakrishnan: Improved Approximations of Independent Sets in Bounded-Degree Graphs. SWAT 1994: 195-206

Magnús M. Halldórsson, Jaikumar Radhakrishnan, K. V. Subrahmanyam: Directed vs. Undirected Monotone Contact Networks for Threshold Functions. FOCS 1993: 604-613

Magnús M. Halldórsson, Jaikumar Radhakrishnan, K. V. Subrahmanyam: On Some Communication Complexity Problems Related to THreshold Functions. FSTTCS 1993: 248-259

Jaikumar Radhakrishnan: Improved Bounds for Covering Complete Uniform Hypergraphs. Inf. Process. Lett. 41(4): 203-207 (1992)

Shiva Chaudhuri, Jaikumar Radhakrishnan: The Complexity of Parallel Prefix Problems on Small Domains. FOCS 1992: 638-647

Jaikumar Radhakrishnan: Better Bounds for Threshold Formulas. FOCS 1991: 314-323