Jaikumar Radhakrishnan

According to our database, Jaikumar Radhakrishnan authored at least 98 papers between 1991 and 2022.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2022

Bounds on the Zero-Error List-Decoding Capacity of the q/(q - 1) Channel.

Siddharth Bhandari, Jaikumar Radhakrishnan

IEEE Trans. Inf. Theory, 2022

Randomized versus Deterministic Decision Tree Size.

Arkadev Chattopadhyay, Yogesh Dahiya, Nikhil S. Mande, Jaikumar Radhakrishnan, Swagato Sanyal

Electron. Colloquium Comput. Complex., 2022

Set Membership with Two Classical and Quantum Bit Probes.

Shyam Dhamapurkar, Shubham Vivek Pawar, Jaikumar Radhakrishnan

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

2021

Generalized parametric path problems.

Kshitij Gajjar, Girish Varma, Prerona Chatterjee, Jaikumar Radhakrishnan

Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, 2021

Property B: Two-Coloring Non-Uniform Hypergraphs.

Jaikumar Radhakrishnan, Aravind Srinivasan

Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2021

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

Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes.

Palash Dey, Jaikumar Radhakrishnan, Santhoshini Velusamy

Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

2019

Minimizing Branching Vertices in Distance-Preserving Subgraphs.

Kshitij Gajjar, Jaikumar Radhakrishnan

Proceedings of the Computer Science - Theory and Applications, 2019

2018

Separation Between Deterministic and Randomized Query Complexity.

Sagnik Mukhopadhyay, Jaikumar Radhakrishnan, Swagato Sanyal

SIAM J. Comput., 2018

Parametric Shortest Paths in Planar Graphs.

Kshitij Gajjar, Jaikumar Radhakrishnan

Electron. Colloquium Comput. Complex., 2018

2017

Set Membership with Non-Adaptive Bit Probes.

Mohit Garg, Jaikumar Radhakrishnan

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

Distance-Preserving Subgraphs of Interval Graphs.

Kshitij Gajjar, Jaikumar Radhakrishnan

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

2016

One-Shot Marton Inner Bound for Classical-Quantum Broadcast Channel.

Jaikumar Radhakrishnan, Pranab Sen, Naqueeb Ahmad Warsi

IEEE Trans. Inf. Theory, 2016

The zero-error randomized query complexity of the pointer function.

Jaikumar Radhakrishnan, Swagato Sanyal

Electron. Colloquium Comput. Complex., 2016

Tight bounds for communication assisted agreement distillation.

Venkatesan Guruswami, Jaikumar Radhakrishnan

Electron. Colloquium Comput. Complex., 2016

Coordination Complexity: Small Information Coordinating Large Populations.

Rachel Cummings, Katrina Ligett, Jaikumar Radhakrishnan, Aaron Roth, Zhiwei Steven Wu

Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

Partition Bound Is Quadratically Tight for Product Distributions.

Prahladh Harsha, Rahul Jain, Jaikumar Radhakrishnan

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

Relaxed partition bound is quadratically tight for product distributions.

Prahladh Harsha, Rahul Jain, Jaikumar Radhakrishnan

Electron. Colloquium Comput. Complex., 2015

Hypergraph Two-Coloring in the Streaming Model.

Jaikumar Radhakrishnan, Saswata Shannigrahi, Rakesh Venkat

CoRR, 2015

A Sampling Technique of Proving Lower Bounds for Noisy Computations.

Chinmoy Dutta, Jaikumar Radhakrishnan

CoRR, 2015

How Hard is Computing Parity with Noisy Communications?

Chinmoy Dutta, Yashodhan Kanoria, D. Manjunath, Jaikumar Radhakrishnan

CoRR, 2015

Set membership with a few bit probes.

Mohit Garg, Jaikumar Radhakrishnan

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014

Topology matters in communication.

Arkadev Chattopadhyay, Jaikumar Radhakrishnan, Atri Rudra

Electron. Colloquium Comput. Complex., 2014

One-shot Marton inner bound for classical-quantum broadcast channel.

Jaikumar Radhakrishnan, Pranab Sen, Naqueeb Warsi

CoRR, 2014

2013

Streaming algorithms for language recognition problems.

Ajesh Babu, Nutan Limaye, Jaikumar Radhakrishnan, Girish Varma

Theor. Comput. Sci., 2013

2012

Expansion properties of (secure) wireless networks.

Alessandro Panconesi, Jaikumar Radhakrishnan

ACM Trans. Algorithms, 2012

Online Set Packing.

Yuval Emek, Magnús M. Halldórsson, Yishay Mansour, Boaz Patt-Shamir, Jaikumar Radhakrishnan, Dror Rawitz

SIAM J. Comput., 2012

More on a Problem of Zarankiewicz.

Chinmoy Dutta, Jaikumar Radhakrishnan

Proceedings of the Algorithms and Computation - 23rd International Symposium, 2012

Split and Join: Strong Partitions and Universal Steiner Trees for Graphs.

Costas Busch, Chinmoy Dutta, Jaikumar Radhakrishnan, Rajmohan Rajaraman, Srinivasagopalan Srivathsan

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011

Streaming Algorithms for 2-Coloring Uniform Hypergraphs.

Jaikumar Radhakrishnan, Saswata Shannigrahi

Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

2010

Subspace polynomials and limits to list decoding of Reed-Solomon codes.

Eli Ben-Sasson, Swastik Kopparty, Jaikumar Radhakrishnan

IEEE Trans. Inf. Theory, 2010

An entropy based proof of the Moore bound for irregular graphs

Ajesh Babu, Jaikumar Radhakrishnan

CoRR, 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

Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, 2010

Data Structures for Storing Small Sets in the Bitprobe Model.

Jaikumar Radhakrishnan, Smit Shah, Saswata Shannigrahi

Proceedings of the Algorithms, 2010

2009

A property of quantum relative entropy with an application to privacy in quantum communication.

Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen

J. ACM, 2009

Random Measurement Bases, Quantum State Distinction and Applications to the Hidden Subgroup Problem.

Jaikumar Radhakrishnan, Martin Rötteler, Pranab Sen

Algorithmica, 2009

Finding duplicates in a data stream.

Parikshit Gopalan, Jaikumar Radhakrishnan

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2008

Redoubtable Sensor Networks.

Roberto Di Pietro, Luigi V. Mancini, Alessandro Mei, Alessandro Panconesi, Jaikumar Radhakrishnan

ACM Trans. Inf. Syst. Secur., 2008

Optimal Direct Sum and Privacy Trade-off Results for Quantum and Classical Communication Complexity

Rahul Jain, Pranab Sen, Jaikumar Radhakrishnan

CoRR, 2008

Minimizing average latency in oblivious routing.

Prahladh Harsha, Thomas P. Hayes, Hariharan Narayanan, Harald Räcke, Jaikumar Radhakrishnan

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

A tight lower bound for parity in noisy communication networks.

Chinmoy Dutta, Yashodhan Kanoria, D. Manjunath, Jaikumar Radhakrishnan

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Unassailable sensor networks.

Alessandro Mei, Alessandro Panconesi, Jaikumar Radhakrishnan

Proceedings of the 4th International ICST Conference on Security and Privacy in Communication Networks, 2008

Lower Bounds for Noisy Wireless Networks using Sampling Algorithms.

Chinmoy Dutta, Jaikumar Radhakrishnan

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

Complete partitions of graphs.

Magnús M. Halldórsson, Guy Kortsarz, Jaikumar Radhakrishnan, Sivaramakrishnan Sivasubramanian

Comb., 2007

2006

The communication complexity of correlation.

Prahladh Harsha, Rahul Jain, David A. McAllester, Jaikumar Radhakrishnan

Electron. Colloquium Comput. Complex., 2006

Tradeoffs in Depth-Two Superconcentrators.

Chinmoy Dutta, Jaikumar Radhakrishnan

Proceedings of the STACS 2006, 2006

Sensor Networks that Are Provably Resilient.

Roberto Di Pietro, Luigi V. Mancini, Alessandro Mei, Alessandro Panconesi, Jaikumar Radhakrishnan

Proceedings of the Second International Conference on Security and Privacy in Communication Networks and the Workshops, 2006

Gap Amplification in PCPs Using Lazy Random Walks.

Jaikumar Radhakrishnan

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

Zero Error List-Decoding Capacity of the <i>q</i>/(<i>q</i>-1) Channel.

Sourav Chakraborty, Jaikumar Radhakrishnan, Nandakumar Raghunathan, Prashant Sasatte

Proceedings of the FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science, 2006

Subspace Polynomials and List Decoding of Reed-Solomon Codes.

Eli Ben-Sasson, Swastik Kopparty, Jaikumar Radhakrishnan

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005

On converting CNF to DNF.

Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener

Theor. Comput. Sci., 2005

Lower bounds for adaptive locally decodable codes.

Amit Deshpande, Rahul Jain, Telikepalli Kavitha, Satyanarayana V. Lokam, Jaikumar Radhakrishnan

Random Struct. Algorithms, 2005

Essential covers of the cube by hyperplanes.

Nathan Linial, Jaikumar Radhakrishnan

J. Comb. Theory A, 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

Is partial quantum search of a database any easier?

Lov K. Grover, Jaikumar Radhakrishnan

Proceedings of the SPAA 2005: Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2005

Complete partitions of graphs.

Guy Kortsarz, Jaikumar Radhakrishnan, Sivaramakrishnan Sivasubramanian

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

On the Power of Random Bases in Fourier Sampling: Hidden Subgroup Problem in the Heisenberg Group.

Jaikumar Radhakrishnan, Martin Rötteler, Pranab Sen

Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

Prior Entanglement, Message Compression and Privacy in Quantum Communication.

Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

Bounds for Error Reduction with Few Quantum Queries.

Sourav Chakraborty, Jaikumar Radhakrishnan, Nandakumar Raghunathan

Proceedings of the Approximation, 2005

2004

Connectivity properties of secure wireless sensor networks.

Roberto Di Pietro, Luigi V. Mancini, Alessandro Mei, Alessandro Panconesi, Jaikumar Radhakrishnan

Proceedings of the 2nd ACM Workshop on Security of ad hoc and Sensor Networks, 2004

2003

A note on scrambling permutations.

Jaikumar Radhakrishnan

Random Struct. Algorithms, 2003

A Direct Sum Theorem in Communication Complexity via Message Compression.

Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen

Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

A Lower Bound for the Bounded Round Quantum Communication Complexity of Set Disjointness.

Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2002

Are Bitvectors Optimal?

Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, Srinivasan Venkatesh

SIAM J. Comput., 2002

The Quantum Complexity of Set Membership.

Jaikumar Radhakrishnan, Pranab Sen, Srinivasan Venkatesh

Algorithmica, 2002

On the Hardness of Approximating Minimum Monopoly Problems.

S. Mishra, Jaikumar Radhakrishnan, Sivaramakrishnan Sivasubramanian

Proceedings of the FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science, 2002

The Quantum Communication Complexity of the Pointer Chasing Problem: The Bit Version.

Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen

Proceedings of the FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science, 2002

Privacy and Interaction in Quantum Communication Complexity and a Theorem about the Relative Entropy of Quantum States.

Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen

Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Better Lower Bounds for Locally Decodable Codes.

Amit Deshpande, Rahul Jain, Telikepalli Kavitha, Jaikumar Radhakrishnan, Satyanarayana V. Lokam

Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001

The Communication Complexity of Pointer Chasing.

Stephen Ponzio, Jaikumar Radhakrishnan, Srinivasan Venkatesh

J. Comput. Syst. Sci., 2001

A tradeoff between search and update in dictionaries.

Jaikumar Radhakrishnan, Venkatesh Raman

Inf. Process. Lett., 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

Explicit Deterministic Constructions for Membership in the Bitprobe Model.

Jaikumar Radhakrishnan, Venkatesh Raman, S. Srinivasa Rao

Proceedings of the Algorithms, 2001

2000

Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators.

Jaikumar Radhakrishnan, Amnon Ta-Shma

SIAM J. Discret. Math., 2000

Improved bounds and algorithms for hypergraph 2-coloring.

Jaikumar Radhakrishnan, Aravind Srinivasan

Random Struct. Algorithms, 2000

Depth-3 Arithmetic Circuits for S_n²(X) and Extensions of the Graham-Pollack Theorem.

Jaikumar Radhakrishnan, Pranab Sen, Sundar Vishwanathan

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 2000

1999

The Communication Complexity of Pointer Chasing: Applications of Entropy and Sampling.

Stephen Ponzio, Jaikumar Radhakrishnan, Srinivasan Venkatesh

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

The Communication Complexity of Pointer Chasing Applications of Entropy and Sampling (Abstract).

Stephen Ponzio, Jaikumar Radhakrishnan, Srinivasan Venkatesh

Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998

Robust Asynchronous Protocols Are Finite-State.

Madhavan Mukund, K. Narayan Kumar, Jaikumar Radhakrishnan, Milind A. Sohoni

Proceedings of the Automata, Languages and Programming, 25th International Colloquium, 1998

Improved Bounds and Algorithms for Hypergraph Two-Coloring.

Jaikumar Radhakrishnan, Aravind Srinivasan

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Towards a Characterisation of Finite-State Message-Passing Systems.

Madhavan Mukund, K. Narayan Kumar, Jaikumar Radhakrishnan, Milind A. Sohoni

Proceedings of the Advances in Computing Science, 1998

1997

An Entropy Proof of Bregman's Theorem.

Jaikumar Radhakrishnan

J. Comb. Theory A, 1997

Better Lower Bounds for Monotone Threshold Formulas.

Jaikumar Radhakrishnan

J. Comput. Syst. Sci., 1997

The Complexity of Parallel Prefix Problems on Small Domains.

Shiva Chaudhuri, Jaikumar Radhakrishnan

Inf. Comput., 1997

Greed is Good: Approximating Independent Sets in Sparse and Bounded-Degree Graphs.

Magnús M. Halldórsson, Jaikumar Radhakrishnan

Algorithmica, 1997

Tight Bounds for Depth-two Superconcentrators.

Jaikumar Radhakrishnan, Amnon Ta-Shma

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1996

The Randomized Complexity of Maintaining the Minimum.

Gerth Stølting Brodal, Shiva Chaudhuri, Jaikumar Radhakrishnan

Nord. J. Comput., 1996

Pi-Sigma-Pi Threshold Formulas.

Jaikumar Radhakrishnan

Math. Syst. Theory, 1996

Deterministic Restrictions in Circuit Complexity

Shiva Chaudhuri, Jaikumar Radhakrishnan

Electron. Colloquium Comput. Complex., 1996

1995

On the Number of Negations Needed to Compute Parity Functions.

Tetsuro Nishino, Jaikumar Radhakrishnan

IEICE Trans. Inf. Syst., 1995

1994

Improved Approximations of Independent Sets in Bounded-Degree Graphs via Subgraph Removal.

Magnús M. Halldórsson, Jaikumar Radhakrishnan

Nord. J. Comput., 1994

Directed Monotone Contact Networks for Threshold Functions.

Jaikumar Radhakrishnan, K. V. Subrahmanyam

Inf. Process. Lett., 1994

Sigma Pi Sigma Threshold Formulas.

Jaikumar Radhakrishnan

Comb., 1994

Improved Approximations of Independent Sets in Bounded-Degree Graphs.

Magnús M. Halldórsson, Jaikumar Radhakrishnan

Proceedings of the Algorithm Theory, 1994

1993

On Some Communication Complexity Problems Related to THreshold Functions.

Magnús M. Halldórsson, Jaikumar Radhakrishnan, K. V. Subrahmanyam

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1993

Directed vs. Undirected Monotone Contact Networks for Threshold Functions

Magnús M. Halldórsson, Jaikumar Radhakrishnan, K. V. Subrahmanyam

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992

Improved Bounds for Covering Complete Uniform Hypergraphs.

Jaikumar Radhakrishnan

Inf. Process. Lett., 1992

1991

Better Bounds for Threshold Formulas

Jaikumar Radhakrishnan

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991