Better Bounds for Threshold Formulas - Jaikumar Radhakrishnan (FOCS, 1991)

Improved Bounds for Covering Complete Uniform Hypergraphs. - Jaikumar Radhakrishnan (Inf. Process. Lett., 1992)

Directed vs. Undirected Monotone Contact Networks for Threshold Functions - Magnús M. Halldórsson; Jaikumar Radhakrishnan; K. V. Subrahmanyam 001 (FOCS, 1993)

On Some Communication Complexity Problems Related to THreshold Functions. - Magnús M. Halldórsson; Jaikumar Radhakrishnan; K. V. Subrahmanyam 001 (FSTTCS, 1993)

Improved Approximations of Independent Sets in Bounded-Degree Graphs. - Magnús M. Halldórsson; Jaikumar Radhakrishnan (SWAT, 1994)

Sigma Pi Sigma Threshold Formulas. - Jaikumar Radhakrishnan (Comb., 1994)

Directed Monotone Contact Networks for Threshold Functions. - Jaikumar Radhakrishnan; K. V. Subrahmanyam 001 (Inf. Process. Lett., 1994)

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

On the Number of Negations Needed to Compute Parity Functions. - Tetsuro Nishino; Jaikumar Radhakrishnan (IEICE Trans. Inf. Syst., 1995)

Deterministic Restrictions in Circuit Complexity - Shiva Chaudhuri; Jaikumar Radhakrishnan (Electron. Colloquium Comput. Complex., 1996)

Pi-Sigma-Pi Threshold Formulas. - Jaikumar Radhakrishnan (Math. Syst. Theory, 1996)

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

Tight Bounds for Depth-two Superconcentrators. - Jaikumar Radhakrishnan; Amnon Ta-Shma (FOCS, 1997)

Greed is Good: Approximating Independent Sets in Sparse and Bounded-Degree Graphs. - Magnús M. Halldórsson; Jaikumar Radhakrishnan (Algorithmica, 1997)

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

Better Lower Bounds for Monotone Threshold Formulas. - Jaikumar Radhakrishnan (J. Comput. Syst. Sci., 1997)

An Entropy Proof of Bregman's Theorem. - Jaikumar Radhakrishnan (J. Comb. Theory A, 1997)

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

Improved Bounds and Algorithms for Hypergraph Two-Coloring. - Jaikumar Radhakrishnan; Aravind Srinivasan (FOCS, 1998)

Robust Asynchronous Protocols Are Finite-State. - Madhavan Mukund; K. Narayan Kumar; Jaikumar Radhakrishnan; Milind A. Sohoni (ICALP, 1998)

The Communication Complexity of Pointer Chasing Applications of Entropy and Sampling (Abstract). - Stephen Ponzio; Jaikumar Radhakrishnan; Srinivasan Venkatesh 001 (CCC, 1999)

The Communication Complexity of Pointer Chasing: Applications of Entropy and Sampling. - Stephen Ponzio; Jaikumar Radhakrishnan; Srinivasan Venkatesh 001 (STOC, 1999)

Depth-3 Arithmetic Circuits for Sn2(X) and Extensions of the Graham-Pollack Theorem. - Jaikumar Radhakrishnan; Pranab Sen; Sundar Vishwanathan (FSTTCS, 2000)

Improved bounds and algorithms for hypergraph 2-coloring. - Jaikumar Radhakrishnan; Aravind Srinivasan (Random Struct. Algorithms, 2000)

Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators. - Jaikumar Radhakrishnan; Amnon Ta-Shma (SIAM J. Discret. Math., 2000)

Explicit Deterministic Constructions for Membership in the Bitprobe Model. - Jaikumar Radhakrishnan; Venkatesh Raman 001; S. Srinivasa Rao 001 (ESA, 2001)

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

A tradeoff between search and update in dictionaries. - Jaikumar Radhakrishnan; Venkatesh Raman 001 (Inf. Process. Lett., 2001)

The Communication Complexity of Pointer Chasing. - Stephen Ponzio; Jaikumar Radhakrishnan; Srinivasan Venkatesh 001 (J. Comput. Syst. Sci., 2001)

Better Lower Bounds for Locally Decodable Codes. - Amit Deshpande 001; Rahul Jain 001; Telikepalli Kavitha; Jaikumar Radhakrishnan; Satyanarayana V. Lokam (CCC, 2002)

Privacy and Interaction in Quantum Communication Complexity and a Theorem about the Relative Entropy of Quantum States. - Rahul Jain 001; Jaikumar Radhakrishnan; Pranab Sen (FOCS, 2002)

The Quantum Communication Complexity of the Pointer Chasing Problem: The Bit Version. - Rahul Jain 001; Jaikumar Radhakrishnan; Pranab Sen (FSTTCS, 2002)

On the Hardness of Approximating Minimum Monopoly Problems. - S. Mishra; Jaikumar Radhakrishnan; Sivaramakrishnan Sivasubramanian (FSTTCS, 2002)

The Quantum Complexity of Set Membership. - Jaikumar Radhakrishnan; Pranab Sen; Srinivasan Venkatesh 001 (Algorithmica, 2002)

Are Bitvectors Optimal? - Harry Buhrman; Peter Bro Miltersen; Jaikumar Radhakrishnan; Srinivasan Venkatesh 001 (SIAM J. Comput., 2002)

A Lower Bound for the Bounded Round Quantum Communication Complexity of Set Disjointness. - Rahul Jain 001; Jaikumar Radhakrishnan; Pranab Sen (FOCS, 2003)

A Direct Sum Theorem in Communication Complexity via Message Compression. - Rahul Jain 001; Jaikumar Radhakrishnan; Pranab Sen (ICALP, 2003)

A note on scrambling permutations. - Jaikumar Radhakrishnan (Random Struct. Algorithms, 2003)

Connectivity properties of secure wireless sensor networks. - Roberto Di Pietro; Luigi V. Mancini; Alessandro Mei; Alessandro Panconesi; Jaikumar Radhakrishnan (SASN, 2004)

Bounds for Error Reduction with Few Quantum Queries. - Sourav Chakraborty 001; Jaikumar Radhakrishnan; Nandakumar Raghunathan (APPROX-RANDOM, 2005)

Prior Entanglement, Message Compression and Privacy in Quantum Communication. - Rahul Jain 001; Jaikumar Radhakrishnan; Pranab Sen (CCC, 2005)

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

Complete partitions of graphs. - Guy Kortsarz; Jaikumar Radhakrishnan; Sivaramakrishnan Sivasubramanian (SODA, 2005)

Is partial quantum search of a database any easier? - Lov K. Grover; Jaikumar Radhakrishnan (SPAA, 2005)

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

Essential covers of the cube by hyperplanes. - Nathan Linial; Jaikumar Radhakrishnan (J. Comb. Theory A, 2005)

Lower bounds for adaptive locally decodable codes. - Amit Deshpande 001; Rahul Jain 001; Telikepalli Kavitha; Satyanarayana V. Lokam; Jaikumar Radhakrishnan (Random Struct. Algorithms, 2005)

On converting CNF to DNF. - Peter Bro Miltersen; Jaikumar Radhakrishnan; Ingo Wegener (Theor. Comput. Sci., 2005)

Subspace Polynomials and List Decoding of Reed-Solomon Codes. - Eli Ben-Sasson; Swastik Kopparty; Jaikumar Radhakrishnan (FOCS, 2006)

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

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

Sensor Networks that Are Provably Resilient. - Roberto Di Pietro; Luigi V. Mancini; Alessandro Mei; Alessandro Panconesi; Jaikumar Radhakrishnan (SecureComm, 2006)

Tradeoffs in Depth-Two Superconcentrators. - Chinmoy Dutta; Jaikumar Radhakrishnan (STACS, 2006)

The communication complexity of correlation. - Prahladh Harsha; Rahul Jain 001; David A. McAllester; Jaikumar Radhakrishnan (Electron. Colloquium Comput. Complex., 2006)

Complete partitions of graphs. - Magnús M. Halldórsson; Guy Kortsarz; Jaikumar Radhakrishnan; Sivaramakrishnan Sivasubramanian (Comb., 2007)

Lower Bounds for Noisy Wireless Networks using Sampling Algorithms. - Chinmoy Dutta; Jaikumar Radhakrishnan (FOCS, 2008)

Unassailable sensor networks. - Alessandro Mei; Alessandro Panconesi; Jaikumar Radhakrishnan (SecureComm, 2008)

A tight lower bound for parity in noisy communication networks. - Chinmoy Dutta; Yashodhan Kanoria; D. Manjunath; Jaikumar Radhakrishnan (SODA, 2008)

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

Optimal Direct Sum and Privacy Trade-off Results for Quantum and Classical Communication Complexity - Rahul Jain 001; Pranab Sen; Jaikumar Radhakrishnan (CoRR, 2008)

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

Finding duplicates in a data stream. - Parikshit Gopalan; Jaikumar Radhakrishnan (SODA, 2009)

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

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

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

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

An entropy based proof of the Moore bound for irregular graphs - Ajesh Babu; Jaikumar Radhakrishnan (CoRR, 2010)

Subspace polynomials and limits to list decoding of Reed-Solomon codes. - Eli Ben-Sasson; Swastik Kopparty; Jaikumar Radhakrishnan (IEEE Trans. Inf. Theory, 2010)

Streaming Algorithms for 2-Coloring Uniform Hypergraphs. - Jaikumar Radhakrishnan; Saswata Shannigrahi (WADS, 2011)

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

More on a Problem of Zarankiewicz. - Chinmoy Dutta; Jaikumar Radhakrishnan (ISAAC, 2012)

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

Expansion properties of (secure) wireless networks. - Alessandro Panconesi; Jaikumar Radhakrishnan (ACM Trans. Algorithms, 2012)

Streaming algorithms for language recognition problems. - Ajesh Babu; Nutan Limaye; Jaikumar Radhakrishnan; Girish Varma (Theor. Comput. Sci., 2013)

One-shot Marton inner bound for classical-quantum broadcast channel. - Jaikumar Radhakrishnan; Pranab Sen; Naqueeb Warsi (CoRR, 2014)

Topology matters in communication. - Arkadev Chattopadhyay; Jaikumar Radhakrishnan; Atri Rudra (Electron. Colloquium Comput. Complex., 2014)

Set membership with a few bit probes. - Mohit Garg 003; Jaikumar Radhakrishnan (SODA, 2015)

How Hard is Computing Parity with Noisy Communications? - Chinmoy Dutta; Yashodhan Kanoria; D. Manjunath; Jaikumar Radhakrishnan (CoRR, 2015)

A Sampling Technique of Proving Lower Bounds for Noisy Computations. - Chinmoy Dutta; Jaikumar Radhakrishnan (CoRR, 2015)

Hypergraph Two-Coloring in the Streaming Model. - Jaikumar Radhakrishnan; Saswata Shannigrahi; Rakesh Venkat (CoRR, 2015)

Relaxed partition bound is quadratically tight for product distributions. - Prahladh Harsha; Rahul Jain 001; Jaikumar Radhakrishnan (Electron. Colloquium Comput. Complex., 2015)

Partition Bound Is Quadratically Tight for Product Distributions. - Prahladh Harsha; Rahul Jain 001; Jaikumar Radhakrishnan (ICALP, 2016)

Coordination Complexity: Small Information Coordinating Large Populations. - Rachel Cummings; Katrina Ligett; Jaikumar Radhakrishnan; Aaron Roth 001; Zhiwei Steven Wu (ITCS, 2016)

Tight bounds for communication assisted agreement distillation. - Venkatesan Guruswami; Jaikumar Radhakrishnan (Electron. Colloquium Comput. Complex., 2016)

The zero-error randomized query complexity of the pointer function. - Jaikumar Radhakrishnan; Swagato Sanyal (Electron. Colloquium Comput. Complex., 2016)

One-Shot Marton Inner Bound for Classical-Quantum Broadcast Channel. - Jaikumar Radhakrishnan; Pranab Sen; Naqueeb Ahmad Warsi (IEEE Trans. Inf. Theory, 2016)

Distance-Preserving Subgraphs of Interval Graphs. - Kshitij Gajjar; Jaikumar Radhakrishnan (ESA, 2017)

Set Membership with Non-Adaptive Bit Probes. - Mohit Garg 003; Jaikumar Radhakrishnan (STACS, 2017)

Parametric Shortest Paths in Planar Graphs. - Kshitij Gajjar; Jaikumar Radhakrishnan (Electron. Colloquium Comput. Complex., 2018)

Separation Between Deterministic and Randomized Query Complexity. - Sagnik Mukhopadhyay; Jaikumar Radhakrishnan; Swagato Sanyal (SIAM J. Comput., 2018)

Minimizing Branching Vertices in Distance-Preserving Subgraphs. - Kshitij Gajjar; Jaikumar Radhakrishnan (CSR, 2019)

Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes. - Palash Dey; Jaikumar Radhakrishnan; Santhoshini Velusamy (MFCS, 2020)

An Improved Bound on the Zero-Error List-Decoding Capacity of the 4/3 Channel. - Marco Dalai; Venkatesan Guruswami; Jaikumar Radhakrishnan (IEEE Trans. Inf. Theory, 2020)

Property B: Two-Coloring Non-Uniform Hypergraphs. - Jaikumar Radhakrishnan; Aravind Srinivasan (FSTTCS, 2021)

Generalized parametric path problems. - Kshitij Gajjar; Girish Varma; Prerona Chatterjee; Jaikumar Radhakrishnan (UAI, 2021)

Set Membership with Two Classical and Quantum Bit Probes. - Shyam Dhamapurkar; Shubham Vivek Pawar; Jaikumar Radhakrishnan (ICALP, 2022)

Randomized versus Deterministic Decision Tree Size. - Arkadev Chattopadhyay; Yogesh Dahiya; Nikhil S. Mande; Jaikumar Radhakrishnan; Swagato Sanyal (Electron. Colloquium Comput. Complex., 2022)

Bounds on the Zero-Error List-Decoding Capacity of the q/(q - 1) Channel. - Siddharth Bhandari; Jaikumar Radhakrishnan (IEEE Trans. Inf. Theory, 2022)