2005 | ||
---|---|---|
52 | 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 | 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 | 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 | Nathan Linial, Jaikumar Radhakrishnan: Essential covers of the cube by hyperplanes. J. Comb. Theory, Ser. A 109(2): 331-338 (2005) | |
2004 | ||
49 | 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 | Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen: A Lower Bound for the Bounded Round Quantum Communication Complexity of Set Disjointness. FOCS 2003: 220-229 | |
46 | Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen: A Direct Sum Theorem in Communication Complexity via Message Compression. ICALP 2003: 300-315 | |
45 | Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener: On Converting CNF to DNF. MFCS 2003: 612-621 | |
44 | 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 | Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen: A direct sum theorem in communication complexity via message compression CoRR cs.CC/0304020: (2003) | |
42 | Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener: On Converting CNF to DNF Electronic Colloquium on Computational Complexity (ECCC) 10(017): (2003) | |
41 | Jaikumar Radhakrishnan: A note on scrambling permutations. Random Struct. Algorithms 22(4): 435-439 (2003) | |
2002 | ||
40 | 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 | S. Mishra, Jaikumar Radhakrishnan, S. Sivasubramanian: On the Hardness of Approximating Minimum Monopoly Problems. FSTTCS 2002: 277-288 | |
37 | 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 | Jaikumar Radhakrishnan, Venkatesh Raman, S. Srinivasa Rao: Explicit Deterministic Constructions for Membership in the Bitprobe Model. ESA 2001: 290-299 | |
33 | 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 | 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 | 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 | 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 | Jaikumar Radhakrishnan, Amnon Ta-Shma: Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators. SIAM J. Discrete Math. 13(1): 2-24 (2000) | |
1999 | ||
24 | 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 | Stephen Ponzio, Jaikumar Radhakrishnan, S. Venkatesh: The Communication Complexity of Pointer Chasing: Applications of Entropy and Sampling. STOC 1999: 602-611 | |
1998 | ||
22 | Madhavan Mukund, K. Narayan Kumar, Jaikumar Radhakrishnan, Milind A. Sohoni: Towards a Characterisation of Finite-State Message-Passing Systems. ASIAN 1998: 282-299 | |
21 | Jaikumar Radhakrishnan, Aravind Srinivasan: Improved Bounds and Algorithms for Hypergraph Two-Coloring. FOCS 1998: 684-693 | |
20 | Madhavan Mukund, K. Narayan Kumar, Jaikumar Radhakrishnan, Milind A. Sohoni: Robust Asynchronous Protocols Are Finite-State. ICALP 1998: 188-199 | |
1997 | ||
19 | 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 | Jaikumar Radhakrishnan: An Entropy Proof of Bregman's Theorem. J. Comb. Theory, Ser. A 77(1): 161-164 (1997) | |
15 | Jaikumar Radhakrishnan: Better Lower Bounds for Monotone Threshold Formulas. J. Comput. Syst. Sci. 54(2): 221-226 (1997) | |
1996 | ||
14 | 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 | 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 | 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 | Jaikumar Radhakrishnan: Sigma Pi Sigma Threshold Formulas. Combinatorica 14(3): 345-374 (1994) | |
7 | 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 | 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 | Shiva Chaudhuri, Jaikumar Radhakrishnan: The Complexity of Parallel Prefix Problems on Small Domains FOCS 1992: 638-647 | |
2 | Jaikumar Radhakrishnan: Improved Bounds for Covering Complete Uniform Hypergraphs. Inf. Process. Lett. 41(4): 203-207 (1992) | |
1991 | ||
1 | Jaikumar Radhakrishnan: Better Bounds for Threshold Formulas FOCS 1991: 314-323 |
1 | Gerth Stølting Brodal | [13] |
2 | Harry Buhrman | [28] [35] |
3 | Shiva Chaudhuri | [3] [12] [13] [14] [17] |
4 | Amit Deshpande | [37] |
5 | Devdatt P. Dubhashi | [44] |
6 | Magnús M. Halldórsson | [4] [5] [6] [9] [10] [18] |
7 | Rahul Jain | [37] [39] [40] [43] [46] [47] |
8 | T. Kavitha | [37] |
9 | K. Narayan Kumar | [20] [22] |
10 | Nathan Linial | [50] |
11 | Satyanarayana V. Lokam | [37] |
12 | Alessandro Mei | [44] |
13 | Peter Bro Miltersen | [28] [35] [42] [45] |
14 | S. Mishra | [38] |
15 | Madhavan Mukund | [20] [22] |
16 | Alessandro Panconesi | [44] [49] |
17 | Paritosh K. Pandya | [48] |
18 | Stephen Ponzio | [23] [24] [31] |
19 | Venkatesh Raman | [32] [34] |
20 | S. Srinivasa Rao | [34] |
21 | Pranab Sen | [27] [29] [30] [33] [36] [39] [40] [43] [46] [47] |
22 | S. Sivasubramanian | [38] |
23 | Milind A. Sohoni | [20] [22] |
24 | Aravind Srinivasan | [21] [26] [44] |
25 | K. V. Subrahmanyam | [4] [5] [7] |
26 | Amnon Ta-Shma | [19] [25] |
27 | S. Venkatesh | [23] [24] [27] [28] [30] [31] [35] [36] |
28 | Sundar Vishwanathan | [29] [33] |
29 | Ingo Wegener | [42] [45] |