Jaikumar Radhakrishnan

136 papers A* 30A 12B 8C 2Misc 1Journal 67Unranked 14
YearRankTypeTitle / Venue / Authors
2026 A conf
Optimal Two-Round Communication Lower Bound for Graph Connectivity via Pointer Chasing.
ITCS
Jaikumar Radhakrishnan, Chaitanya Reddy, Rakesh Venkat
2023 A* conf
Randomized versus Deterministic Decision Tree Size.
STOC
Arkadev Chattopadhyay, Yogesh Dahiya, Nikhil S. Mande, Jaikumar Radhakrishnan, Swagato Sanyal
2022 J jnl
Bounds on the Zero-Error List-Decoding Capacity of the q/(q - 1) Channel.
IEEE Trans. Inf. Theory
Siddharth Bhandari, Jaikumar Radhakrishnan
2022 J jnl
Randomized versus Deterministic Decision Tree Size.
Electron. Colloquium Comput. Complex.
Arkadev Chattopadhyay, Yogesh Dahiya, Nikhil S. Mande, Jaikumar Radhakrishnan, Swagato Sanyal
2022 A* conf
Set Membership with Two Classical and Quantum Bit Probes.
ICALP
Shyam Dhamapurkar, Shubham Vivek Pawar, Jaikumar Radhakrishnan
2021 J jnl
Generalized Parametric Path Problems.
CoRR
Prerona Chatterjee, Kshitij Gajjar, Jaikumar Radhakrishnan, Girish Varma
2021 A conf
Generalized parametric path problems.
UAI
Kshitij Gajjar, Girish Varma, Prerona Chatterjee, Jaikumar Radhakrishnan
2021 — conf
Property B: Two-Coloring Non-Uniform Hypergraphs.
FSTTCS
Jaikumar Radhakrishnan, Aravind Srinivasan
2021 J jnl
Set membership with two classical and quantum bit probes.
CoRR
Shyam Dhamapurkar, Shubham Vivek Pawar, Jaikumar Radhakrishnan
2020 J jnl
An Improved Bound on the Zero-Error List-Decoding Capacity of the 4/3 Channel.
IEEE Trans. Inf. Theory
Marco Dalai, Venkatesan Guruswami, Jaikumar Radhakrishnan
2020 B conf
Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes.
MFCS
Palash Dey, Jaikumar Radhakrishnan, Santhoshini Velusamy
2019 Misc conf
Minimizing Branching Vertices in Distance-Preserving Subgraphs.
CSR
Kshitij Gajjar, Jaikumar Radhakrishnan
2019 A* conf
Parametric Shortest Paths in Planar Graphs.
FOCS
Kshitij Gajjar, Jaikumar Radhakrishnan
2018 B conf
Bounds on the Zero-Error List-Decoding Capacity of the q/(q-1) Channel.
ISIT
Siddharth Bhandari, Jaikumar Radhakrishnan
2018 J jnl
Bounds on the Zero-Error List-Decoding Capacity of the q/(q-1) Channel.
CoRR
Siddharth Bhandari, Jaikumar Radhakrishnan
2018 J jnl
Minimizing Branching Vertices in Distance-preserving Subgraphs.
CoRR
Kshitij Gajjar, Jaikumar Radhakrishnan
2018 J jnl
Parametric Shortest Paths in Planar Graphs.
CoRR
Kshitij Gajjar, Jaikumar Radhakrishnan
2018 J jnl
Parametric Shortest Paths in Planar Graphs.
Electron. Colloquium Comput. Complex.
Kshitij Gajjar, Jaikumar Radhakrishnan
2018 J jnl
Separation Between Deterministic and Randomized Query Complexity.
SIAM J. Comput.
Sagnik Mukhopadhyay, Jaikumar Radhakrishnan, Swagato Sanyal
2017 B conf
An improved bound on the zero-error list-decoding capacity of the 4/3 channel.
ISIT
Marco Dalai, Venkatesan Guruswami, Jaikumar Radhakrishnan
2017 A conf
Distance-Preserving Subgraphs of Interval Graphs.
ESA
Kshitij Gajjar, Jaikumar Radhakrishnan
2017 J jnl
Distance-preserving Subgraphs of Interval Graphs.
CoRR
Kshitij Gajjar, Jaikumar Radhakrishnan
2017 A conf
Set Membership with Non-Adaptive Bit Probes.
STACS
Mohit Garg, Jaikumar Radhakrishnan
2016 A conf
Coordination Complexity: Small Information Coordinating Large Populations.
ITCS
Rachel Cummings, Katrina Ligett, Jaikumar Radhakrishnan, Aaron Roth, Zhiwei Steven Wu
2016 J jnl
One-Shot Marton Inner Bound for Classical-Quantum Broadcast Channel.
IEEE Trans. Inf. Theory
Jaikumar Radhakrishnan, Pranab Sen, Naqueeb Ahmad Warsi
2016 A* conf
Partition Bound Is Quadratically Tight for Product Distributions.
ICALP
Prahladh Harsha, Rahul Jain, Jaikumar Radhakrishnan
2016 J jnl
Set membership with non-adaptive bit probes.
CoRR
Mohit Garg, Jaikumar Radhakrishnan
2016 — conf
The Zero-Error Randomized Query Complexity of the Pointer Function.
FSTTCS
Jaikumar Radhakrishnan, Swagato Sanyal
2016 J jnl
The zero-error randomized query complexity of the pointer function.
CoRR
Jaikumar Radhakrishnan, Swagato Sanyal
2016 J jnl
The zero-error randomized query complexity of the pointer function.
Electron. Colloquium Comput. Complex.
Jaikumar Radhakrishnan, Swagato Sanyal
2016 A conf
Tight Bounds for Communication-Assisted Agreement Distillation.
CCC
Venkatesan Guruswami, Jaikumar Radhakrishnan
2016 J jnl
Tight bounds for communication assisted agreement distillation.
Electron. Colloquium Comput. Complex.
Venkatesan Guruswami, Jaikumar Radhakrishnan
2015 J jnl
A Sampling Technique of Proving Lower Bounds for Noisy Computations.
CoRR
Chinmoy Dutta, Jaikumar Radhakrishnan
2015 J jnl
Coordination Complexity: Small Information Coordinating Large Populations.
CoRR
Rachel Cummings, Katrina Ligett, Jaikumar Radhakrishnan, Aaron Roth, Zhiwei Steven Wu
2015 J jnl
How Hard is Computing Parity with Noisy Communications?
CoRR
Chinmoy Dutta, Yashodhan Kanoria, D. Manjunath, Jaikumar Radhakrishnan
2015 J jnl
Hypergraph Two-Coloring in the Streaming Model.
CoRR
Jaikumar Radhakrishnan, Saswata Shannigrahi, Rakesh Venkat
2015 J jnl
Relaxed partition bound is quadratically tight for product distributions.
CoRR
Prahladh Harsha, Rahul Jain, Jaikumar Radhakrishnan
2015 J jnl
Relaxed partition bound is quadratically tight for product distributions.
Electron. Colloquium Comput. Complex.
Prahladh Harsha, Rahul Jain, Jaikumar Radhakrishnan
2015 J jnl
Set Membership with a Few Bit Probes.
CoRR
Mohit Garg, Jaikumar Radhakrishnan
2015 A* conf
Set membership with a few bit probes.
SODA
Mohit Garg, Jaikumar Radhakrishnan
2014 J jnl
One-shot Marton inner bound for classical-quantum broadcast channel.
CoRR
Jaikumar Radhakrishnan, Pranab Sen, Naqueeb Warsi
2014 A* conf
Topology Matters in Communication.
FOCS
Arkadev Chattopadhyay, Jaikumar Radhakrishnan, Atri Rudra
2014 J jnl
Topology matters in communication.
Electron. Colloquium Comput. Complex.
Arkadev Chattopadhyay, Jaikumar Radhakrishnan, Atri Rudra
2013 J jnl
Streaming algorithms for language recognition problems.
Theor. Comput. Sci.
Ajesh Babu, Nutan Limaye, Jaikumar Radhakrishnan, Girish Varma
2012 J jnl
Expansion properties of (secure) wireless networks.
ACM Trans. Algorithms
Alessandro Panconesi, Jaikumar Radhakrishnan
2012 — ed.
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2012, Hyderabad, India, December 15-17, 2012
FSTTCS
Deepak D'Souza, Telikepalli Kavitha, Jaikumar Radhakrishnan
2012 J jnl
More on a Problem of Zarankiewicz
CoRR
Chinmoy Dutta, Jaikumar Radhakrishnan
2012 B conf
More on a Problem of Zarankiewicz.
ISAAC
Chinmoy Dutta, Jaikumar Radhakrishnan
2012 J jnl
Online Set Packing.
SIAM J. Comput.
Yuval Emek, Magnús M. Halldórsson, Yishay Mansour, Boaz Patt-Shamir, Jaikumar Radhakrishnan, Dror Rawitz
2012 A* conf
Split and Join: Strong Partitions and Universal Steiner Trees for Graphs.
FOCS
Costas Busch, Chinmoy Dutta, Jaikumar Radhakrishnan, Rajmohan Rajaraman, Srinivasagopalan Srivathsan
2011 J jnl
Split and Join: Strong Partitions and Universal Steiner Trees for Graphs
CoRR
Costas Busch, Chinmoy Dutta, Jaikumar Radhakrishnan, Rajmohan Rajaraman, Srinivasagopalan Srivathsan
2011 B conf
Streaming Algorithms for 2-Coloring Uniform Hypergraphs.
WADS
Jaikumar Radhakrishnan, Saswata Shannigrahi
2011 J jnl
Streaming algorithms for language recognition problems
CoRR
Ajesh Babu, Nutan Limaye, Jaikumar Radhakrishnan, Girish Varma
2010 J jnl
An entropy based proof of the Moore bound for irregular graphs
CoRR
Ajesh Babu, Jaikumar Radhakrishnan
2010 — conf
Data Structures for Storing Small Sets in the Bitprobe Model.
ESA (2)
Jaikumar Radhakrishnan, Smit Shah, Saswata Shannigrahi
2010 A* conf
Online set packing and competitive scheduling of multi-part tasks.
PODC
Yuval Emek, Magnús M. Halldórsson, Yishay Mansour, Boaz Patt-Shamir, Jaikumar Radhakrishnan, Dror Rawitz
2010 J jnl
Subspace polynomials and limits to list decoding of Reed-Solomon codes.
IEEE Trans. Inf. Theory
Eli Ben-Sasson, Swastik Kopparty, Jaikumar Radhakrishnan
2010 J jnl
The communication complexity of correlation.
IEEE Trans. Inf. Theory
Prahladh Harsha, Rahul Jain, David A. McAllester, Jaikumar Radhakrishnan
2009 J jnl
A property of quantum relative entropy with an application to privacy in quantum communication.
J. ACM
Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen
2009 A* conf
Finding duplicates in a data stream.
SODA
Parikshit Gopalan, Jaikumar Radhakrishnan
2009 J jnl
Random Measurement Bases, Quantum State Distinction and Applications to the Hidden Subgroup Problem.
Algorithmica
Jaikumar Radhakrishnan, Martin Rötteler, Pranab Sen
2008 A* conf
A tight lower bound for parity in noisy communication networks.
SODA
Chinmoy Dutta, Yashodhan Kanoria, D. Manjunath, Jaikumar Radhakrishnan
2008 A* conf
Lower Bounds for Noisy Wireless Networks using Sampling Algorithms.
FOCS
Chinmoy Dutta, Jaikumar Radhakrishnan
2008 A* conf
Minimizing average latency in oblivious routing.
SODA
Prahladh Harsha, Thomas P. Hayes, Hariharan Narayanan, Harald Räcke, Jaikumar Radhakrishnan
2008 J jnl
Optimal Direct Sum and Privacy Trade-off Results for Quantum and Classical Communication Complexity
CoRR
Rahul Jain, Pranab Sen, Jaikumar Radhakrishnan
2008 J jnl
Redoubtable Sensor Networks.
ACM Trans. Inf. Syst. Secur.
Roberto Di Pietro, Luigi V. Mancini, Alessandro Mei, Alessandro Panconesi, Jaikumar Radhakrishnan
2008 C conf
Unassailable sensor networks.
SecureComm
Alessandro Mei, Alessandro Panconesi, Jaikumar Radhakrishnan
2007 J jnl
Complete partitions of graphs.
Comb.
Magnús M. Halldórsson, Guy Kortsarz, Jaikumar Radhakrishnan, Sivaramakrishnan Sivasubramanian
2007 A conf
The Communication Complexity of Correlation.
CCC
Prahladh Harsha, Rahul Jain, David A. McAllester, Jaikumar Radhakrishnan
2006 — conf
Gap Amplification in PCPs Using Lazy Random Walks.
ICALP (1)
Jaikumar Radhakrishnan
2006 C conf
Sensor Networks that Are Provably Resilient.
SecureComm
Roberto Di Pietro, Luigi V. Mancini, Alessandro Mei, Alessandro Panconesi, Jaikumar Radhakrishnan
2006 A* conf
Subspace Polynomials and List Decoding of Reed-Solomon Codes.
FOCS
Eli Ben-Sasson, Swastik Kopparty, Jaikumar Radhakrishnan
2006 J jnl
The communication complexity of correlation.
Electron. Colloquium Comput. Complex.
Prahladh Harsha, Rahul Jain, David A. McAllester, Jaikumar Radhakrishnan
2006 A conf
Tradeoffs in Depth-Two Superconcentrators.
STACS
Chinmoy Dutta, Jaikumar Radhakrishnan
2006 — conf
Zero Error List-Decoding Capacity of the
FSTTCS
Sourav Chakraborty, Jaikumar Radhakrishnan, Nandakumar Raghunathan, Prashant Sasatte
2005 — conf
Bounds for Error Reduction with Few Quantum Queries.
APPROX-RANDOM
Sourav Chakraborty, Jaikumar Radhakrishnan, Nandakumar Raghunathan
2005 A* conf
Complete partitions of graphs.
SODA
Guy Kortsarz, Jaikumar Radhakrishnan, Sivaramakrishnan Sivasubramanian
2005 J jnl
Essential covers of the cube by hyperplanes.
J. Comb. Theory A
Nathan Linial, Jaikumar Radhakrishnan
2005 J jnl
Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons.
J. Comput. Syst. Sci.
Devdatt P. Dubhashi, Alessandro Mei, Alessandro Panconesi, Jaikumar Radhakrishnan, Aravind Srinivasan
2005 B conf
Is partial quantum search of a database any easier?
SPAA
Lov K. Grover, Jaikumar Radhakrishnan
2005 J jnl
Lower bounds for adaptive locally decodable codes.
Random Struct. Algorithms
Amit Deshpande, Rahul Jain, Telikepalli Kavitha, Satyanarayana V. Lokam, Jaikumar Radhakrishnan
2005 J jnl
On converting CNF to DNF.
Theor. Comput. Sci.
Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener
2005 A* conf
On the Power of Random Bases in Fourier Sampling: Hidden Subgroup Problem in the Heisenberg Group.
ICALP
Jaikumar Radhakrishnan, Martin Rötteler, Pranab Sen
2005 A conf
Prior Entanglement, Message Compression and Privacy in Quantum Communication.
CCC
Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen
2004 — conf
Connectivity properties of secure wireless sensor networks.
SASN
Roberto Di Pietro, Luigi V. Mancini, Alessandro Mei, Alessandro Panconesi, Jaikumar Radhakrishnan
2004 B conf
Expansion properties of (secure) wireless networks.
SPAA
Alessandro Panconesi, Jaikumar Radhakrishnan
2003 A* conf
A Direct Sum Theorem in Communication Complexity via Message Compression.
ICALP
Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen
2003 A* conf
A Lower Bound for the Bounded Round Quantum Communication Complexity of Set Disjointness.
FOCS
Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen
2003 J jnl
A direct sum theorem in communication complexity via message compression
CoRR
Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen
2003 J jnl
A note on scrambling permutations.
Random Struct. Algorithms
Jaikumar Radhakrishnan
2003 — ed.
FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 23rd Conference, Mumbai, India, December 15-17, 2003, Proceedings
FSTTCS
Paritosh K. Pandya, Jaikumar Radhakrishnan
2003 A* conf
Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons.
SODA
Devdatt P. Dubhashi, Alessandro Mei, Alessandro Panconesi, Jaikumar Radhakrishnan, Aravind Srinivasan
2003 J jnl
On Converting CNF to DNF
Electron. Colloquium Comput. Complex.
Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener
2003 B conf
On Converting CNF to DNF.
MFCS
Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener
2002 J jnl
Are Bitvectors Optimal?
SIAM J. Comput.
Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, Srinivasan Venkatesh
2002 A conf
Better Lower Bounds for Locally Decodable Codes.
CCC
Amit Deshpande, Rahul Jain, Telikepalli Kavitha, Jaikumar Radhakrishnan, Satyanarayana V. Lokam
2002 — conf
On the Hardness of Approximating Minimum Monopoly Problems.
FSTTCS
S. Mishra, Jaikumar Radhakrishnan, Sivaramakrishnan Sivasubramanian
2002 A* conf
Privacy and Interaction in Quantum Communication Complexity and a Theorem about the Relative Entropy of Quantum States.
FOCS
Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen
2002 — conf
The Quantum Communication Complexity of the Pointer Chasing Problem: The Bit Version.
FSTTCS
Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen
2002 J jnl
The Quantum Complexity of Set Membership.
Algorithmica
Jaikumar Radhakrishnan, Pranab Sen, Srinivasan Venkatesh
2001 J jnl
A tradeoff between search and update in dictionaries.
Inf. Process. Lett.
Jaikumar Radhakrishnan, Venkatesh Raman
2001 J jnl
Depth-3 Arithmetic Circuits for S^2_n(X) and Extensions of the Graham-Pollack Theorem
CoRR
Jaikumar Radhakrishnan, Pranab Sen, Sundar Vishwanathan
2001 A conf
Explicit Deterministic Constructions for Membership in the Bitprobe Model.
ESA
Jaikumar Radhakrishnan, Venkatesh Raman, S. Srinivasa Rao
2001 J jnl
The Communication Complexity of Pointer Chasing.
J. Comput. Syst. Sci.
Stephen Ponzio, Jaikumar Radhakrishnan, Srinivasan Venkatesh
2000 A* conf
Are bitvectors optimal?
STOC
Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, Srinivasan Venkatesh
2000 J jnl
Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators.
SIAM J. Discret. Math.
Jaikumar Radhakrishnan, Amnon Ta-Shma
2000 — conf
Depth-3 Arithmetic Circuits for S
FSTTCS
Jaikumar Radhakrishnan, Pranab Sen, Sundar Vishwanathan
2000 J jnl
Improved bounds and algorithms for hypergraph 2-coloring.
Random Struct. Algorithms
Jaikumar Radhakrishnan, Aravind Srinivasan
2000 J jnl
The Quantum Complexity of Set Membership
CoRR
Jaikumar Radhakrishnan, Pranab Sen, Srinivasan Venkatesh
2000 A* conf
The Quantum Complexity of Set Membership.
FOCS
Jaikumar Radhakrishnan, Pranab Sen, Srinivasan Venkatesh
1999 A conf
The Communication Complexity of Pointer Chasing Applications of Entropy and Sampling (Abstract).
CCC
Stephen Ponzio, Jaikumar Radhakrishnan, Srinivasan Venkatesh
1999 A* conf
The Communication Complexity of Pointer Chasing: Applications of Entropy and Sampling.
STOC
Stephen Ponzio, Jaikumar Radhakrishnan, Srinivasan Venkatesh
1998 A* conf
Improved Bounds and Algorithms for Hypergraph Two-Coloring.
FOCS
Jaikumar Radhakrishnan, Aravind Srinivasan
1998 A* conf
Robust Asynchronous Protocols Are Finite-State.
ICALP
Madhavan Mukund, K. Narayan Kumar, Jaikumar Radhakrishnan, Milind A. Sohoni
1998 — conf
Towards a Characterisation of Finite-State Message-Passing Systems.
ASIAN
Madhavan Mukund, K. Narayan Kumar, Jaikumar Radhakrishnan, Milind A. Sohoni
1997 J jnl
An Entropy Proof of Bregman's Theorem.
J. Comb. Theory A
Jaikumar Radhakrishnan
1997 J jnl
Better Lower Bounds for Monotone Threshold Formulas.
J. Comput. Syst. Sci.
Jaikumar Radhakrishnan
1997 J jnl
Greed is Good: Approximating Independent Sets in Sparse and Bounded-Degree Graphs.
Algorithmica
Magnús M. Halldórsson, Jaikumar Radhakrishnan
1997 J jnl
The Complexity of Parallel Prefix Problems on Small Domains.
Inf. Comput.
Shiva Chaudhuri, Jaikumar Radhakrishnan
1997 A* conf
Tight Bounds for Depth-two Superconcentrators.
FOCS
Jaikumar Radhakrishnan, Amnon Ta-Shma
1996 J jnl
Deterministic Restrictions in Circuit Complexity
Electron. Colloquium Comput. Complex.
Shiva Chaudhuri, Jaikumar Radhakrishnan
1996 A* conf
Deterministic Restrictions in Circuit Complexity.
STOC
Shiva Chaudhuri, Jaikumar Radhakrishnan
1996 J jnl
Pi-Sigma-Pi Threshold Formulas.
Math. Syst. Theory
Jaikumar Radhakrishnan
1996 — conf
The Randomized Complexity of Maintaining the Minimum.
SWAT
Gerth Stølting Brodal, Shiva Chaudhuri, Jaikumar Radhakrishnan
1996 J jnl
The Randomized Complexity of Maintaining the Minimum.
Nord. J. Comput.
Gerth Stølting Brodal, Shiva Chaudhuri, Jaikumar Radhakrishnan
1995 J jnl
On the Number of Negations Needed to Compute Parity Functions.
IEICE Trans. Inf. Syst.
Tetsuro Nishino, Jaikumar Radhakrishnan
1994 J jnl
Directed Monotone Contact Networks for Threshold Functions.
Inf. Process. Lett.
Jaikumar Radhakrishnan, K. V. Subrahmanyam
1994 A* conf
Greed is good: approximating independent sets in sparse and bounded-degree graphs.
STOC
Magnús M. Halldórsson, Jaikumar Radhakrishnan
1994 J jnl
Improved Approximations of Independent Sets in Bounded-Degree Graphs via Subgraph Removal.
Nord. J. Comput.
Magnús M. Halldórsson, Jaikumar Radhakrishnan
1994 — conf
Improved Approximations of Independent Sets in Bounded-Degree Graphs.
SWAT
Magnús M. Halldórsson, Jaikumar Radhakrishnan
1994 J jnl
Sigma Pi Sigma Threshold Formulas.
Comb.
Jaikumar Radhakrishnan
1993 A* conf
Directed vs. Undirected Monotone Contact Networks for Threshold Functions
FOCS
Magnús M. Halldórsson, Jaikumar Radhakrishnan, K. V. Subrahmanyam
1993 — conf
On Some Communication Complexity Problems Related to THreshold Functions.
FSTTCS
Magnús M. Halldórsson, Jaikumar Radhakrishnan, K. V. Subrahmanyam
1992 J jnl
Improved Bounds for Covering Complete Uniform Hypergraphs.
Inf. Process. Lett.
Jaikumar Radhakrishnan
1992 A* conf
The Complexity of Parallel Prefix Problems on Small Domains
FOCS
Shiva Chaudhuri, Jaikumar Radhakrishnan
1991 A* conf
Better Bounds for Threshold Formulas
FOCS
Jaikumar Radhakrishnan