Jaikumar Radhakrishnan

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

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

On csauthors.net:

Bibliography

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

Randomized versus Deterministic Decision Tree Size.
Electron. Colloquium Comput. Complex., 2022

Set Membership with Two Classical and Quantum Bit Probes.
Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

2021
Generalized parametric path problems.
Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, 2021

Property B: Two-Coloring Non-Uniform Hypergraphs.
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.
IEEE Trans. Inf. Theory, 2020

Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes.
Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

2019
Minimizing Branching Vertices in Distance-Preserving Subgraphs.
Proceedings of the Computer Science - Theory and Applications, 2019

2018
Separation Between Deterministic and Randomized Query Complexity.
SIAM J. Comput., 2018

Parametric Shortest Paths in Planar Graphs.
Electron. Colloquium Comput. Complex., 2018

2017
Set Membership with Non-Adaptive Bit Probes.
Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

Distance-Preserving Subgraphs of Interval Graphs.
Proceedings of the 25th Annual European Symposium on Algorithms, 2017

2016
One-Shot Marton Inner Bound for Classical-Quantum Broadcast Channel.
IEEE Trans. Inf. Theory, 2016

The zero-error randomized query complexity of the pointer function.
Electron. Colloquium Comput. Complex., 2016

Tight bounds for communication assisted agreement distillation.
Electron. Colloquium Comput. Complex., 2016

Coordination Complexity: Small Information Coordinating Large Populations.
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

Partition Bound Is Quadratically Tight for Product Distributions.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015
Relaxed partition bound is quadratically tight for product distributions.
Electron. Colloquium Comput. Complex., 2015

Hypergraph Two-Coloring in the Streaming Model.
CoRR, 2015

A Sampling Technique of Proving Lower Bounds for Noisy Computations.
CoRR, 2015

How Hard is Computing Parity with Noisy Communications?
CoRR, 2015

Set membership with a few bit probes.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014
Topology matters in communication.
Electron. Colloquium Comput. Complex., 2014

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

2013
Streaming algorithms for language recognition problems.
Theor. Comput. Sci., 2013

2012
Expansion properties of (secure) wireless networks.
ACM Trans. Algorithms, 2012

Online Set Packing.
SIAM J. Comput., 2012

More on a Problem of Zarankiewicz.
Proceedings of the Algorithms and Computation - 23rd International Symposium, 2012

Split and Join: Strong Partitions and Universal Steiner Trees for Graphs.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011
Streaming Algorithms for 2-Coloring Uniform Hypergraphs.
Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

2010
Subspace polynomials and limits to list decoding of Reed-Solomon codes.
IEEE Trans. Inf. Theory, 2010

An entropy based proof of the Moore bound for irregular graphs
CoRR, 2010

Online set packing and competitive scheduling of multi-part tasks.
Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, 2010

Data Structures for Storing Small Sets in the Bitprobe Model.
Proceedings of the Algorithms, 2010

2009
A property of quantum relative entropy with an application to privacy in quantum communication.
J. ACM, 2009

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

Finding duplicates in a data stream.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2008
Redoubtable Sensor Networks.
ACM Trans. Inf. Syst. Secur., 2008

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

Minimizing average latency in oblivious routing.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

A tight lower bound for parity in noisy communication networks.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

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

Lower Bounds for Noisy Wireless Networks using Sampling Algorithms.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007
Complete partitions of graphs.
Comb., 2007

2006
The communication complexity of correlation.
Electron. Colloquium Comput. Complex., 2006

Tradeoffs in Depth-Two Superconcentrators.
Proceedings of the STACS 2006, 2006

Sensor Networks that Are Provably Resilient.
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.
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.
Proceedings of the FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science, 2006

Subspace Polynomials and List Decoding of Reed-Solomon Codes.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005
On converting CNF to DNF.
Theor. Comput. Sci., 2005

Lower bounds for adaptive locally decodable codes.
Random Struct. Algorithms, 2005

Essential covers of the cube by hyperplanes.
J. Comb. Theory A, 2005

Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons.
J. Comput. Syst. Sci., 2005

Is partial quantum search of a database any easier?
Proceedings of the SPAA 2005: Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2005

Complete partitions of graphs.
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.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

Prior Entanglement, Message Compression and Privacy in Quantum Communication.
Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

Bounds for Error Reduction with Few Quantum Queries.
Proceedings of the Approximation, 2005

2004
Connectivity properties of secure wireless sensor networks.
Proceedings of the 2nd ACM Workshop on Security of ad hoc and Sensor Networks, 2004

2003
A note on scrambling permutations.
Random Struct. Algorithms, 2003

A Direct Sum Theorem in Communication Complexity via Message Compression.
Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

A Lower Bound for the Bounded Round Quantum Communication Complexity of Set Disjointness.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2002
Are Bitvectors Optimal?
SIAM J. Comput., 2002

The Quantum Complexity of Set Membership.
Algorithmica, 2002

On the Hardness of Approximating Minimum Monopoly Problems.
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.
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.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Better Lower Bounds for Locally Decodable Codes.
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001
The Communication Complexity of Pointer Chasing.
J. Comput. Syst. Sci., 2001

A tradeoff between search and update in dictionaries.
Inf. Process. Lett., 2001

Depth-3 Arithmetic Circuits for S^2_n(X) and Extensions of the Graham-Pollack Theorem
CoRR, 2001

Explicit Deterministic Constructions for Membership in the Bitprobe Model.
Proceedings of the Algorithms, 2001

2000
Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators.
SIAM J. Discret. Math., 2000

Improved bounds and algorithms for hypergraph 2-coloring.
Random Struct. Algorithms, 2000

Depth-3 Arithmetic Circuits for S<sub>n</sub><sup>2</sup>(X) and Extensions of the Graham-Pollack Theorem.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 2000

1999
The Communication Complexity of Pointer Chasing: Applications of Entropy and Sampling.
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).
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998
Robust Asynchronous Protocols Are Finite-State.
Proceedings of the Automata, Languages and Programming, 25th International Colloquium, 1998

Improved Bounds and Algorithms for Hypergraph Two-Coloring.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Towards a Characterisation of Finite-State Message-Passing Systems.
Proceedings of the Advances in Computing Science, 1998

1997
An Entropy Proof of Bregman's Theorem.
J. Comb. Theory A, 1997

Better Lower Bounds for Monotone Threshold Formulas.
J. Comput. Syst. Sci., 1997

The Complexity of Parallel Prefix Problems on Small Domains.
Inf. Comput., 1997

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

Tight Bounds for Depth-two Superconcentrators.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1996
The Randomized Complexity of Maintaining the Minimum.
Nord. J. Comput., 1996

Pi-Sigma-Pi Threshold Formulas.
Math. Syst. Theory, 1996

Deterministic Restrictions in Circuit Complexity
Electron. Colloquium Comput. Complex., 1996

1995
On the Number of Negations Needed to Compute Parity Functions.
IEICE Trans. Inf. Syst., 1995

1994
Improved Approximations of Independent Sets in Bounded-Degree Graphs via Subgraph Removal.
Nord. J. Comput., 1994

Directed Monotone Contact Networks for Threshold Functions.
Inf. Process. Lett., 1994

Sigma Pi Sigma Threshold Formulas.
Comb., 1994

Improved Approximations of Independent Sets in Bounded-Degree Graphs.
Proceedings of the Algorithm Theory, 1994

1993
On Some Communication Complexity Problems Related to THreshold Functions.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1993

Directed vs. Undirected Monotone Contact Networks for Threshold Functions
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992
Improved Bounds for Covering Complete Uniform Hypergraphs.
Inf. Process. Lett., 1992

1991
Better Bounds for Threshold Formulas
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991


  Loading...