Jump to Content
Prabhakar Raghavan

Prabhakar Raghavan

Prabhakar Raghavan is a Senior Vice President at Google. He is responsible for Google Search, Assistant, Geo, Ads, Commerce and Payments products.

Prabhakar is one of the foremost authorities on Search and is the co-author of two widely-used graduate texts on algorithms and on search: Randomized Algorithms and Introduction to Information Retrieval. He has over 20 years of research spanning algorithms, web search and databases, published over 100 papers in various fields, and holds 20 issued patents, including several on link analysis for web search.

Previously, he served as Vice President of Google Apps, Google Cloud, overseeing engineering, products and user experience. Under his leadership, the Apps business expanded from a set of consumer apps to an enterprise solution that is a major contributor to Google’s Cloud business. He also grew both Gmail and Drive past 1 billion MAUs and introduced a number of machine intelligence features in G Suite, including Smart Reply, Smart Compose, Drive Quick Access — each leading to measurable improvements in user experience.

In 2018 he became responsible for the Ads & Commerce teams, including search, display and video advertising, analytics, shopping, payments, and travel. He’s helped drive double-digit growth, while remaining centered on longstanding principles of user trust and fair value exchange among users, publishers, and advertisers.

Prior to joining Google, Prabhakar founded and led Yahoo! Labs where he was responsible for search and ad ranking, as well as ad marketplace design, and later served as the company’s Chief Strategy Officer. He also served as CTO at Verity, and held various positions over the course of 14 years at IBM with a focus on algorithms, data mining and machine learning.

Prabhakar holds a Ph.D. from U.C. Berkeley in Electrical Engineering and Computer Science and a Bachelor of Technology from the Indian Institute of Technology, Madras. He is a member of the National Academy of Engineering; a Fellow of the ACM and IEEE; a former editor in chief for the Journal of the ACM; and was a Consulting Professor of Computer Science at Stanford University. In 2009, he was awarded a Laurea honoris causa from the University of Bologna.

Authored Publications
Google Publications
Other Publications
Sort By
  • Title
  • Title, descending
  • Year
  • Year, descending
    The Limits of Popularity-Based Recommendations, and the Role of Social Ties
    Marco Bressan
    Stefano Leucci
    Alessandro Panconesi
    Erisa Terolli
    Proceedings of ACM KDD 2016, ACM
    Preview abstract In this paper we introduce a mathematical model that captures some of the salient features of recommender systems that are based on popularity and that try to exploit social ties among the users. We show that, under very general conditions, the market always converges to a steady state, for which we are able to give an explicit form. Thanks to this we can tell rather precisely how much a market is altered by a recommendation system, and determine the power of users to influence others. Our theoretical results are complemented by experiments with real world social networks showing that social graphs prevent large market distortions in spite of the presence of highly influential users. View details
    Current trends in the integration of searching and browsing
    Yoelle S. Maarek
    Krishna Bharat
    Susan T. Dumais
    Steve Papa
    Jan O. Pedersen
    WWW (Special interest tracks and posters) (2005), pp. 793
    Preview
    Models for the Compressible Web
    Flavio Chierichetti
    Ravi Kumar
    Alessandro Panconesi
    SIAM Journal on Computing (2013)
    Are web users really Markovian?
    Flavio Chierichetti
    Ravi Kumar
    Tamás Sarlós
    WWW (2012), pp. 609-618
    An algorithmic treatment of strong queries
    Ravi Kumar
    WSDM (2011), pp. 775-784
    Markov Layout
    Flavio Chierichetti
    Ravi Kumar
    FOCS (2011), pp. 492-501
    An Algorithmic Treatment of Strong Queries.
    Optimizing two-dimensional search results presentation
    Flavio Chierichetti
    Ravi Kumar
    WSDM (2011), pp. 257-266
    The Quantitative Analysis of User Behavior Online - Data, Models and Algorithms
    SWAT (2010), pp. 163
    The Quantitative Analysis of User Behavior Online - Data, Models and Algorithms
    CSR (2010), pp. 327
    Heavy Tails and Models for the Web and Social Networks
    ICDCN (2010), pp. 2
    Search is dead!: long live search
    Elizabeth F. Churchill
    Marti Hearst
    Barney Pell
    WWW (2010), pp. 1337-1338
    The FUNnest Talks That belong to FUN (Abstract)
    FUN (2010), pp. 3
    Some results of Christos Papadimitriou on internet structure, network routing, and web information
    Jon M. Kleinberg
    Computer Science Review, vol. 3 (2009), pp. 119-125
    Models for the Compressible Web
    Flavio Chierichetti
    Ravi Kumar
    Alessandro Panconesi
    FOCS (2009), pp. 331-340
    Next Generation Web Search
    Ricardo A. Baeza-Yates
    SeCO Workshop (2009), pp. 11-23
    Models for the Compressible Web.
    Flavio Chierichetti
    Ravi Kumar
    Alessandro Panconesi
    FOCS2009
    Compressed web indexes
    Flavio Chierichetti
    Ravi Kumar
    WWW (2009), pp. 451-460
    On compressing social networks.
    Flavio Chierichetti
    Ravi Kumar
    Michael Mitzenmacher
    Alessandro Panconesi
    KDD2009
    Online story scheduling in web advertising
    Anirban Dasgupta
    Arpita Ghosh
    Hamid Nazerzadeh
    SODA (2009), pp. 1275-1284
    On compressing social networks
    Flavio Chierichetti
    Ravi Kumar
    Michael Mitzenmacher
    Alessandro Panconesi
    KDD (2009), pp. 219-228
    Heavy Tails and Web Models
    SUM (2008), pp. 4
    Introduction to information retrieval
    Christopher D. Manning
    Hinrich Schütze
    Cambridge University Press (2008), I-XXI, 1-482
    The Changing Face of Web Search
    CPM (2008), pp. 4
    Web Search: Bridging Information Retrieval and Microeconomic Modeling
    HiPC (2007), pp. 6
    Web search: from information retrieval to microeconomic modeling
    CIKM (2007), pp. 1-2
    Finding near neighbors through cluster pruning
    Flavio Chierichetti
    Alessandro Panconesi
    Mauro Sozio
    Alessandro Tiberi
    Eli Upfal
    PODS (2007), pp. 103-112
    Visualizing tags over time
    Micah Dubinko
    Ravi Kumar
    Joseph Magnani
    Jasmine Novak
    TWEB, vol. 1 (2007)
    The changing face of web search: algorithms, auctions and advertising
    STOC (2006), pp. 129
    Guest Editors' Introduction
    Fred Douglis
    World Wide Web, vol. 9 (2006), pp. 367-368
    The Changing Face of Web Search
    PAKDD (2006), pp. 11
    Using PageRank to Characterize Web Structure
    Gopal Pandurangan
    Eli Upfal
    Internet Mathematics, vol. 3 (2006), pp. 1-20
    Visualizing tags over time
    Micah Dubinko
    Ravi Kumar
    Joseph Magnani
    Jasmine Novak
    WWW (2006), pp. 193-202
    Core algorithms in the CLEVER system
    Ravi Kumar
    Sridhar Rajagopalan
    ACM Trans. Internet Techn., vol. 6 (2006), pp. 131-152
    The Changing Face of Web Search
    MDM (2006), pp. 2
    Incentive networks
    KDD (2005), pp. 1
    Automatic Subspace Clustering of High Dimensional Data
    Rakesh Agrawal
    Johannes Gehrke
    Dimitrios Gunopulos
    Data Min. Knowl. Discov., vol. 11 (2005), pp. 5-33
    Query Incentive Networks
    ASIAN (2005), pp. 19-21
    On the Bursty Evolution of Blogspace
    Ravi Kumar
    Jasmine Novak
    World Wide Web, vol. 8 (2005), pp. 159-178
    Query Incentive Networks
    Jon M. Kleinberg
    FOCS (2005), pp. 132-141
    Incentive Networks
    LA-WEB (2005)
    Encoding XML in Vector Spaces
    Vinay Kakade
    ECIR (2005), pp. 96-111
    Variable latent semantic indexing
    Anirban Dasgupta
    Ravi Kumar
    KDD (2005), pp. 13-21
    Anti-aliasing on the web
    Jasmine Novak
    WWW (2004), pp. 30-39
    Propagation of trust and distrust
    Structure and evolution of blogspace
    Ravi Kumar
    Jasmine Novak
    Commun. ACM, vol. 47 (2004), pp. 35-39
    Multidimensional Cube Packing
    Yoshiharu Kohayakawa
    Flávio Keidi Miyazawa
    Yoshiko Wakabayashi
    Algorithmica, vol. 40 (2004), pp. 173-187
    Social Networks and the Web
    AWIC (2004), pp. 1
    Segmentation problems
    Jon M. Kleinberg
    Christos H. Papadimitriou
    J. ACM, vol. 51 (2004), pp. 263-280
    Efficiency-Quality Tradeoffs for Vector Score Aggregation
    Pavan Kumar C. Singitham
    Mahathi S. Mahabhashyam
    VLDB (2004), pp. 624-635
    Building low-diameter peer-to-peer networks
    Gopal Pandurangan
    Eli Upfal
    IEEE Journal on Selected Areas in Communications, vol. 21 (2003), pp. 995-1002
    SETS: search enhanced by topic segmentation
    Mayank Bawa
    Gurmeet Singh Manku
    SIGIR (2003), pp. 306-313
    Dynamic schemes for speculative execution of code
    Hadas Shachnai
    Mira Yaniv
    Perform. Eval., vol. 53 (2003), pp. 125-142
    Editorial: Preserving excellence through change
    J. ACM, vol. 50 (2003), pp. 427-428
    Extracting and Exploiting Structure in Text Search
    SIGMOD Conference (2003), pp. 635
    Symphony: Distributed Hashing in a Small World
    Gurmeet Singh Manku
    Mayank Bawa
    USENIX Symposium on Internet Technologies and Systems (2003)
    On the bursty evolution of blogspace
    Ravi Kumar
    Jasmine Novak
    WWW (2003), pp. 568-576
    Auditing Boolean attributes
    Jon M. Kleinberg
    Christos H. Papadimitriou
    J. Comput. Syst. Sci., vol. 66 (2003), pp. 244-253
    Social Networks: From the Web to the Enterprise
    IEEE Internet Computing, vol. 6 (2002), pp. 91-94
    More on random walks, electrical networks, and the harmonic k-server algorithm
    Yair Bartal
    Marek Chrobak
    John Noga
    Inf. Process. Lett., vol. 84 (2002), pp. 271-276
    Using PageRank to Characterize Web Structure
    Gopal Pandurangan
    Eli Upfal
    COCOON (2002), pp. 330-339
    Query Strategies for Priced Information
    Moses Charikar
    Ronald Fagin
    Venkatesan Guruswami
    Jon M. Kleinberg
    Amit Sahai
    J. Comput. Syst. Sci., vol. 64 (2002), pp. 785-819
    Competitive recommendation systems
    Petros Drineas
    Iordanis Kerenidis
    STOC (2002), pp. 82-90
    Thematic mapping - from unstructured documents to taxonomies
    Christina Yip Chung
    Raymond Lieu
    Jinhui Liu
    Alpha K. Luk
    Jianchang Mao
    CIKM (2002), pp. 608-610
    Mining Significant Associations in Large Scale Text Corpora
    Panayiotis Tsaparas
    ICDM (2002), pp. 402-409
    The Web and Social Networks
    Ravi Kumar
    Sridhar Rajagopalan
    IEEE Computer, vol. 35 (2002), pp. 32-36
    A deterministic (2-2/(k+1))n algorithm for k-SAT based on local search
    Evgeny Dantsin
    Andreas Goerdt
    Edward A. Hirsch
    Ravi Kannan
    Jon M. Kleinberg
    Christos H. Papadimitriou
    Uwe Schöning
    Theor. Comput. Sci., vol. 289 (2002), pp. 69-83
    Recommendation Systems: A Probabilistic Analysis
    Ravi Kumar
    Sridhar Rajagopalan
    J. Comput. Syst. Sci., vol. 63 (2001), pp. 42-61
    Adversarial queuing theory
    Allan Borodin
    Jon M. Kleinberg
    Madhu Sudan
    David P. Williamson
    J. ACM, vol. 48 (2001), pp. 13-38
    Building Low-Diameter P2P Networks
    Gopal Pandurangan
    Eli Upfal
    FOCS (2001), pp. 492-499
    Structured and Unstructured Search in Enterprises
    IEEE Data Eng. Bull., vol. 24 (2001), pp. 15-18
    On Semi-Automated Web Taxonomy Construction
    Ravi Kumar
    Sridhar Rajagopalan
    WebDB (2001), pp. 91-96
    Multidimensional Cube Packing
    Yoshiharu Kohayakawa
    Flávio Keidi Miyazawa
    Yoshiko Wakabayashi
    Electronic Notes in Discrete Mathematics, vol. 7 (2001), pp. 110-113
    Navigating large-scale semi-structured data in business portals
    Mani Abrol
    Neil Latarche
    Uma Mahadevan
    Jianchang Mao
    Rajat Mukherjee
    Michel Tourn
    John Wang
    Grace Zhang
    VLDB (2001), pp. 663-666
    Social Networks on the Web and in the Enterprise
    Web Intelligence (2001), pp. 58-60
    Auditing Boolean Attributes
    Jon M. Kleinberg
    Christos H. Papadimitriou
    PODS (2000), pp. 86-91
    Random walks with ``back buttons'' (extended abstract)
    Ronald Fagin
    Anna R. Karlin
    Jon M. Kleinberg
    Sridhar Rajagopalan
    Ronitt Rubinfeld
    Madhu Sudan
    STOC (2000), pp. 484-493
    The Web as a Graph
    Ravi Kumar
    Sridhar Rajagopalan
    D. Sivakumar
    Eli Upfal
    PODS (2000), pp. 1-10
    Clustering Categorical Data: An Approach Based on Dynamical Systems
    David Gibson
    Jon M. Kleinberg
    VLDB J., vol. 8 (2000), pp. 222-236
    Graph structure in the Web
    Ravi Kumar
    Farzin Maghoul
    Sridhar Rajagopalan
    Raymie Stata
    Janet L. Wiener
    Computer Networks, vol. 33 (2000), pp. 309-320
    Graph Structure of the Web: A Survey
    LATIN (2000), pp. 123-125
    Markov Paging
    Anna R. Karlin
    Steven J. Phillips
    SIAM J. Comput., vol. 30 (2000), pp. 906-922
    Random graph models for the web graph
    Ravi Kumar
    Sridhar Rajagopalan
    D. Sivakumar
    Eli Upfal
    FOCS (2000), pp. 57-65
    Latent Semantic Indexing: A Probabilistic Analysis
    Christos H. Papadimitriou
    Hisao Tamaki
    Santosh Vempala
    J. Comput. Syst. Sci., vol. 61 (2000), pp. 217-235
    Extracting Large-Scale Knowledge Bases from the Web
    Ravi Kumar
    Sridhar Rajagopalan
    VLDB (1999), pp. 639-650
    Mining the Web's Link Structure
    Soumen Chakrabarti
    Byron Dom
    Ravi Kumar
    Sridhar Rajagopalan
    David Gibson
    Jon M. Kleinberg
    IEEE Computer, vol. 32 (1999), pp. 60-67
    On targeting Markov segments
    Moses Charikar
    Ravi Kumar
    Sridhar Rajagopalan
    STOC (1999), pp. 99-108
    The Web as a Graph: Measurements, Models, and Methods
    Jon M. Kleinberg
    Ravi Kumar
    Sridhar Rajagopalan
    COCOON (1999), pp. 1-17
    Combinatorial and experimental results for randomized point matching algorithms
    Sandy Irani
    Comput. Geom., vol. 12 (1999), pp. 17-31
    A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata
    Paul Beame
    Allan Borodin
    Walter L. Ruzzo
    Martin Tompa
    SIAM J. Comput., vol. 28 (1999), pp. 1051-1072
    Topic Distillation and Spectral Filtering
    Soumen Chakrabarti
    Byron Dom
    David Gibson
    Ravi Kumar
    Sridhar Rajagopalan
    Artif. Intell. Rev., vol. 13 (1999), pp. 409-435
    Trawling the Web for Emerging Cyber-Communities
    Ravi Kumar
    Sridhar Rajagopalan
    Computer Networks, vol. 31 (1999), pp. 1481-1493
    Dynamic Schemes for Speculative Execution of Code
    Hadas Shachnai
    Mira Yaniv
    MASCOTS (1998), pp. 309-
    On a theory of computing symposia
    Avrim Blum
    SIGACT News, vol. 29 (1998), pp. 104-111
    Latent Semantic Indexing: A Probabilistic Analysis
    Christos H. Papadimitriou
    Hisao Tamaki
    Santosh Vempala
    PODS (1998), pp. 159-168
    Clustering Categorical Data: An Approach Based on Dynamical Systems
    David Gibson
    Jon M. Kleinberg
    VLDB (1998), pp. 311-322
    Stochastic Contention Resolution With Short Delays
    Eli Upfal
    SIAM J. Comput., vol. 28 (1998), pp. 709-719
    Recommendation Systems: A Probabilistic Analysis
    Ravi Kumar
    Sridhar Rajagopalan
    FOCS (1998), pp. 664-673
    Scalable Feature Selection, Classification and Signature Generation for Organizing Large Text Databases into Hierarchical Topic Taxonomies
    Soumen Chakrabarti
    Byron Dom
    Rakesh Agrawal
    VLDB J., vol. 7 (1998), pp. 163-178
    Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications
    Rakesh Agrawal
    Johannes Gehrke
    Dimitrios Gunopulos
    SIGMOD Conference (1998), pp. 94-105
    Inferring Web Communities from Link Topology
    David Gibson
    Jon M. Kleinberg
    Hypertext (1998), pp. 225-234
    Approximation Schemes for Euclidean k-Medians and Related Problems
    Sanjeev Arora
    Satish Rao
    STOC (1998), pp. 106-113
    Randomized Query Processing in Robot Path Planning
    Lydia E. Kavraki
    Jean-Claude Latombe
    Rajeev Motwani
    J. Comput. Syst. Sci., vol. 57 (1998), pp. 50-66
    Segmentation Problems
    Jon M. Kleinberg
    Christos H. Papadimitriou
    STOC (1998), pp. 473-482
    A Microeconomic View of Data Mining
    Jon M. Kleinberg
    Christos H. Papadimitriou
    Data Min. Knowl. Discov., vol. 2 (1998), pp. 311-324
    Automatic Resource Compilation by Analyzing Hyperlink Structure and Associated Text
    Soumen Chakrabarti
    Byron Dom
    Sridhar Rajagopalan
    David Gibson
    Jon M. Kleinberg
    Computer Networks, vol. 30 (1998), pp. 65-74
    The Electrical Resistance of a Graph Captures its Commute and Cover Times
    Ashok K. Chandra
    Walter L. Ruzzo
    Roman Smolensky
    Prasoon Tiwari
    Computational Complexity, vol. 6 (1997), pp. 312-340
    Using Taxonomy, Discriminants, and Signatures for Navigating in Text Databases
    Soumen Chakrabarti
    Byron Dom
    Rakesh Agrawal
    VLDB (1997), pp. 446-455
    How much can hardware help routing?
    Allan Borodin
    Baruch Schieber
    Eli Upfal
    J. ACM, vol. 44 (1997), pp. 726-741
    Strategic directions in research in theory of computing
    Anne Condon
    Faith Fich
    Greg N. Frederickson
    Andrew V. Goldberg
    David S. Johnson
    Michael C. Loui
    Steven Mahaney
    John E. Savage
    Alan L. Selman
    David B. Shmoys
    SIGACT News, vol. 28 (1997), pp. 75-93
    Locality-Preserving Hashing in Multidimensional Spaces
    Piotr Indyk
    Rajeev Motwani
    Santosh Vempala
    STOC (1997), pp. 618-625
    A Random Sampling Scheme for Path Planning
    Jérôme Barraquand
    Lydia E. Kavraki
    Jean-Claude Latombe
    Tsai-Yen Li
    Rajeev Motwani
    I. J. Robotic Res., vol. 16 (1997), pp. 759-774
    Navigating in Unfamiliar Geometric Terrain
    Avrim Blum
    Baruch Schieber
    SIAM J. Comput., vol. 26 (1997), pp. 110-137
    Information Retrieval Algorithms: A Survey
    SODA (1997), pp. 11-18
    Time-Space Tradeoffs for Undirected Graph Traversal by Graph Automata
    Paul Beame
    Allan Borodin
    Walter L. Ruzzo
    Martin Tompa
    Inf. Comput., vol. 130 (1996), pp. 101-129
    A Linear Method for Deviation Detection in Large Databases
    Andreas Arning
    Rakesh Agrawal
    KDD (1996), pp. 164-169
    A Theory of Wormhole Routing in Parallel Computers
    Sergio A. Felperin
    Eli Upfal
    IEEE Trans. Computers, vol. 45 (1996), pp. 704-713
    Combinatorial and Experimental Results for Randomized Point Matching Algorithms
    Sandy Irani
    Symposium on Computational Geometry (1996), pp. 68-77
    Adversarial Queueing Theory
    Allan Borodin
    Jon M. Kleinberg
    Madhu Sudan
    David P. Williamson
    STOC (1996), pp. 376-385
    Computational Geometry Impact Potential: A Business and Industrial Perspective
    CCCG (1996), pp. 276
    Competitive Paging with Locality of Reference
    Allan Borodin
    Sandy Irani
    Baruch Schieber
    J. Comput. Syst. Sci., vol. 50 (1995), pp. 244-258
    Robust Algorithms for Packet Routing in a Mesh
    Mathematical Systems Theory, vol. 28 (1995), pp. 1-11
    Motion planning for a steering-constrained robot through moderate obstacles
    Pankaj K. Agarwal
    Hisao Tamaki
    STOC (1995), pp. 343-352
    The Worst-Case Running Time of the Random Simplex Algorithm is Exponential in the Height
    Martin E. Dyer
    Alan M. Frieze
    Eli Upfal
    Inf. Process. Lett., vol. 56 (1995), pp. 79-81
    Randomized query processing in robot path planning (Extended Abstract)
    Lydia E. Kavraki
    Jean-Claude Latombe
    Rajeev Motwani
    STOC (1995), pp. 353-362
    Stochastic contention resolution with short delays
    Eli Upfal
    STOC (1995), pp. 229-237
    Randomized Algorithms
    Rajeev Motwani
    SIGACT News, vol. 26 (1995), pp. 48-50
    The Traveling Cameraman Problem, with Applications to Automatic Optical Inspection
    Kazuo Iwano
    Hisao Tamaki
    ISAAC (1994), pp. 29-37
    Efficient routing in all-optical networks
    Eli Upfal
    STOC (1994), pp. 134-143
    Motion Planning on a Graph (Extended Abstract)
    Christos H. Papadimitriou
    Madhu Sudan
    Hisao Tamaki
    FOCS (1994), pp. 511-520
    Guest Editor's Foreword: Special Issue on On-Line Algorithms
    Algorithmica, vol. 11 (1994), pp. 1
    The minimum latency problem
    Avrim Blum
    Prasad Chalasani
    Don Coppersmith
    William R. Pulleyblank
    Madhu Sudan
    STOC (1994), pp. 163-171
    Computing with Noisy Information
    Uriel Feige
    David Peleg
    Eli Upfal
    SIAM J. Comput., vol. 23 (1994), pp. 1001-1018
    Randomized Approximation Algorithms in Combinatorial Optimization
    FSTTCS (1994), pp. 300-317
    Trading Space for Time in Undirected s-t Connectivity
    Anna R. Karlin
    Eli Upfal
    SIAM J. Comput., vol. 23 (1994), pp. 324-334
    Memory versus randomization in on-line algorithms
    Marc Snir
    IBM Journal of Research and Development, vol. 38 (1994), pp. 683-708
    Randomized Algorithms and Pseudorandom Numbers
    Howard J. Karloff
    J. ACM, vol. 40 (1993), pp. 454-476
    Fast Deflection Routing for Packets and Worms (Extended Summary)
    Amotz Bar-Noy
    Baruch Schieber
    Hisao Tamaki
    PODC (1993), pp. 75-86
    How much can hardware help routing?
    Allan Borodin
    Baruch Schieber
    Eli Upfal
    STOC (1993), pp. 573-582
    Random Walks on Weighted Graphs and Applications to On-line Algorithms
    Don Coppersmith
    Peter Doyle
    Marc Snir
    J. ACM, vol. 40 (1993), pp. 421-453
    Integer Programming in VLSI Design
    Discrete Applied Mathematics, vol. 40 (1992), pp. 29-43
    A Theory of Wormhole Routing in Parallel Computers (Extended Abstract)
    Sergio A. Felperin
    Eli Upfal
    FOCS (1992), pp. 563-572
    Markov Paging (Extended Abstract)
    Anna R. Karlin
    Steven J. Phillips
    FOCS (1992), pp. 208-217
    Exact Analysis of Hot-Potato Routing (Extended Abstract)
    Uriel Feige
    FOCS (1992), pp. 553-562
    An Experimental Study of Wormhole Routing in Parallel Computers
    Sergio A. Felperin
    Eli Upfal
    Heinz Nixdorf Symposium (1992), pp. 156-165
    Fast Geometric Approximation Techniques and Geometric Embedding Problems
    Marshall W. Bern
    Howard J. Karloff
    Baruch Schieber
    Theor. Comput. Sci., vol. 106 (1992), pp. 265-281
    Optimal Time Bounds for Some Proximity Problems in the Plane
    Alok Aggarwal
    Herbert Edelsbrunner
    Prasoon Tiwari
    Inf. Process. Lett., vol. 42 (1992), pp. 55-60
    Deferred Data Structure for the Nearest Neighbor Problem
    Alok Aggarwal
    Inf. Process. Lett., vol. 40 (1991), pp. 119-122
    Multiterminal Global Routing: A Deterministic Approximation Scheme
    Clark D. Thompson
    Algorithmica, vol. 6 (1991), pp. 73-82
    Competitive Paging with Locality of Reference (Preliminary Version)
    Allan Borodin
    Sandy Irani
    Baruch Schieber
    STOC (1991), pp. 249-259
    On the Parallel Complexity of Evaluating Game Trees
    Anna R. Karlin
    Eli Upfal
    SODA (1991), pp. 404-413
    Navigating in Unfamiliar Geometric Terrain (Preliminary Version)
    Avrim Blum
    Baruch Schieber
    STOC (1991), pp. 494-504
    Asymptotically Tight Bounds for Computing with Faulty Arrays of Processors (Extended Abstract)
    Christos Kaklamanis
    Anna R. Karlin
    Frank Thomson Leighton
    Victor Milenkovic
    Satish Rao
    Clark D. Thomborson
    A. Tsantilas
    FOCS (1990), pp. 285-296
    Time-Space Tradeoffs for Undirected Graph Traversal
    Paul Beame
    Allan Borodin
    Walter L. Ruzzo
    Martin Tompa
    FOCS (1990), pp. 429-438
    Computing with Unreliable Information (Preliminary Version)
    Uriel Feige
    David Peleg
    Eli Upfal
    STOC (1990), pp. 128-137
    Random Walks on Weighted Graphs, and Applications to On-line Algorithms (Preliminary Version)
    Don Coppersmith
    Peter Doyle
    Marc Snir
    STOC (1990), pp. 369-378
    Randomized Broadcast in Networks
    Uriel Feige
    David Peleg
    Eli Upfal
    Random Struct. Algorithms, vol. 1 (1990), pp. 447-460
    Randomized Broadcast in Networks
    Uriel Feige
    David Peleg
    Eli Upfal
    SIGAL International Symposium on Algorithms (1990), pp. 128-137
    Memory Versus Randomization in On-line Algorithms (Extended Abstract)
    Marc Snir
    ICALP (1989), pp. 687-703
    Parallel Graph Algorithms That Are Efficient on Average
    Don Coppersmith
    Martin Tompa
    Inf. Comput., vol. 81 (1989), pp. 318-333
    The Electrical Resistance of a Graph Captures its Commute and Cover Times (Detailed Abstract)
    Ashok K. Chandra
    Walter L. Ruzzo
    Roman Smolensky
    Prasoon Tiwari
    STOC (1989), pp. 574-586
    Program Correctness: Can One Test For It?
    Manuel Blum
    IFIP Congress (1989), pp. 127-134
    Trading Space for Time in Undirected s-t Connectivity
    Anna R. Karlin
    Eli Upfal
    STOC (1989), pp. 543-549
    Fast Geometric Approximation Techniques and Geometric Embedding Problems
    Marshall W. Bern
    Howard J. Karloff
    Baruch Schieber
    Symposium on Computational Geometry (1989), pp. 292-301
    Robust Algorithms for Packet Routing in a Mesh
    SPAA (1989), pp. 344-350
    Energy Consumption in VLSI Circuits (Preliminary Version)
    Alok Aggarwal
    Ashok K. Chandra
    STOC (1988), pp. 205-216
    Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs
    J. Comput. Syst. Sci., vol. 37 (1988), pp. 130-143
    Randomized Algorithms and Pseudorandom Numbers
    Howard J. Karloff
    STOC (1988), pp. 310-321
    Parallel Graph Algorithms that Are Efficient on Average
    Don Coppersmith
    Martin Tompa
    FOCS (1987), pp. 260-269
    Randomized rounding: a technique for provably good algorithms and algorithmic proofs
    Clark D. Thompson
    Combinatorica, vol. 7 (1987), pp. 365-374
    A language for describing rectilinear Steiner tree configurations
    Antony P.-C. Ng
    Clark D. Thompson
    DAC (1986), pp. 659-662
    Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs
    FOCS (1986), pp. 10-18
    Provably Good Routing in Graphs: Regular Arrays
    Clark D. Thompson
    STOC (1985), pp. 79-87