Publications:

• Atish Das Sarma, Sreenivas Gollapudi, and Rina Panigrahy, Sparse Cut Projections in Graph Streams, in 17th Annual European Symposium on Algorithms (ESA), European Association for Theoretical Computer Science, September 2009
• Andrew McGregor Krzysztof Onak and Rina Panigrahy, The Oil Searching Problem, in ESA, Springer Verlag, July 2009
• Marc Najork, Sreenivas Gollapudi, and Rina Panigrahy, Less is More: Sampling the Neighborhood Graph Makes SALSA Better and Faster, in 2nd ACM International Conference on Web Search and Data Mining, Association for Computing Machinery, Inc., February 2009
• Eric Lehman and Rina Panigrahy, 3.5-Way Cuckoo Hashing for the Price of 2-and-a-Bit, in ESA, Springer Verlag, 2009
• Rina Panigrahy, Kunal Talwar, and Udi Wieder, A Geometric Approach to Lower Bounds for Approximate Near-Neighbor Search and Partial Match, in FOCS '08: Proceedings of the 49th annual IEEE Symposium on Foundations of Computer Science, IEEE, October 2008
• Yinglian Xie, Fang Yu, Kannan Achan, Rina Panigrahy, Geoff Hulten, and Ivan Osipkov, Spamming Botnet: Signatures and Characteristics, in ACM SIGCOMM 2008, Seattle, WA, August 2008
• Nitin Agrawal, Vijayan Prabhakaran, Ted Wobber, John D. Davis, Mark Manasse, and Rina Panigrahy, Design Tradeoffs for SSD Performance, in Proceedings of the 2008 USENIX Technical Conference (USENIX'08), USENIX, June 2008
• Sreenivas Gollapudi and Rina Panigrahy, The power of two min-hashes in similarity search among hierarchical data objects, in Proceedings of the Twenty-Seventh ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Association for Computing Machinery, Inc., June 2008
• Atish Das Sarma, Sreenivas Gollapudi, and Rina Panigrahy, Estimating PageRank on Graph Streams, in Proceedings of the Twenty-Seventh ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Association for Computing Machinery, Inc., June 2008
• Rina Panigrahy, An Improved Algorithm Finding Nearest Neighbor Using Kd-trees, in Latin American Symposium on Theoretical Informatics (LATIN), Springer, Bzios, Brazil, April 2008
• Thomas Holenstein, Michael Mitzenmacher, Rina Panigrahy, and Udi Wieder, Trace reconstruction with constant deletion probability and related results, in ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, CA, January 2008
• Sreenivas Gollapudi, Marc Najork, and Rina Panigrahy, Using Bloom Filters to Speed Up HITS-like Ranking Algorithms, in 5th Workshop on Algorithms and Models for the Web Graph (WAW), Springer-Verlag, December 2007
• Rina Panigrahy and Dilys Thomas, Finding Frequent Elements in non-bursty Streams, in Annual European Symposium on Algorithms (ESA), Eilat, Israel, October 2007
• Rina Panigrahy and Ravi Kumar, On Finding Frequent Elements in a Data Stream, in Workshop on Randomization and Computation (RANDOM), Princeton University, NJ, August 2007
• Rajeev Motwani, Rina Panigrahy, and Ying Xu 0002, Estimating Sum by Weighted Sampling, in International Colloquium on Automata, Languages and Programming, (ICALP), Wroclaw, Poland, July 2007
• "Hashing Searching Sketching". Ph.D. Thesis, Stanford University.
• "An Improved Construction for Counting Bloom Filters" with F. Bonomi, M. Mitzenmacher, S. Singh, and G. Varghese. ESA 2006.
• "Compact Approximate Representations of Concurrent State Machines for Network Applications" with Flavio Bonomi, Michael Mitzenmacher, Sushil Singh, and George Varghese, Proceedings of the ACM SIGCOMM Conference, Pisa, Italy, September 2006.
• "A Dictionary for Approximate String Search and Longest Prefix Search" with S. Gollapudi. CIKM 2006.
• "Exploiting Asymmetry in Hierarchical Topic Extraction" with S. Gollapudi. CIKM 2006.
• "Estimating Corpus Size via Queries" with A. Broder, M. Fontoura, V. Josifovski, R. Kumar and R. Motwani. CIKM 2006
• "Lower bounds on Locality Sensitive Hashing". SOCG 2006.
• "Near-Perfect Fractional Matching via Balls-and-Bins" with Rajeev Motwani and Ying Xu. RANDOM 2006.
• "Entropy based Nearest Neighbor Search in High Dimensions". SODA 2006.
• "Balanced Allocation on Graphs" with Krishnaram Kenthapadi. SODA 2006.
• "Analyzing the Efficiency of BitTorrent and Related Peer-to-Peer Networks" with David Arthur. SODA 2006.
• "Efficient Hashing with Lookups in two Memory Accesses". SODA 2005.
• "Efficient Multicast on a Terabit Router" with Punit Bhargava and Sriram C. Krishnan. Hot Interconnects 2004.
• "Better streaming algorithms for clustering problems" with Moses Charikar and Liadan O'Callaghan. STOC 2003.
• "Computing Shortest Paths with Uncertainty" with Tomas Feder, Rajeev Motwani, Liadan O'Callaghan, chris Olston. STACS 2003.
• "Representing Graph Metrics with Fewest Edges" with Tomas Feder, Adam Meyerson, Rajeev Motwani, Liadan O'Callaghan. STACS 2003.
• Sorting and Searching using Ternary CAMs Rina Panigrahy, Samar Sharma (Cisco Systems). Hot Interconnects 2002. Also in IEEE Micro 23(1): 44-53 (2003)
• Reducing TCAM Power Consumption and Increasing Throughput Rina Panigrahy, Samar Sharma (Cisco Systems). Hot Interconnects 2002
• David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, and Rina Panigrahy. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 654-663, El Paso, Texas, 4-6 May 1997.
• Object Accessibility for Java is Decidable. (with R. Motwani, V. Saraswat, and S. Venkatasubrmanian)
  Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000.
• Computing the Median with Uncertainty. (with T. Feder, R. Motwani, C. Olston, and J. Widom)
  Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000.
• Web Caching With Request Reordering. (with T. Feder, R. Motwani, and A. Zhu)
  Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002.
• New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching and Related Problems,
  with P. Indyk and M. Charikar,
  Proceedings of the 29th International Colloquium on Automata Languages and Programming, 2002.
• Approximating The Smallest Grammar: Kolmogorov Complexity in Natural Models,
  with E. Lehman, D. Liu, M. Charikar, M. Prabhakaran, A. Rasala, A. Sahai, and A. Shelat,
  in Proceedings of the 34th Annual ACM Symposium on Theory of Computing, (2002)..
• Rina Panigrahy and Sundar Vishwanathan, ``An O(log^* n) approximation algorithm for the asymmetric p-center problem,'' Journal of Algorithms, 27:259--268, 1998.