| 2005 |
|---|
| 52 |
pdf | Lov K. Grover, Jaikumar
Radhakrishnan: Is partial quantum search of a database any easier? To
appear in the proceedings of SPAA 2005, July 2005. |
| 51 | pdf | Jaikumar
Radhakrishnan, Martin Roetteler: On the Power of Random Bases in
Fourier Sampling: Hidden Subgroup Problem in the Heisenberg Group. To
appear in the proceedings of ICALP 2005, July 2005. |
| 51 | pdf | Rahul Jain,
Jaikumar Radhakrishnan, Pranab Sen: Prior entanglement, message
compression and privacy in quantum communication. To appear in the
proceedings of CCC 2005, June 2005. |
| 50 | pdf | Nathan Linial,
Jaikumar Radhakrishnan:
Essential covers of the cube by hyperplanes.
J. Comb. Theory, Ser. A 109(2): 331-338 (2005) |
| 2004 |
|---|
| 49 | pdf | Alessandro Panconesi,
Jaikumar Radhakrishnan:
Expansion properties of (secure) wireless networks.
SPAA 2004: 281-285 |
| 2003 |
|---|
| 48 | | Paritosh K. Pandya,
Jaikumar Radhakrishnan: FST TCS 2003: Foundations of Software
Technology and Theoretical Computer Science, 23rd Conference, Mumbai,
India, December 15-17, 2003, Proceedings Springer 2003 |
| 47 | pdf | Rahul
Jain, Jaikumar Radhakrishnan, Pranab
Sen: A Lower Bound for the Bounded Round Quantum Communication
Complexity of Set Disjointness. FOCS
2003: 220-229 |
| 46 | pdf | Rahul Jain,
Jaikumar Radhakrishnan,
Pranab Sen:
A Direct Sum Theorem in Communication Complexity via Message Compression.
ICALP 2003: 300-315 |
| 45 | pdf | Peter Bro Miltersen,
Jaikumar Radhakrishnan,
Ingo Wegener:
On Converting CNF to DNF.
MFCS 2003: 612-621 |
| 44 | pdf | Devdatt P. Dubhashi,
Alessandro Mei,
Alessandro Panconesi,
Jaikumar Radhakrishnan,
Aravind Srinivasan:
Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons.
SODA 2003: 717-724 |
| 43 | pdf | Rahul Jain,
Jaikumar Radhakrishnan,
Pranab Sen:
A direct sum theorem in communication complexity via message compression
CoRR cs.CC/0304020: (2003) |
| 42 | pdf | Peter Bro Miltersen,
Jaikumar Radhakrishnan,
Ingo Wegener:
On Converting CNF to DNF
Electronic Colloquium on Computational Complexity (ECCC) 10(017): (2003) |
| 41 | pdf | Jaikumar Radhakrishnan:
A note on scrambling permutations.
Random Struct. Algorithms 22(4): 435-439 (2003) |
| 2002 |
|---|
| 40 | pdf | Rahul
Jain, Jaikumar Radhakrishnan, Pranab
Sen: Privacy and Interaction in Quantum Communication Complexity
and a Theorem about the Relative Entropy of Quantum States. FOCS
2002: 429-438 |
| 39 | ps | Rahul
Jain, Jaikumar Radhakrishnan, Pranab
Sen: The Quantum Communication Complexity of the Pointer Chasing
Problem: The Bit Version. FSTTCS
2002: 218-229 |
| 38 | pdf | S. Mishra,
Jaikumar Radhakrishnan,
S. Sivasubramanian:
On the Hardness of Approximating Minimum Monopoly Problems.
FSTTCS 2002: 277-288 |
| 37 | pdf | Amit Deshpande,
Rahul Jain,
T. Kavitha,
Jaikumar Radhakrishnan,
Satyanarayana V. Lokam:
Better Lower Bounds for Locally Decodable Codes.
IEEE Conference on Computational Complexity 2002: 184-193 |
| 36 | ps | Jaikumar Radhakrishnan,
Pranab Sen,
S. Venkatesh:
The Quantum Complexity of Set Membership.
Algorithmica 34(4): 462-479 (2002) |
| 35 | ps | Harry
Buhrman, Peter
Bro Miltersen, Jaikumar Radhakrishnan, S. Venkatesh:
Are Bitvectors Optimal? SIAM
J. Comput. 31(6): 1723-1744 (2002) |
| 2001 |
|---|
| 34 | pdf | Jaikumar Radhakrishnan,
Venkatesh Raman,
S. Srinivasa Rao:
Explicit Deterministic Constructions for Membership in the Bitprobe Model.
ESA 2001: 290-299 |
| 33 | pdf | Jaikumar Radhakrishnan,
Pranab Sen,
Sundar Vishwanathan:
Depth-3 Arithmetic Circuits for S^2_n(X) and Extensions of the Graham-Pollack Theorem
CoRR cs.DM/0110031: (2001) |
| 32 | pdf | Jaikumar Radhakrishnan,
Venkatesh Raman:
A tradeoff between search and update in dictionaries.
Inf. Process. Lett. 80(5): 243-247 (2001) |
| 31 | ps |
Stephen
Ponzio, Jaikumar Radhakrishnan, S. Venkatesh:
The Communication Complexity of Pointer Chasing. J. Comput. Syst. Sci. 62(2):
323-355 (2001) |
| 2000 |
|---|
| 30 | | Jaikumar Radhakrishnan,
Pranab Sen,
S. Venkatesh:
The Quantum Complexity of Set Membership.
FOCS 2000: 554-562 |
| 29 | pdf | Jaikumar Radhakrishnan,
Pranab Sen,
Sundar Vishwanathan:
Depth-3 Arithmetic Circuits for Sn2(X) and Extensions of the Graham-Pollack Theorem.
FSTTCS 2000: 176-187 |
| 28 | ps | Harry
Buhrman, Peter
Bro Miltersen, Jaikumar Radhakrishnan, S. Venkatesh:
Are bitvectors optimal? STOC
2000: 449-458 |
| 27 | pdf | Jaikumar Radhakrishnan,
Pranab Sen,
S. Venkatesh:
The Quantum Complexity of Set Membership
CoRR quant-ph/0007021: (2000) |
| 26 | | Jaikumar Radhakrishnan,
Aravind Srinivasan:
Improved bounds and algorithms for hypergraph 2-coloring.
Random Struct. Algorithms 16(1): 4-32 (2000) |
| 25 | pdf | Jaikumar Radhakrishnan,
Amnon Ta-Shma:
Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators.
SIAM J. Discrete Math. 13(1): 2-24 (2000) |
| 1999 |
|---|
| 24 | pdf | Stephen Ponzio,
Jaikumar Radhakrishnan,
S. Venkatesh:
The Communication Complexity of Pointer Chasing Applications of Entropy and Sampling (Abstract).
IEEE Conference on Computational Complexity 1999: 7 |
| 23 | pdf | Stephen Ponzio,
Jaikumar Radhakrishnan,
S. Venkatesh:
The Communication Complexity of Pointer Chasing: Applications of Entropy and Sampling.
STOC 1999: 602-611 |
| 1998 |
|---|
| 22 | pdf | Madhavan Mukund,
K. Narayan Kumar,
Jaikumar Radhakrishnan,
Milind A. Sohoni:
Towards a Characterisation of Finite-State Message-Passing Systems.
ASIAN 1998: 282-299 |
| 21 | pdf | Jaikumar Radhakrishnan,
Aravind Srinivasan:
Improved Bounds and Algorithms for Hypergraph Two-Coloring.
FOCS 1998: 684-693 |
| 20 | pdf | Madhavan Mukund,
K. Narayan Kumar,
Jaikumar Radhakrishnan,
Milind A. Sohoni:
Robust Asynchronous Protocols Are Finite-State.
ICALP 1998: 188-199 |
| 1997 |
|---|
| 19 | pdf | Jaikumar Radhakrishnan,
Amnon Ta-Shma:
Tight Bounds for Depth-two Superconcentrators.
FOCS 1997: 585-594 |
| 18 | | Magnús M. Halldórsson,
Jaikumar Radhakrishnan:
Greed is Good: Approximating Independent Sets in Sparse and Bounded-Degree Graphs.
Algorithmica 18(1): 145-163 (1997) |
| 17 | | Shiva Chaudhuri,
Jaikumar Radhakrishnan:
The Complexity of Parallel Prefix Problems on Small Domains.
Inf. Comput. 138(1): 1-22 (1997) |
| 16 | pdf | Jaikumar Radhakrishnan:
An Entropy Proof of Bregman's Theorem.
J. Comb. Theory, Ser. A 77(1): 161-164 (1997) |
| 15 | pdf | Jaikumar Radhakrishnan:
Better Lower Bounds for Monotone Threshold Formulas.
J. Comput. Syst. Sci. 54(2): 221-226 (1997) |
| 1996 |
|---|
| 14 |
pdf | Shiva
Chaudhuri, Jaikumar Radhakrishnan: Deterministic Restrictions in
Circuit Complexity. STOC
1996: 30-36 |
| 13 | | Gerth Stølting Brodal,
Shiva Chaudhuri,
Jaikumar Radhakrishnan:
The Randomized Complexity of Maintaining the Minimum.
SWAT 1996: 4-15 |
| 12 | pdf | Shiva Chaudhuri,
Jaikumar Radhakrishnan:
Deterministic Restrictions in Circuit Complexity
Electronic Colloquium on Computational Complexity (ECCC) 3(4): (1996) |
| 11 | | Jaikumar Radhakrishnan:
Pi-Sigma-Pi Threshold Formulas.
Mathematical Systems Theory 29(4): 357-374 (1996) |
| 1994 |
|---|
| 10 | pdf | Magnús M. Halldórsson,
Jaikumar Radhakrishnan:
Greed is good: approximating independent sets in sparse and bounded-degree graphs.
STOC 1994: 439-448 |
| 9 | | Magnús M. Halldórsson,
Jaikumar Radhakrishnan:
Improved Approximations of Independent Sets in Bounded-Degree Graphs.
SWAT 1994: 195-206 |
| 8 |
pdf | Jaikumar Radhakrishnan:
Sigma Pi Sigma Threshold Formulas.
Combinatorica 14(3): 345-374 (1994) |
| 7 |
pdf | Jaikumar Radhakrishnan,
K. V. Subrahmanyam:
Directed Monotone Contact Networks for Threshold Functions.
Inf. Process. Lett. 50(4): 199-203 (1994) |
| 6 | | Magnús M. Halldórsson,
Jaikumar Radhakrishnan:
Improved Approximations of Independent Sets in Bounded-Degree Graphs via Subgraph Removal.
Nord. J. Comput. 1(4): 475-492 (1994) |
| 1993 |
|---|
| 5 | pdf | Magnús
M. Halldórsson, Jaikumar Radhakrishnan, K. V. Subrahmanyam:
Directed vs. Undirected Monotone Contact Networks for Threshold
Functions FOCS
1993: 604-613 |
| 4 | | Magnús M. Halldórsson,
Jaikumar Radhakrishnan,
K. V. Subrahmanyam:
On Some Communication Complexity Problems Related to THreshold Functions.
FSTTCS 1993: 248-259 |
| 1992 |
|---|
| 3 | pdf | Shiva Chaudhuri,
Jaikumar Radhakrishnan:
The Complexity of Parallel Prefix Problems on Small Domains
FOCS 1992: 638-647 |
| 2 | pdf | Jaikumar Radhakrishnan:
Improved Bounds for Covering Complete Uniform Hypergraphs.
Inf. Process. Lett. 41(4): 203-207 (1992) |
| 1991 |
|---|
| 1 | pdf | Jaikumar Radhakrishnan:
Better Bounds for Threshold Formulas
FOCS 1991: 314-323 |