Arrow Research search

Author name cluster

Prabhakar Raghavan

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

48 papers
2 author rows

Possible papers

48

FOCS Conference 2011 Conference Paper

Markov Layout

  • Flavio Chierichetti
  • Ravi Kumar 0001
  • Prabhakar Raghavan

Consider the problem of laying out a set of n images that match a query onto the nodes of a √n×√n grid. We are given a score for each image, as well as the distribution of patterns by which a user's eye scans the nodes of the grid and we wish to maximize the expected total score of images selected by the user. This is a special case of the Markov layout problem, in which we are given a Markov chain M together with a set of objects to be placed at the states of the Markov chain. Each object has a utility to the user if viewed, as well as a stopping probability with which the user ceases to look further at objects. This layout problem is prototypical in a number of applications in web search and advertising, particularly in an emerging genre of search results pages from major engines. In a different class of applications, the states of the Markov chain are web pages at a publishers website and the objects are advertisements. We study the approximability of the Markov layout problem. Our main result is an O(log n) approximation algorithm for the most general version of the problem. The core idea is to transform an optimization problem over partial permutations into an optimization problem over sets by losing a logarithmic factor in approximation, the latter problem is then shown to be sub modular with two matroid constraints, which admits a constant-factor approximation. In contrast, we also show the problem is APX-hard via a reduction from CUBIC MAX-BISECTION. We then study harder variants of greater practical interest of the problem in which no gaps - states of M with no object placed on them - are allowed. By exploiting the geometry, we obtain an O(log 3/2 n) approximation algorithm when the digraph underlying M is a grid and an O(log n) approximation algorithm when it is a tree. These special cases are especially appropriate for our applications.

Details

FOCS Conference 2009 Conference Paper

Models for the Compressible Web

  • Flavio Chierichetti
  • Ravi Kumar 0001
  • Silvio Lattanzi
  • Alessandro Panconesi
  • Prabhakar Raghavan

Graphs resulting from human behavior (the web graph, friendship graphs, etc.) have hitherto been viewed as a monolithic class of graphs with similar characteristics; for instance, their degree distributions are markedly heavy-tailed. In this paper we take our understanding of behavioral graphs a step further by showing that an intriguing empirical property of web graphs-their compressibility-cannot be exhibited by well-known graph models for the web and for social networks. We then develop amore nuanced model for web graphs and show that it does exhibit compressibility, in addition to previously modeled web graph properties.

Details

STOC Conference 2006 Conference Paper

The changing face of web search: algorithms, auctions and advertising

  • Prabhakar Raghavan

Web search has come to dominate our consciousness as a convenience we take for granted, as a medium for connecting advertisers and buyers, and as a fast-growing revenue source for the companies that provide this service. Following a brief overview of the state of the art and how we got there, this talk covers a spectrum of technical challenges arising in web search.This lecture will begin with an overview of the social, economic and historical challenges underlying web search. Understanding the basic background is a useful prerequisite for deep technical work in this area. Following this, we will cover three vignettes, whose goal is to expose significant research areas rather than to present definitive results.The first deals with an emerging area variously referred to as Human Computation, Social Computation or Social Media . The idea is to solve difficult problems in artificial intelligence (such as image recognition) not through direct computation, but by exploiting the wisdom of crowds on the web. In the simplest form, an incentive mechanism is devised whereby many web users label images descriptively. These labels are then used for image retrieval. This immediately raises several foundational questions. What incentive mechanisms lead to high-quality labels? Given the inevitability of misleading labels (spam), how does one filter out good labels? Since the participants in such a system are likely to be connected in various social networks, how does one propagate trust and reputation in these networks to obtain reliable judges and thereby judgments.The second vignette centers around optimization and marketplace design for advertisements on the internet. We first outline how the presentation of brand advertisement on the internet leads to stochastic programming problems - in turn leading to novel issues in the design of futures contracts. We then turn to a problem more heavily studied in the theoretical computer science literature: the auction design and pricing of advertisement on keyword search results. Beginning with the classic Vickrey auction, known to be a truthful mechanism for single-item, sealed-bid auctions, we point out how sponsored search advertisements depart from this simple setting. We review the current state of the art here and mention several problems that remain open.The final vignette is based on the paper with Kleinberg. We formulate a model for query incentive networks , motivated by users seeking information or services that pose queries, together with incentives for answering them. This type of information-seeking process can be formulated as a game among the nodes in the network, and this game has a natural Nash equilibrium. How much incentive is needed in order to achieve a reasonable probability of obtaining an answer to a query? We study the size of query incentives as a function both of the rarity of the answer and the structure of the underlying network. This leads to natural questions related to strategic behavior in branching processes. Whereas the classically studied criticality of branching processes is centered around the region where the branching parameter is 1, we show in contrast that strategic interaction in incentive propagation exhibits critical behavior when the branching parameter is 2.

Details

FOCS Conference 2005 Conference Paper

Query Incentive Networks

  • Jon M. Kleinberg
  • Prabhakar Raghavan

The concurrent growth of on-line communities exhibiting large-scale social structure, and of large decentralized peer-to-peer file-sharing systems, has stimulated new interest in understanding networks of interacting agents as economic systems. Here we formulate a model for query incentive networks, motivated by such systems: users seeking information or services can pose queries, together with incentives for answering them, that are propagated along paths in a network. This type of information-seeking process can be formulated as a game among the nodes in the network, and this game has a natural Nash equilibrium. In such systems, it is a fundamental question to understand how much incentive is needed in order for a node to achieve a reasonable probability of obtaining an answer to a query from the network. We study the size of query incentives as a function both of the rarity of the answer and the structure of the underlying network. This leads to natural questions related to strategic behavior in branching processes. Whereas the classically studied criticality of branching processes is centered around the region where the branching parameter is 1, we show in contrast that strategic interaction in incentive propagation exhibits critical behavior when the branching parameter is 2.

Details

TCS Journal 2002 Journal Article

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 Kleinberg
  • Christos Papadimitriou
  • Prabhakar Raghavan
  • Uwe Schöning

Local search is widely used for solving the propositional satisfiability problem. Papadimitriou (1991) showed that randomized local search solves 2-SAT in polynomial time. Recently, Schöning (1999) proved that a close algorithm for k-SAT takes time (2−2/k) n up to a polynomial factor. This is the best known worst-case upper bound for randomized 3-SAT algorithms (cf. also recent preprint by Schuler et al.). We describe a deterministic local search algorithm for k-SAT running in time (2−2/(k+1)) n up to a polynomial factor. The key point of our algorithm is the use of covering codes instead of random choice of initial assignments. Compared to other “weakly exponential” algorithms, our algorithm is technically quite simple. We also describe an improved version of local search. For 3-SAT the improved algorithm runs in time 1. 481 n up to a polynomial factor. Our bounds are better than all previous bounds for deterministic k-SAT algorithms.

Details DOI

STOC Conference 2002 Conference Paper

Competitive recommendation systems

  • Petros Drineas
  • Iordanis Kerenidis
  • Prabhakar Raghavan

A recommendation system tracks past purchases of a group of users to make product recommendations to individual members of the group. In this paper we present a notion of competitive recommendation systems, building on recent theoretical work on this subject. We reduce the problem of achieving competitiveness to a problem in matrix reconstruction. We then present a matrix reconstruction scheme that is competitive: it requires a small overhead in the number of users and products to be sampled, delivering in the process a net utility that closely approximates the best possible with full knowledge of all user-product preferences.

Details

FOCS Conference 2001 Conference Paper

Building Low-Diameter P2P Networks

  • Gopal Pandurangan
  • Prabhakar Raghavan
  • Eli Upfal

In a peer-to-peer (P2P) network, nodes connect into an existing network and participate in providing and availing of services. There is no dichotomy between a central server and distributed clients. Current P2P networks (e. g. , Gnutella) are constructed by participants following their own uncoordinated (and often whimsical) protocols; they consequently suffer from frequent network overload and fragmentation into disconnected pieces separated by choke-points with inadequate bandwidth. The authors propose a simple scheme for participants to build P2P networks in a distributed fashion, and prove that it results in connected networks of constant degree and logarithmic diameter. It does so with no global knowledge of all the nodes in the network. In the most common P2P application to date (search), these properties are important.

Details

FOCS Conference 2000 Conference Paper

Random graph models for the web graph

  • Ravi Kumar 0001
  • Prabhakar Raghavan
  • Sridhar Rajagopalan
  • D. Sivakumar 0001
  • Andrew Tomkins
  • Eli Upfal

The Web may be viewed as a directed graph each of whose vertices is a static HTML Web page, and each of whose edges corresponds to a hyperlink from one Web page to another. We propose and analyze random graph models inspired by a series of empirical observations on the Web. Our graph models differ from the traditional G/sub n, p/ models in two ways: 1. Independently chosen edges do not result in the statistics (degree distributions, clique multitudes) observed on the Web. Thus, edges in our model are statistically dependent on each other. 2. Our model introduces new vertices in the graph as time evolves. This captures the fact that the Web is changing with time. Our results are two fold: we show that graphs generated using our model exhibit the statistics observed on the Web graph, and additionally, that natural graph models proposed earlier do not exhibit them. This remains true even when these earlier models are generalized to account for the arrival of vertices over time. In particular, the sparse random graphs in our models exhibit properties that do not arise in far denser random graphs generated by Erdos-Renyi models.

Details

FOCS Conference 1998 Conference Paper

Recommendation Systems: A Probabilistic Analysis

  • Ravi Kumar 0001
  • Prabhakar Raghavan
  • Sridhar Rajagopalan
  • Andrew Tomkins

A recommendation system tracks past actions of a group of users to make recommendations to individual members of the group. The growth of computer-mediated marketing and commerce has led to increased interest in such systems. We introduce a simple analytical framework for recommendation systems, including a basis for defining the utility of such a system. We perform probabilistic analyses of algorithmic methods within this framework. These analyses yield insights into how much utility can be derived from the memory of past actions and on how this memory can be exploited.

Details

ICRA Conference 1997 Conference Paper

Nonholonomic path planning for pushing a disk among obstacles

  • Pankaj K. Agarwal
  • Jean-Claude Latombe
  • Rajeev Motwani 0001
  • Prabhakar Raghavan

We consider the path-planning problem for a robot pushing an object in an environment containing obstacles. This new variant of the classical robot path-planning problem has several interesting geometric aspects, which we explore. We focus on the setting where the robot makes a point contact with the object which is assumed to be a unit disk, while the obstacles are assumed to be polygonal.

Details

FOCS Conference 1997 Conference Paper

Storage Management for Evolving Databases

  • Jon M. Kleinberg
  • Rajeev Motwani 0001
  • Prabhakar Raghavan
  • Suresh Venkatasubramanian

The problem of maintaining data that arrives continuously over time is increasingly prevalent in databases and digital libraries. Building on a model for sliding window indices developed by N. Shivakumar and H. Garcia-Molina (1997), we devise efficient algorithms for some of the central problems that arise. We also show connections between the problems in this model and some fundamental problems in optimization and graph theory.

Details

I&C Journal 1996 Journal Article

Time-Space Tradeoffs for Undirected Graph Traversal by Graph Automata

  • Paul Beame
  • Allan Borodin
  • Prabhakar Raghavan
  • Walter L. Ruzzo
  • Martin Tompa

We investigate time-space tradeoffs for traversing undirected graphs, using a variety of structured models that are all variants of Cook and Rackoff's “Jumping Automata for Graphs. ” Our strongest tradeoff is a quadratic lower bound on the product of time and space for graph traversal. For example, achieving linear time requires linear space, implying that depth-first search is optimal. Since our bound in fact applies to nondeterministic algorithms fornonconnectivity, it also implies that closure under complementation of nondeterministic space-bounded complexity classes is achieved only at the expense of increased time. To demonstrate that these structured models are realistic, we also investigate their power. In addition to admitting well known algorithms such as depth-first search and random walk, we show that one simple variant of this model is nearly as powerful as a Turing machine. Specifically, for general undirected graph problems, it can simulate a Turing machine with only a constant factor increase in space and a polynomial factor increase in time.

Details DOI

FOCS Conference 1994 Conference Paper

Motion Planning on a Graph (Extended Abstract)

  • Christos H. Papadimitriou
  • Prabhakar Raghavan
  • Madhu Sudan 0001
  • Hisao Tamaki

We are given a connected, undirected graph G on n vertices. There is a mobile robot on one of the vertices; this vertex is labeled s. Each of several other vertices contains a single movable obstacle. The robot and the obstacles may only reside at vertices, although they may be moved across edges. A vertex may never contain more than one object (robot/obstacle). In one step, we may move either the robot or one of the obstacles from its current position /spl upsi/ to a vacant vertex adjacent to v. Our goal is to move the robot to a designated vertex t using the smallest number of steps possible. The problem is a simple abstraction of a robot motion planning problem, with the geometry replaced by the adjacencies in the graph. We point out its connections to robot motion planning. We study its complexity, giving exact and approximate algorithms for several cases. >

Details

FOCS Conference 1992 Conference Paper

A Theory of Wormhole Routing in Parallel Computers (Extended Abstract)

  • Sergio A. Felperin
  • Prabhakar Raghavan
  • Eli Upfal

Virtually all theoretical work on message routing in parallel computers has dwelt on packet routing: messages are conveyed as packets, an entire packet can reside at a node of the network, and a packet is sent from the queue of one node to the queue of another node until its reaches its destination. The current trend in multicomputer architecture, however, is to use wormhole routing. In wormhole routing a message is transmitted as a contiguous stream of bits, physically occupying a sequence of nodes/edges in the network. Thus, a message resembles a worm burrowing through the network. The authors give theoretical analyses of simple wormhole routing algorithms, showing them to be nearly optimal for butterfly and mesh connected networks. The analysis requires initial random delays in injecting messages to the network. They report simulation results suggesting that the idea of random initial delays is not only useful for theoretical analysis but may actually improve the performance of wormhole routing algorithms. >

Details

FOCS Conference 1992 Conference Paper

Exact Analysis of Hot-Potato Routing (Extended Abstract)

  • Uriel Feige
  • Prabhakar Raghavan

The authors consider a form of packet routing known as hot potato routing or deflection routing. Its striking feature is that there are no buffers at intermediate nodes. Thus packets are always moving (possibly in the 'wrong' direction), giving rise to the term 'hot potato'. They give a simple deterministic algorithm that on a n*n torus will route a random instance in 2n+O(log n) steps with high probability. They add random delays to this algorithm so that it solves the permutation routing problem on the torus in 9n steps with high probability, on every instance. On a hypercube with N=2/sup n/ nodes, they give a simple deterministic algorithm that will route a random instance in O(n) steps with high probability. Various other results are discussed. >

Details

TCS Journal 1992 Journal Article

Fast geometric approximation techniques and geometric embedding problems

  • Marshall W. Bern
  • Howard J. Karloff
  • Prabhakar Raghavan
  • Baruch Schieber

Given an undirected n-vertex graph G and a set of n points in R d, we wish to embed the vertices of G onto the points so as to minimize the total embedded edge length. Important special cases of this geometric embedding problem as those in which G is a binary tree, a cycle, or a star. We give fast approximation algorithms for embedding these graphs on the line and in the plane in several metrics. Our principal techniques are: a notion of “approximate geometric sorting” that can be computed in linear time, and fast approximation schemes for the minimum spanning tree problem in the plane. We expect that these approximation techniques can be applied to many geometric problems besides the embedding problem. We give the example of approximating the convex hull of a set of points in the plane.

Details DOI

FOCS Conference 1992 Conference Paper

Markov Paging (Extended Abstract)

  • Anna R. Karlin
  • Steven J. Phillips
  • Prabhakar Raghavan

This paper considers the problem of paging under the assumption that the sequence of pages accessed is generated by a Markov chain. The authors use this model to study the fault-rate of paging algorithms, a quantity of interest to practitioners. They first draw on the theory of Markov decision processes to characterize the paging algorithm that achieves optimal fault-rate on any Markov chain. They address the problem of efficiently devising a paging strategy with low fault-rate for a given Markov chain. They show that a number of intuitively good approaches fail. Their main result is an efficient procedure that, on any Markov chain, will give a paging algorithm with fault-rate at most a constant times optimal. Their techniques also show that some algorithms that do poorly in practice fail in the Markov setting, despite known (good) performance guarantees when the requests are generated independently from a probability distribution. >

Details

FOCS Conference 1990 Conference Paper

Asymptotically Tight Bounds for Computing with Faulty Arrays of Processors (Extended Abstract)

  • Christos Kaklamanis
  • Anna R. Karlin
  • Frank Thomson Leighton
  • Victor Milenkovic
  • Prabhakar Raghavan
  • Satish Rao
  • Clark D. Thompson
  • A. Tsantilas

The computational power of 2-D and 3-D processor arrays that contain a potentially large number of faults is analyzed. Both a random and a worst-case fault model are considered, and it is proved that in either scenario low-dimensional arrays are surprisingly fault tolerant. It is also shown how to route, sort, and perform systolic algorithms for problems such as matrix multiplication in optimal time on faulty arrays. In many cases, the running time is the same as if there were no faults in the array (up to constant factors). On the negative side, it is shown that any constant congestion embedding of an n*n fault-free array on an n*n array with Theta (n/sup 2/) random faults (or Theta (log n) worst-case faults) requires dilation Theta (log n). For 3-D arrays, knot theory is used to prove that the required dilation is Omega ( square root log n). >

Details

FOCS Conference 1990 Conference Paper

Time-Space Tradeoffs for Undirected Graph Traversal

  • Paul Beame
  • Allan Borodin
  • Prabhakar Raghavan
  • Walter L. Ruzzo
  • Martin Tompa

Time-space tradeoffs for traversing undirected graphs are proved. One of these tradeoffs is a quadratic lower bound on a deterministic model that closely matches the probabilistic upper bound of A. Z. Broder et al. (1989). The models used are variants of S. A. Cook and C. W. Rackoff's (1980) jumping automata for graphs. Some open problems are stated. >

Details

I&C Journal 1989 Journal Article

Parallei graph algorithms that are efficient on average

  • Don Coppersmith
  • Prabhakar Raghavan
  • Martin Tompa

The following three problems concerning random graphs can be solved in (logn) O(1)expected time using linearly many processors: (1) finding the lexicographically first maximal independent set, (2) coloring the vertices using a number of colors that is almost surely within twice the chromatic number, and (3) finding a Hamiltonian circuit.

Details DOI

STOC Conference 1989 Conference Paper

Trading Space for Time in Undirected s-t Connectivity

  • Andrei Z. Broder
  • Anna R. Karlin
  • Prabhakar Raghavan
  • Eli Upfal

Aleliunas et al. [1] posed the following question: “The reachability problem for undirected graphs can be solved in logspace and O ( mn ) time [ m is the number of edges and n is the number of vertices] by a probabilistic algorithm that simulates a random walk, or in linear time and space by a conventional deterministic graph traversal algorithm. Is there a spectrum of time-space trade-offs between these extremes?” We answer this question in the affirmative for linear-sized graphs by presenting an algorithm which is faster than the random walk by a factor essentially proportional to the size of its workspace. For denser graphs, the algorithm is faster than the random walk but the speed-up factor is smaller.

Details

FOCS Conference 1987 Conference Paper

Parallel Graph Algorithms that Are Efficient on Average

  • Don Coppersmith
  • Prabhakar Raghavan
  • Martin Tompa

The following three problems concerning random graphs can be solved in (log n)O(1) expected time using linearly many processors: (1) finding the lexicographically first maximal independent set, (2) coloring the vertices using a number of colors that is almost surely within twice the chromatic number, and (3) finding a Hamiltonian circuit.

Details

FOCS Conference 1986 Conference Paper

Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs

  • Prabhakar Raghavan

We consider the problem of approximating an integer program by first solving its relaxation linear program and "rounding" the resulting solution. For several packing problems, we prove probabilistically that there exists an integer solution close to the optimum of the relaxation solution. We then develop a methodology for converting such a probabilistic existence proof to a deterministic approximation algorithm. The methodology mimics the existence proof in a very strong sense.

Details
v2026.09.13