# Jaikumar Radhakrishnan

According to our database

Collaborative distances:

^{1}, Jaikumar Radhakrishnan authored at least 89 papers between 1991 and 2019.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### On csauthors.net:

## Bibliography

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.

Electronic Colloquium on Computational Complexity (ECCC), 2018

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

Proceedings of the 2018 IEEE International Symposium on Information Theory, 2018

2017

Set Membership with Non-Adaptive Bit Probes.

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

An improved bound on the zero-error list-decoding capacity of the 4/3 channel.

Proceedings of the 2017 IEEE International Symposium on Information Theory, 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. Information Theory, 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

The Zero-Error Randomized Query Complexity of the Pointer Function.

Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2016

Tight Bounds for Communication-Assisted Agreement Distillation.

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

Relaxed partition bound is quadratically tight for product distributions.

Electronic Colloquium on Computational Complexity (ECCC), 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.

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

Streaming algorithms for language recognition problems.

Theor. Comput. Sci., 2013

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. Information Theory, 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

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.

Combinatorica, 2007

The Communication Complexity of Correlation.

Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007

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

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

Lower bounds for adaptive locally decodable codes.

Random Struct. Algorithms, 2005

Essential covers of the cube by hyperplanes.

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

Expansion properties of (secure) wireless networks.

Proceedings of the SPAA 2004: Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 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

On Converting CNF to DNF

Electronic Colloquium on Computational Complexity (ECCC), 2003

Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons.

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

On Converting CNF to DNF.

Proceedings of the Mathematical Foundations of Computer Science 2003, 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

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

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. Discrete Math., 2000

Improved bounds and algorithms for hypergraph 2-coloring.

Random Struct. Algorithms, 2000

Are bitvectors optimal?

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

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

The Quantum Complexity of Set Membership.

Proceedings of the 41st Annual Symposium on Foundations of 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, Ser. 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

Tight Bounds for Depth-two Superconcentrators.

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

1996

Pi-Sigma-Pi Threshold Formulas.

Mathematical Systems Theory, 1996

Deterministic Restrictions in Circuit Complexity

Electronic Colloquium on Computational Complexity (ECCC), 1996

The Randomized Complexity of Maintaining the Minimum.

Proceedings of the Algorithm Theory, 1996

Deterministic Restrictions in Circuit Complexity.

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

1995

On the Number of Negations Needed to Compute Parity Functions.

IEICE Transactions, 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.

Combinatorica, 1994

Improved Approximations of Independent Sets in Bounded-Degree Graphs.

Proceedings of the Algorithm Theory, 1994

Greed is good: approximating independent sets in sparse and bounded-degree graphs.

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 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

The Complexity of Parallel Prefix Problems on Small Domains

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1991

Better Bounds for Threshold Formulas

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