Publications

• Rina Panigrahy, Preyas Popat, Fractal Structures in Adversarial Prediction , ITCS 2015
• Alexandr Andoni, Rina Panigrahy, Gregory Valiant, and Li Zhang, Learning polynomials with neural networks , ICML, June 2014
• Alexandr Andoni, Rina Panigrahy, Gregory Valiant, and Li Zhang, Learning sparse polynomials, SODA, ACM, 2014
• Abhimanyu Das, Sreenivas Gollapudi, Rina Panigrahy, and Mahyar Salek, Debiasing Social Wisdom , ACM International Conference on Knowledge Discovery and Data Mining, August 2013
• Anish Das Sarma, Sreenivas Gollapudi, Rina Panigrahy, and Li Zhang, Undertanding cyclic trends in social choices, Proc. ACM Conf on Web Search and Data Mining, ACM, February 2012
• Rina Panigrahy, Marc Najork, and Yinglian Xie, How User Behavior is Related to Social Affinity, in 5th ACM International Conference on Web Search and Data Mining (WSDM), ACM, February 2012
• Michael Kapralov and Rina Panigrahy, Prediction strategies without loss, Neural Information Processing Systems Foundation, 2012
• Michael Kapralov and Rina Panigrahy, Spectral sparsification via random spanners , Innovations in Theoretical Computer Science, 2012
• Ding Yuan, Yinglian Xie, Rina Panigrahy, Junfeng Yang, Chad Verbowski, and Arunvijay Kumar, Context-based Online Configuration-Error Detection , in The 2011 USENIX Annual Technical Conference, USENIX, June 2011
• Sangmin Lee, Rina Panigrahy, Vijayan Prabhakaran, Venugopalan Ramasubramanian, Kunal Talwar, Lincoln Uyeda, and Udi Wieder, Validating Heuristics for Virtual Machines Consolidation , no. MSR-TR-2011-9, January 2011
• Rina Panigrahy, Kunal Talwar, Lincoln Uyeda, and Udi Wieder, Heuristics for Vector Bin Packing, 2011
• Rina Panigrahy, Kunal Talwar, and Udi Wieder, Lower Bounds on Near Neighbor Search via Metric Expansion , FOCS , IEEE Computer Society, October 2010
• Gagan Aggarwal, Tomas Feder, Krishnaram Kenthapadi, Samir Khuller, Rina Panigrahy, Dilys Thomas, and An Zhu, Achieving anonymity via clustering, ACM Transactions on Algorithms (TALG), vol. 6, no. 3, pp. 49:1-49:19, ACM, July 2010
• Atish Das Sarma, Sreenivas Gollapudi, Marc Najork, and Rina Panigrahy, A Sketch-Based Distance Oracle for Web-Scale Graphs , 3rd ACM International Conference on Web Search and Data Mining (WSDM), Association for Computing Machinery, Inc., February 2010
• Anish Das Sarma, Atish Das Sarma, Sreenivas Gollapudi, and Rina Panigrahy, Ranking Mechanisms for Twitter-Like Forums, Proc. of Third ACM International Conference on Web Search and Data Mining (WSDM), Association for Computing Machinery, Inc., 2010
• Rina Panigrahy and Li Zhang. The Mind Grows Circuits.
• Rina Panigrahy A non-expert view on Turing machines, Proof Verifiers, and Mental reasoning.
• Atish Das Sarma, Sreenivas Gollapudi, and Rina Panigrahy, Sparse Cut Projections in Graph Streams, 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, 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, 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, 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 , 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, 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, 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, Buzios, 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, Workshop on Randomization and Computation (RANDOM), Princeton University, NJ, August 2007
• Rajeev Motwani, Rina Panigrahy, and Ying Xu 0002, Estimating Sum by Weighted Sampling, International Colloquium on Automata, Languages and Programming, (ICALP), Wroclaw, Poland, July 2007
• Rina Panigrahy Hashing Searching Sketching, Ph.D. Thesis, Stanford University.
• F. Bonomi, M. Mitzenmacher, R. Panigrahy, S. Singh, and G. Varghese, An Improved Construction for Counting Bloom Filters, ESA 2006.
• with Flavio Bonomi, Michael Mitzenmacher, Rina Panigrahy, Sushil Singh, and George Varghese Compact Approximate Representations of Concurrent State Machines for Network Applications , Proceedings of the ACM SIGCOMM Conference, Pisa, Italy, September 2006.
• S. Gollapudi and R. Panigrahy, A Dictionary for Approximate String Search and Longest Prefix Search, CIKM 2006.
• S. Gollapudi and R. Panigrahy, Exploiting Asymmetry in Hierarchical Topic Extraction, CIKM 2006.
• A. Broder, M. Fontoura, V. Josifovski, R. Kumar, R. Motwani, and R. Panigrahy, Estimating Corpus Size via Queries, CIKM 2006
• Rina Panigrahy, Lower bounds on Locality Sensitive Hashing, SOCG 2006.
• Rajeev Motwani, Rina Panigrahy, and Ying Xu Near-Perfect Fractional Matching via Balls-and-Bins, RANDOM 2006.
• Rina Panigrahy, Entropy based Nearest Neighbor Search in High Dimensions, SODA 2006.
• Rina Panigrahy and Krishnaram Kenthapadi, Balanced Allocation on Graphs(best student paper award), SODA 2006.
• Rina Panigrahy and David Arthur, Analyzing the Efficiency of BitTorrent and Related Peer-to-Peer Networks, SODA 2006.
• Rina Panigrahy, Efficient Hashing with Lookups in two Memory Accesses, SODA 2005.
• Punit Bhargava, Sriram C. Krishnan, and Rina Panigrahy, Efficient Multicast on a Terabit Router, Hot Interconnects 2004.
• Moses Charikar, Liadan O'Callaghan, and Rina Panigrahy, Better streaming algorithms for clustering problems, STOC 2003
• Tomas Feder, Rajeev Motwani, Liadan O'Callaghan, Chris Olston, and Rina Panigrahy, Computing Shortest Paths with Uncertainty, STACS 2003.
• Liadan O'Callaghan, Tomas Feder, Adam Meyerson, Rajeev Motwani, and Rina Panigrahy, Representing Graph Metrics with Fewest Edges, STACS 2003.
• Rina Panigrahy, Samar Sharma, Sorting and Searching using Ternary CAMs , Hot Interconnects 2002. Also in IEEE Micro 23(1): 44-53 (2003)
• Rina Panigrahy, Samar Sharma, Reducing TCAM Power Consumption and Increasing Throughput , 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.
• with R. Motwani, R. Panigrahy, V. Saraswat, and S. Venkatasubrmanian Object Accessibility for Java is Decidable. Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000.
• T. Feder, R. Motwani, R. Panigrahy, C. Olston, and J. Widom, Computing the Median with Uncertainty, Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000.
• T. Feder, R. Motwani, R. Panigrahy, and A. Zhu, Web Caching With Request Reordering.
  Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002.
• M. Charikar, P. Indyk and R. Panigrahy, New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching and Related Problems,
  Proceedings of the 29th International Colloquium on Automata Languages and Programming, 2002.
• E. Lehman, D. Liu, M. Charikar, R. Panigrahy, M. Prabhakaran, A. Rasala, A. Sahai, and A. Shelat, Approximating The Smallest Grammar: Kolmogorov Complexity in Natural Models,
  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.

Patents

• Yoichi Hariguchi, Rina Panigrahy, Samar Sharma, Ashwath Nagaraj: Methods and apparatus for mapping ranges of values into unique values of particular use for range matching operations using an associative memory. Cisco Technology April 2004: US 06717946 (56 worldwide citation)
• David Karger, Eric Lehman, F Thomson Leighton, Matthew Levine, Daniel Lewin, Rina Panigrahy: Method and apparatus for distributing requests among a plurality of resources.Massachusetts Institute of Technology April 2003: US 06553420 (40 worldwide citation)
• Abhijit Patra, Rina Panigrahy, Samar Sharma: Techniques for efficient memory management for longest prefix match problems. Cisco Technology April 2004: US 06725326 (26 worldwide citation)
• Suran Saminda De Silva, Rina Panigrahy, Samar Sharma: Methods and apparatus for longest common prefix based caching. Cisco Technology December 2007: US 07313666 (13 worldwide citation)
• Rina Panigrahy, William Nelson, Anh Tien Nguyen: Methods and apparatus for regular expression matching. Cisco Technology December 2007: US 07308446 (11 worldwide citation)
• Abhijit Patra, Rina Panigrahy, Samar Sharma: Techniques for efficient location of free entries for TCAM inserts. Cisco Technology February 2003: US 06516383 (11 worldwide citation)
• Rina Panigrahy, Abhijit Patra, Samar Sharma: Identification of a longest matching prefix based on a search of intervals corresponding to the prefixes. Cisco Technology January 2009: US 07478109 (9 worldwide citation)
• John J Williams Jr, Rina Panigrahy: DFA sequential matching of regular expression with divergent states. Cisco Technology March 2010: US 07689530 (7 worldwide citation)
• David Karger, Eric Lehman, F Thomson Leighton, Matthew Levine, Daniel Lewin, Rina Panigrahy: Method and apparatus for distributing requests among a plurality of resources..Massachusetts Institute of Technology October 2006: US 07127513 (5 worldwide citation)
• Rina Panigrahy, Samar Sharma: Assigning prefixes to associative memory classes based on a value of a last bit of each prefix and their use including but not limited to locating a prefix and for maintaining a Patricia tree data structure. Cisco Technology November 2007: US 07299317 (4 worldwide citation)
• Rina Panigrahy, Jackie Liu, Daniel Yu Kwong Ng, Sanjay Jain, Nagaraj A Bagepalli, Abhijit Patra: Programmable packet parsing processor. Cisco Technology September 2009: US 07586851(4 worldwide citation)
• Rina Panigrahy: Parse state encoding for a packet parsing processor. Cisco Technology November 2009: US 07619983 (4 worldwide citation)
• Rina Panigrahy, Awais Bin Nemat: Weighted random scheduling particularly applicable to packet switching systems. Cisco Technology June 2006: US 07061927 (3 worldwide citation)
• Rina Panigrahy, Samar Sharma: Methods and apparatus for maintaining sets of ranges typically using an associative memory and for using these ranges to identify a matching range based on a query point or query range and to maintain sorted elements for use such as in providing priority queue operations. Cisco Technology July 2009: US 07558775 (2 worldwide citation)
• Rina Panigrahy, Jackie Liu, Daniel Yu Kwong Ng, Sanjay Jain, Nagaraj A Bagepalli, Abhijit Patra: Programmable packet parsing processor. Cisco Technology November 2009: US 07623468(2 worldwide citation)
• Sreenivas Gollapudi, Rina Panigrahy: Method of finding candidate sub-queries from longer queries. Microsoft Corporation July 2010: US 07765204 (1 worldwide citation)
• Sreenivas Gollapudi, Rina Panigrahy: Semi-supervised part-of-speech tagging. Microsoft Corporation January 2012: US 08099417 (1 worldwide citation)
• Punit Bhargava, Rina Panigrahy, Sriram C Krishnan: Constant time signature methods for scalable and bandwidthefficient multicast. Cisco Technology July 2010: US 07760732 (1 worldwide citation)
• Rina Panigrahy, Chad Verbowski, Yinglian Xie, Junfeng Yang, Ding Yuan: Fingerprinting event logs for system management troubleshooting. Microsoft Corporation November 2011: US 08069374 (1 worldwide citation)
• Sriram Chitoor Krishnan, Rina Panigrahy, Sunil Parthasarathy: Error protected ternary content-addressable memories and lookup operations performed thereon. Cisco Technology March 2008: US 07345897 (1 worldwide citation)
• Rina Panigrahy, Ketan Arun Padwekar: Preventing aliasing of compressed keys across multiple hash tables. Cisco Technology January 2010: US 07650429 (1 worldwide citation)
• Rina Panigrahy: Searching for a path to identify where to move entries among hash tables with storage for multiple entries per bucket during insert operations. Cisco Technology November 2010: US 07827182 (1 worldwide citation)
• Rina Panigrahy, Samar Sharma: Methods and apparatus for distributing entries among lookup units and selectively enabling less than all of the lookup units when performing a lookup operation. Cisco Technology October 2008: US 07441074
• Rina Panigrahy: Stateful flow of network packets within a packet parsing processor. Cisco Technology June 2011: US 07957378
• Lincoln K Uyeda, Rina Panigrahy, Ehud Wieder, Kunal Talwar: Virtual machine packing method using scarcity. Microsoft Corporation June 2013: US 08464267
• Punit Bhargava, Rina Panigrahy, Sriram C Krishnan: Clustering methods for scalable and bandwidth-efficient multicast. Cisco Technology June 2009: US 07554928
• Sreenivas Gollapudi, Rina Panigrahy, Atish Das Sarma: Estimating rank on graph streams. Microsoft Corporation December 2011: US 08073832
• Sriram Chitoor Krishnan, Rina Panigrahy, Sunil Parthasarathy: Error protected ternary content-addressable memories and lookup operations performed thereon. Cisco Technology A California Corporation April 2007: US 20070086227- A1
• Rina Panigrahy, Jackie Liu, Daniel Yu Kwong Ng, Sanjay Jain, Nagaraj A Bagepalli, Abhijit Patra: Programmable packet parsing processor. October 2005: US 20050238010-A1
• Rina Panigrahy: Parse state encoding for a packet parsing processor. October 2005: US 20050238011-A1
• Rina Panigrahy, Jackie Liu, Daniel Yu Kwong Ng, Sanjay Jain, Nagaraj A Bagepalli, Abhijit Patra: Programmable packet parsing processor. October 2005: US 20050238012-A1
• Rina Panigrahy: Stateful flow of network packets within a packet parsing processor. October 2005: US 20050238022- A1
• Rina Panigrahy, Awais Bin Nemat: Weighted random scheduling particularly applicable to packet switching systems. Cisco Technology A California Corporation October 2005: US 20050226263-A1
• Rina Panigrahy, Ketan Arun Padwekar: Preventing aliasing of compressed keys across multiple hash tables. August 2006: US 20060179071-A1
• Punit Bhargava, Rina Panigrahy, Sriram C Krishnan: Constant time signature methods for scalable and bandwidthefficient multicast. Cisco Technology October 2006: US 20060221972-A1
• Punit Bhargava, Rina Panigrahy, Sriram C Krishnan: Clustering methods for scalable and bandwidth-efficient multicast. October 2006: US 20060222012-A1
• Rina Panigrahy, Chad Verbowski, Yinglian Xie, Junfeng Yang, Ding Yuan: Fingerprinting event logs for system management troubleshooting. Microsoft Corporation September 2010: US 20100223499-A1
• Sreenivas Gollapudi, Marc A Najork, Rina Panigrahy: Link based ranking of search results using summaries of result neighborhoods. Microsoft Corporation September 2009: US 20090234829-A1
• Sreenivas Gollapudi, Frank McSherry, Rina Panigrahy, Kunal Talwar: Bidding on related keywords. Microsoft Corporation September 2009: US 20090234734-A1
• Marc A Najork, Sreenivas Gollapudi, Rina Panigrahy, Atish Das Sarma: Estimating shortest distances in graphs. August 2011: US 20110202846-A1
• Lincoln K Uyeda, Rina Panigrahy, Ehud Wieder, Kunal Talwar: Virtual Machine Packing Method Using Scarcity. Microsoft Corporation October 2010: US 20100262964-A1
• Sreenivas Gollapudi, Rina Panigrahy, Atish Das Sarma: Estimating rank on graph streams. Microsoft Corporation November 2010: US 20100281022-A1
• Larry Jay Sauls, Sanjay Gautam, Ehud Wieder, Rina Panigrahy, Kunal Talwar: Multiphase virtual machine host capacity planning. Microsoft Corporation November 2010: US 20100281478-A1
• Sreenivas Gollapudi, Rina Panigrahy: System of ranking search results based on query specific position bias. Microsoft Corporation June 2010: US 20100153370-A1