Prabhakar Raghavan has given a Keynote Talk at The ACM Web Conference 2022 on Wednesday 27th April 2022. This paper provides a summary of the topics he addressed during his talk.

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.

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 a more nuanced model for web graphs and show that it does exhibit compressibility, in addition to previously modeled web graph properties.

User modeling on the Web has rested on the fundamental assumption of Markovian behavior --- a user's next action depends only on her current state, and not the history leading up to the current state. This forms the underpinning of PageRank web ranking, as well as a number of techniques for targeting advertising to users. In this work we examine the validity of this assumption, using data from a number of Web settings. Our main result invokes statistical order estimation tests for Markov chains to establish that Web users are not, in fact, Markovian. We study the extent to which the Markovian assumption is invalid, and derive a number of avenues for further research.

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(log3/2n) 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.

Classic search engine results are presented as an ordered list of documents and the problem of presentation trivially reduces to ordering documents by their scores. This is because users scan a list presentation from top to bottom. This leads to natural list optimization measures such as the discounted cumulative gain (DCG) and the rank-biased precision (RBP).

A strong query for a target document with respect to an index is the smallest query for which the target document is returned by the index as the top result for the query. The strong query problem was first studied more than a decade ago in the context of measuring search engine overlap. Despite its simple-to-state nature and its longevity in the field, this problem has not been sufficiently addressed in a formal manner.

Back in the heady days of 1999 and WWW8 (Toronto) we held a panel titled "Finding Anything in the Billion Page Web: Are Algorithms the Key?" In retrospect the answer to this question seems laughably obvious - the search industry has burgeoned on a foundation of algorithms, cloud computing and machine learning. As we move into the second decade of this millennium, we are confronted with a dizzying array of new paradigms for finding content, including social networks and location-based search and advertising. This panel pulls together senior experts from academia and the major search principals to debate whether search will continue to look anything like the 2-keywords-give-10-blue-links paradigm that Google has popularized. What do emerging approaches and paradigms - natural language search, social search, location-based search - mean for the future of search in general?

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.

Motivated by structural properties of the Web graph that support efficient data structures for in memory adjacency queries, we study the extent to which a large network can be compressed. Boldi and Vigna (WWW 2004), showed that Web graphs can be compressed down to three bits of storage per edge; we study the compressibility of social networks where again adjacency queries are a fundamental primitive. To this end, we propose simple combinatorial formulations that encapsulate efficient compressibility of graphs. We show that some of the problems are NP-hard yet admit effective heuristics, some of which can exploit properties of social networks such as link reciprocity. Our extensive experiments show that social networks and the Web graph exhibit vastly different compressibility characteristics.

We study an online job scheduling problem motivated by storyboarding in web advertising, where an advertiser derives value from uninterrupted sequential access to a user surfing the web. The user ceases to browse with probability 1 – β at each step, independently. Stories (jobs) arrive online; job s has length ℓs and per-unit value vs. A value vs is obtained for every unit of the job that is scheduled consecutively without interruption, discounted for the time at which it is scheduled. Jobs can be preempted, but no further value can be derived from the residual unscheduled units of the job. We seek an online algorithm whose total reward is competitive against that of the offline scheduler that knows all jobs in advance. We consider two models based on the maximum delay that can be allowed between the arrival and scheduling of a job. In the first, a job can be scheduled anytime after its arrival; in the second a job is lost unless scheduled immediately upon arrival, preempting a currently running job if needed. The two settings correspond to two natural models of how long an advertiser retains interest in a relevant user. We show that there is, in fact, a sharp separation between what an online scheduler can achieve in these two settings. In the first setting with no deadlines, we give a natural deterministic algorithm with a constant competitive ratio against the offline scheduler. In contrast, we show that in the sharp deadline setting, no (deterministic or randomized) online algorithm can achieve better than a polylogarithmic ratio.

Web search engines use indexes to efficiently retrieve pages containing specified query terms, as well as pages linking to specified pages. The problem of compressed indexes that permit such fast retrieval has a long history. We consider the problem: assuming that the terms in (or links to) a page are generated from a probability distribution, how well compactly can we build such indexes that allow fast retrieval? Of particular interest is the case when the probability distribution is Zipfian (or a similar power law), since these are the distributions that arise on the web. We obtain sharp bounds on the space requirement of Boolean indexes for text documents that follow Zipf's law. In the process we develop a general technique that applies to any probability distribution, not necessarily a power law; this is the first analysis of compression in indexes under arbitrary distributions. Our bounds lead to quantitative versions of rules of thumb that are folklore in indexing. Our experiments on several document collections show that the distribution of terms appears to follow a double-Pareto law rather than Zipf's law. Despite widely varying sets of documents, the index sizes observed in the experiments conform well to our theoretical predictions.

In scarcely a decade, web search has gone from simply scaling traditional information retrieval, to a groundswell of new opportunities that are changing marketing as we know it. In this lecture, we begin by reviewing the progress, pointing out that web search is no longer a purely computer sceince problem. We then hint at the role of other disciplines in this ongoing revolution and a number of directions for research.

Finding near(est) neighbors is a classic, difficult problem in data management and retrieval, with applications in text and image search,in finding similar objects and matching patterns. Here we study cluster pruning, an extremely simple randomized technique. During preprocessing we randomly choose a subset of data points to be leaders the remaining data points are partitioned by which leader is the closest. For query processing, we find the leader(s) closest to the query point. We then seek the nearest neighbors for the query point among only the points in the clusters of the closest leader(s). Recursion may be used in both preprocessing and in search. Such schemes seek approximate nearest neighbors that are "almost as good" as the nearest neighbors. How good are these approximations and how much do they save in computation.

We consider the problem of visualizing the evolution of tags within the Flickr (flickr.com) online image sharing community. Any user of the Flickr service may append a tag to any photo in the system. Over the past year, users have on average added over a million tags each week. Understanding the evolution of these tags over time is therefore a challenging task. We present a new approach based on a characterization of the most interesting tags associated with a sliding interval of time. An animation provided via Flash in a Web browser allows the user to observe and interact with the interesting tags as they evolve over time. New algorithms and data structures are required to support the efficient generation of this visualization. We combine a novel solution to an interval covering problem with extensions to previous work on score aggregation in order to create an efficient backend system capable of producing visualizations at arbitrary scales on this large dataset in real time.

Web search has emerged from being a starting point for exploring the web, to being a proving ranking algorithms and large-scale distributed systems, to its current form in which it is a fast-growing advertising medium. This talk reviews the background of web search, the finally its emerging prospects and technical directions including ubiquitous access across mobile devices. Along the way, we also discuss challenges arising in using the web as an advertising medium.

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.

We consider the problem of visualizing the evolution of tags within the Flickr (flickr.com) online image sharing community. Any user of the Flickr service may append a tag to any photo in the system. Over the past year, users have on average added over a million tags each week. Understanding the evolution of these tags over time is therefore a challenging task. We present a new approach based on a characterization of the most interesting tags associated with a sliding interval of time. An animation provided via Flash in a web browser allows the user to observe and interact with the interesting tags as they evolve over time.New algorithms and data structures are required to support the efficient generation of this visualization. We combine a novel solution to an interval covering problem with extensions to previous work on score aggregation in order to create an efficient backend system capable of producing visualizations at arbitrary scales on this large dataset in real time.

This article describes the CLEVER search system developed at the IBM Almaden Research Center. We present a detailed and unified exposition of the various algorithmic components that make up the system, and then present results from two user studies.

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.

Latent Semantic Indexing is a classical method to produce optimal low-rank approximations of a term-document matrix. However, in the context of a particular query distribution, the approximation thus produced need not be optimal. We propose VLSI, a new query-dependent (or "variable") low-rank approximation that minimizes approximation error for any specified query distribution. With this tool, it is possible to tailor the LSI technique to particular settings, often resulting in vastly improved approximations at much lower dimensionality. We validate this method via a series of experiments on classical corpora, showing that VLSI typically performs similarly to LSI with an order of magnitude fewer dimensions.

We propose a notion of incentive networks, modeling online settings in which multiple participants in a network help each other find information. Within this general setting, we study query incentive networks, a natural abstraction of question-answering systems with rewards for finding answers. We analyze strategic behavior in such networks and under a simple model of networks, show that the Nash equilibrium for participants' strategies exhibits an unexpected threshold phenomenon.

In this talk we look at the convergence of three text-centric areas: entity extraction, semi-structured querying and the integration of search results; we view these in the context of text-centric XML applications. The main focus of the talk will be on text in XML querying and some recent work in approaching it from the perspective of information retrieval.

A (directed) network of people connected by ratings or trust scores, and a model for propagating those trust scores, is a fundamental building block in many of today's most successful e-commerce and recommendation systems. We develop a framework of trust propagation schemes, each of which may be appropriate in certain circumstances, and evaluate the schemes on a large trust network consisting of 800K trust scores expressed among 130K people. We show that a small number of expressed trusts/distrust per individual allows us to predict trust between any two people in the system with high accuracy. Our work appears to be the first to incorporate distrust in a computational trust propagation setting.

It is increasingly common for users to interact with the web using a number of di#erent aliases. This trend is a doubleedged sword. On one hand, it is a fundamental building block in approaches to online privacy. On the other hand, there are economic and social consequences to allowing each user an arbitrary number of free aliases. Thus, there is great interest in understanding the fundamental issues in obscuring the identities behind aliases.

We study a novel genre of optimization problems, which we call segmentation problems , motivated in part by certain aspects of clustering and data mining. For any classical optimization problem, the corresponding segmentation problem seeks to partition a set of cost vectors into several segments , so that the overall cost is optimized. We focus on two natural and interesting (but MAXSNP-complete) problems in this class, the hypercube segmentation problem and the catalog segmentation problem, and present approximation algorithms for them. We also present a general greedy scheme, which can be specialized to approximate any segmentation problem.

We present SETS, an architecture for efficient search in peer-to-peer networks, building upon ideas drawn from machine learning and social network theory. The key idea is to arrange participating sites in a topic-segmented overlay topology in which most connections are short-distance, connecting pairs of sites with similar content. Topically focused sets of sites are then joined together into a single network by long-distance links. Queries are matched and routed to only the topically closest regions. We discuss a variety of design issues and tradeoffs that an implementor of SETS would face. We show that SETS is efficient in network traffic and query processing load.

We propose two new tools to address the evolution of hyperlinked corpora. First, we define time graphs to extend the traditional notion of an evolving directed graph, capturing link creation as a point phenomenon in time. Second, we develop definitions and algorithms for time-dense community tracking, to crystallize the notion of community evolution. We develop these tools in the context of Blogspace , the space of weblogs (or blogs). Our study involves approximately 750K links among 25K blogs. We create a time graph on these blogs by an automatic analysis of their internal time stamps. We then study the evolution of connected component structure and microscopic community structure in this time graph. We show that Blogspace underwent a transition behavior around the end of 2001, and has been rapidly expanding over the past year, not just in metrics of scale, but also in metrics of community structure and connectedness. This expansion shows no sign of abating, although measures of connectedness must plateau within two years. By randomizing link destinations in Blogspace, but retaining sources and timestamps, we introduce a concept of randomized Blogspace . Herein, we observe similar evolution of a giant component, but no corresponding increase in community structure. Having demonstrated the formation of micro-communities over time, we then turn to the ongoing activity within active communities. We extend recent work of Kleinberg [11] to discover dense periods of "bursty" intra-community link creation.

No abstract available.

Peer-to-peer (P2P) computing has emerged as a significant paradigm for providing distributed services, in particular search and data sharing. 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 partitioning into disconnected pieces separated by choke points with inadequate bandwidth. We propose a protocol for participants to build P2P networks in a distributed fashion, and prove that it results in connected networks of constant degree and logarithmic diameter. These properties are crucial for efficient search and data exchange. An important feature of our protocol is that it operates without global knowledge of all the nodes in the network.

Verity Inc. has developed a comprehensive suite of tools for accurately and efficiently organizing enterprise content which involves four basic steps: (i) creating taxonomies, (ii) building classification models, (iii) populating taxonomies with documents, and (iv) deploying populated taxonomies in enterprise portals. A taxonomy is a hierarchical representation of categories. A taxonomy provides a navigation structure for exploring and understanding the underlying corpus without sifting through a huge volume of documents. Thematic Mapping automatically discovers a concept tree from a corpus of unstructured documents and assigns meaningful labels to concepts based on a semantic network. Integrating with Verity Intelligent Classifier's user-friendly GUI, a user can drill down a concept tree for navigation, perform a conceptual search to retrieve documents pertaining to a concept, build a taxonomy from the concept tree, as well as edit a taxonomy to tailor it into various views (customized taxonomies) of the same corpus. Classification rules can be generated automatically from concepts. These classification rules can be used for populating documents into the taxonomy.

Mining large-scale text corpora is an essential step in extracting the key themes in a corpus. We motivate a quantitative measure for significant associations through the distributions of pairs and triplets of co-occurring words. We consider the algorithmic problem of efficiently enumerating such significant associations and present pruning algorithms for these problems, with theoretical as well as empirical analyses. Our algorithms make use of two novel mining methods: (1) matrix mining, and (2) shortened documents. We present evidence from a diverse set of documents that our measure does in fact elicit interesting co-occurrences.

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.

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.

We consider packet routing when packets are injected continuously into a network. We develop an adversarial theory of queuing aimed at addressing some of the restrictions inherent in probabilistic analysis and queuing theory based on time-invariant stochastic generation. We examine the stability of queuing networks and policies when the arrival process is adversarial, and provide some preliminary results in this direction. Our approach sheds light on various queuing policies in simple networks, and paves the way for a systematic study of queuing with few or no probabilistic assumptions.

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.

We study the problem of auditing databases which support statistical sum queries to protect the security of sensitive information; we focus on the special case in which the sensitive information is Boolean. Principles and techniques developed for the security of statistical database in the case of continuous attributes do not apply here. We prove certain strong complexity results suggesting that there is no general efficient solution for the auditing problem in this case. We propose two efficient algorithms: The first is applicable when the sum queries are one-dimensional range queries (we prove that the problem is NP-hard even in the two-dimensional case). The second is an approximate algorithm that maintains security, although it may be too restrictive. Finally, we consider a “dual” variant, with continuous data but an aggregate function that is combinatorial in nature. Specifically, we provide algorithms for two natural definitions of the auditing condition when the aggregate function is MAX.

The pages and hyperlinks of the World-Wide Web may be viewed as nodes and edges in a directed graph. This graph has about a billion nodes today, several billion links, and appears to grow exponentially with time. There are many reasons—mathematical, sociological, and commercial—for studying the evolution of this graph. We first review a set of algorithms that operate on the Web graph, addressing problems from Web search, automatic community discovery, and classification. We then recall a number of measurements and properties of the Web graph. Noting that traditional random graph models do not explain these observations, we propose a new family of random graph models.

We consider a class of problems in which an algorithm seeks to compute a function f over a set of n inputs, where each input has an associated price. The algorithm queries inputs sequentially, trying to learn the value of the function for the minimum cost. We apply the competitive analysis of algorithms to this framework, designing algorithms that incur large cost only when the cost of the cheapest "proof" for the value of f is also large. We provide algorithms that achieve the optimal competitive ratio for functions that include arbitrary Boolean AND/OR trees, and for the problem of searching in a sorted array. We also investigate a model for pricing in this framework, constructing a set of prices for any AND/OR tree that satisfies a very strong type of equilibrium property.

We introduce backoff processes, an idealized stochastic model of browsing on the world-wide web, which incorporates both hyperlink traversals and use of the “back button. ” With some probability the next state is generated by a distribution over out-edges from the current state, as in a traditional Markov chain. With the remaining probability, however, the next state is generated by clicking on the back button, and returning to the state from which the current state was entered by a “forward move”. Repeated clicks on the back button require access to increasingly distant history. We show that this process has fascinating similarities to and differences from Markov chains. In particular, we prove that like Markov chains, backoff processes always have a limit distribution, and we give algorithms to compute this distribution. Unlike Markov chains, the limit distribution may depend on the start state.

This paper considers the problem of paging under the assumption that the sequence of pages accessed is generated by a Markov chain. We use this model to study the fault-rate of paging algorithms. We first draw on the theory of Markov decision processes to characterize the paging algorithm that achieves optimal fault-rate on any Markov chain. Next, we address the problem of devising a paging strategy with low fault-rate for a given Markov chain. We show that a number of intuitive approaches fail. Our main result is a polynomial-time procedure that, on any Markov chain, will give a paging algorithm with fault-rate at most a constant times optimal. Our techniques show also 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.

Consider two user populations, of which one is targered and the other is not.Users in the targeted population follow a Markov chain on a space of n states.The untargeted population follows another Markov chain, also defined on the same set of n states.Each time a user arrives at a state, he/she is presented with information appropriate for the targeted population (an advertisement, or a recommendation) with some probability.Presenting the advertisement incurs a cost.Notice that while the revenue grows in proportion to the flow of targeted users through the state, the cost grows in proportion to the total flow (targeted and untargeted) through the state.How can we compute the best advertisement policy?The world-wide web is a natural setting for such a problem.Internet service providers have trail information for building such Markovian user models where states correspond to pages on the web.In this paper we study the simple problem above, as well as the variants with multiple targetable segments.In some settings the policy need not be a static probability distribution on states.Instead, we can dynamically vary the policy based on the user's path through the states.

We prove a time-space tradeoff for traversing undirected graphs, using a structured model that is a nonjumping variant of Cook and Rackoff's "jumping automata for graphs."

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.

Speculative execution of code is becoming a key technique for enhancing the performance of pipeline processors. We study schemes that predict the execution path of a program based on the history of branch executions. Building on previous work, we present a model for analyzing the effective speedup from pipelining using various schemes for speculative execution. We follow this with stochastic analyses of various speculative execution schemes. Finally, we conclude with simulations covering several of the settings we study.

Article Free Access Share on Latent semantic indexing: a probabilistic analysis Authors: Christos H. Papadimitriou Computer Science Division, U. C. Berkeley Computer Science Division, U. C. BerkeleyView Profile , Hisao Tamaki Computer Science Department, Meiji University Computer Science Department, Meiji UniversityView Profile , Prabhakar Raghavan IBM Almaden Research Center IBM Almaden Research CenterView Profile , Santosh Vempala Department of Mathematics, M.I.T. Department of Mathematics, M.I.T.View Profile Authors Info & Claims PODS '98: Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systemsMay 1998 Pages 159–168https://doi.org/10.1145/275487.275505Published:01 May 1998Publication History 277citation2,760DownloadsMetricsTotal Citations277Total Downloads2,760Last 12 Months261Last 6 weeks43 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Data mining applications place special requirements on clustering algorithms including: the ability to find clusters embedded in subspaces of high dimensional data, scalability, end-user comprehensibility of the results, non-presumption of any canonical data distribution, and insensitivity to the order of input records. We present CLIQUE, a clustering algorithm that satisfies each of these requirements. CLIQUE identifies dense clusters in subspaces of maximum dimensionality. It generates cluster descriptions in the form of DNF expressions that are minimized for ease of comprehension. It produces identical results irrespective of the order in which input records are presented and does not presume any specific mathematical form for data distribution. Through experiments, we show that CLIQUE efficiently finds accurate clusters in large high dimensional datasets. 1 Introduction Clustering is a descriptive task that seeks to identify homogeneous groups of objects based on the values of th...

Article Approximation schemes for Euclidean k-medians and related problems Share on Authors: Sanjeev Arora Princeton University Princeton UniversityView Profile , Prabhakar Raghavan IBM Almaden Research Center, 650 Harry Road, San Jose CA IBM Almaden Research Center, 650 Harry Road, San Jose CAView Profile , Satish Rao NEC Research Institute, Princeton, NJ NEC Research Institute, Princeton, NJView Profile Authors Info & Claims STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computingMay 1998 Pages 106–113https://doi.org/10.1145/276698.276718Published:23 May 1998 210citation1,443DownloadsMetricsTotal Citations210Total Downloads1,443Last 12 Months66Last 6 weeks10 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Article Segmentation problems Share on Authors: Jon Kleinberg Department of Computer Science, Cornell University, Ithaca, NY Department of Computer Science, Cornell University, Ithaca, NYView Profile , Christos Papadimitriou Computer Science Division, Soda Hall, UC Berkeley, CA Computer Science Division, Soda Hall, UC Berkeley, CAView Profile , Prabhakar Raghavan IBM Almaden Research Center, 650 Harry Road, San Jose, CA IBM Almaden Research Center, 650 Harry Road, San Jose, CAView Profile Authors Info & Claims STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computingMay 1998 Pages 473–482https://doi.org/10.1145/276698.276860Online:23 May 1998Publication History 58citation883DownloadsMetricsTotal Citations58Total Downloads883Last 12 Months32Last 6 weeks8 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The subject of this paper is the analysis of a randomized preprocessing scheme that has been used for query processing in robot path planning. The attractiveness of the scheme stems from its general applicability to virtually any path-planning problem, and its empirically observed success. In this paper we initiate a theoretical basis for explaining this empirical success. Under a simple assumption about the configuration space, we show that it is possible to perform preprocessing following which queries can be answered quickly. En route, we consider related problems on graph connectivity in the evasiveness model and art-gallery theorems.

We study contention resolution protocols under a stochastic model of continuous request generation from a set of contenders. The performance of such a protocol is characterized by two parameters: the maximum arrival rate for which the protocol is stable and the expected delay of a request from arrival to service. Known solutions are either unstable for any constant injection rate or have at least polynomial (in the number of contenders) expected delay. Our main contribution is a protocol that is stable for a constant injection rate, while achieving logarithmic expected delay. We extend our results to the case of multiple servers, with each request being targeted for a specific server. This is related to the optically connected parallel computer (or OCPC) model. Finally, we prove a lower bound showing that long delays are inevitable in a class of protocols including backoff-style protocols, if the arrival rate is large enough (but still smaller than 1).

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.

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.

We consider locality-preserving hashing --- in which adjacent points in the domain are mapped to adjacent or nearlyadjacent points in the range --- when the domain is a d- dimensional cube. This problem has applications to highdimensional search and multimedia indexing. We show that simple and natural classes of hash functions are provably good for this problem. We complement this with lower bounds suggesting that our results are essentially the best possible. 1 Introduction In a recent paper, Linial and Sasson [21] proved the following theorem about hash functions: Theorem 1 There exists a family G of functions from an integer line [1; : : : ; U ] to [1; : : : ; R] and a constant C such that for any S ae [1; : : : ; U ] with jSj C p R: ffl Prf2G(f jS is one to one) 1 2 ffl all f 2 G are non-expansive, i.e., for any p; q 2 U d(f(p);f(q)) d(p; q). The family G contains O(jU j) functions, each of which is computable in O(1) operations. Their result gives a family of hash fu...

We study the extent to which complex hardware can speed up routing. Specifically, we consider the following questions. How much does adaptive routing improve over oblivious routing? How much does randomness help? How does it help if each node can have a large number of neighbors? What benefit is available if a node can send packets to several neighbors within a single time step? Some of these features require complex networking hardware, and it is thus important to investigate whether the performance justifies the investment. By varying these hardware parameters, we obtain a hierarchy of time bounds for worst-case permutation routing.

Consider a robot that has to travel from a start location s to a target t in an environment with opaque obstacles that lie in its way. The robot always knows its current absolute position and that of the target. It does not, however, know the positions and extents of the obstacles in advance; rather, it finds out about obstacles as it encounters them. We compare the distance walked by the robot in going from s to t to the length of the shortest (obstacle-free) path between s and t in the scene. We describe and analyze robot strategies that minimize this ratio for different kinds of scenes. In particular, we consider the cases of rectangular obstacles aligned with the axes, rectangular obstacles in more general orientations, and wider classes of convex bodies both in two and three dimensions. For many of these situations, our algorithms are optimal up to constant factors. We study scenes with nonconvex obstacles, which are related to the study of maze traversal. We also show scenes where randomized algorithms are provably better than deterministic algorithms.

We consider the following problem: given a simple polygon ${\cal P}$ and a star-shaped polygon ${\cal V}$, find a point (or the set of points) in ${\cal P}$ from which the portion of ${\cal P}$ that is visible is translation-congruent to ${\cal V}$. The problem arises in the localization of robots equipped with a range finder and a compass---${\cal P}$ is a map of a known environment, ${\cal V}$ is the portion visible from the robot's position, and the robot must use this information to determine its position in the map. We give a scheme that preprocesses ${\cal P}$ so that any subsequent query ${\cal V}$ is answered in optimal time O(m + log n + A), where m and n are the number of vertices in ${\cal V}$ and ${\cal P}$ and A is the number of points in ${\cal P}$ that are valid answers (the output size). Our technique uses O(n5) space and preprocessing in the worst case; within certain limits, we can trade off smoothly between the query time and the preprocessing time and space. In the process of solving this problem, we also devise a data structure for output-sensitive determination of the visibility polygon of a query point inside a polygon ${\cal P}$. We then consider a variant of the localization problem in which there is a maximum distance to which the robot can "see"---this is motivated by practical considerations, and we outline a similar solution for this case. We finally show that a single localization query ${\cal V}$ can be answered in time O(mn) with no preprocessing.

Abstract The subject of this paper is the design and analysis of Monte Carlo algorithms for two basic matching techniques used in model-based recognition: alignment, and geometric hashing. We first give analyses of our Monte Carlo algorithms, showing that they are asymptotically faster than their deterministic counterparts while allowing failure probabilities that are provably very small. We then describe experimental results that bear out this speed-up, suggesting that randomization results in significant improvements in running time. Our theoretical analyses are not the best possible; as a step to remedying this we define a combinatorial measure of self-similarity for point sets, and give an example of its power.

We introduce a new approach to the study of dynamic (or continuous) packet routing, where packets are being continuously injected into a network. Our objective is to study what happens to packet routing under continuous injection as a function of network load, for various queueing policies. Our approach is based on the adversarial generation of packets, so that the results are more robust in that they do not hinge upon particular probabilistic assumptions. In suggesting a new approach to studying a classical phenomenon, it is important to give careful consideration to all the relevant previous work in packet routing, queueing theory and probabilistic analysis. We give a more detailed account of previous work in Appendix A, to permit comparison with our work. Here we summarize the salient features of prior work in order to motivate our model. Most prior work on packet routing has been in the static model in which there is a fixed initial set of packet ro

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. A 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. In this paper we give theoretical analyses of simple wormhole routing algorithms, showing them to be nearly optimal for butterfly and mesh connected networks. Our analysis requires initial random delays in injecting messages to the network. We report simulation results suggesting that the idea of random initial delays may have an impact beyond theoretical analysis.

Article Motion planning for a steering-constrained robot through moderate obstacles Share on Authors: Pankaj K. Agarwal Computer Science Department, Duke University, Box 90129, Durham, NC Computer Science Department, Duke University, Box 90129, Durham, NCView Profile , Prabhakar Raghavan IBM T.J. Watson Research Center, Yorktown Heights, NY IBM T.J. Watson Research Center, Yorktown Heights, NYView Profile , Hisao Tamaki IBM Tokyo Research Laboratory, 1623-14 Shimotsuruma, Yamato-shi, Kanagawa 242, Japan IBM Tokyo Research Laboratory, 1623-14 Shimotsuruma, Yamato-shi, Kanagawa 242, JapanView Profile Authors Info & Claims STOC '95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computingMay 1995 Pages 343–352https://doi.org/10.1145/225058.225158Online:29 May 1995Publication History 35citation649DownloadsMetricsTotal Citations35Total Downloads649Last 12 Months11Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The subject of this paper is the analysis of a randomized preprocessing scheme that has been used for query processing in robot path planning. The attractiveness of the scheme stems from its general applicability to virtually any path-planning problem, and its empirically observed success. In this paper we initiate a theoretical basis for explaining this empirical success. Under a simple assumption about the configuration space, we show that it is possible to perform preprocessing following which queries can be answered quickly. En route, we consider related problems on graph connectivity in the evasiveness model, and art-gallery theorems. Robotics Laboratory, Department of Computer Science, Stanford University, Stanford, CA 94305-2140. Partially supported by ARPA grant N00014-92-J-1809 and ONR grant N00014-94-1-0721. y Department of Computer Science, Stanford University, Stanford, CA 94305-2140. Supported by an Alfred P. Sloan Research Fellowship, an IBM Faculty Development Award,...

We study contention resolution protocols under a stochastic model of continuous request generation from

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.>

We are given a set of points p1;...;pn and a symmetric distance matrix (dij) givingthedistancebetweenpiandpj. Wewishtoconstruct atourthatminimizesPni=1`(i),where`(i)is thelatencyofpi,denedtobethedistance traveledbeforerstvisitingpi.Thisproblem isalsoknownintheliteratureasthedeliveryman problem orthetravelingrepairmanproblem. It arises in a number ofapplicationsincluding disk-head scheduling, and turnsouttobesurprisinglydierentfromthetravelingsalesman problem in character. We give exact and approximate solutions to a number of cases, including a constant-factor approximation algorithm whenever the distance matrix satisfies the triangle inequality.

Communication in all-optical networks requires novel routing paradigms. The high bandwidth of the optic fiber is utilized through wavelengthdivision multiplexing: A single physical optical link can carry several logical signals, provided that they are transmitted on different wavelengths. We study the problem of routing a set of requests (each of which is a pair of nodes to be connected by a path) on sparse networks using a limited number of wavelengths, ensuring that different paths using the same wavelength never use the same physical link. The constraints on the selection of paths and wavelengths depend on the type of photonic switches used in the network. We present efficient routing techniques for the two types of photonic switches that dominate current research in all-optical networks. Our results es- IBM T.J. Watson Research Center, Yorktown. This work was supported in part by grant MDA 97292 -C-0075 from ARPA. y The Weizmann Institute, Israel, and IBM Almaden Research Cente...

Aleliunas et al. [20th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1979, pp. 218–223] posed the following question: “The reachability problem for undirected graphs can be solved in log space 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?” This question is answered in the affirmative for sparse graphs by presentation of an algorithm that is faster than the random walk by a factor essentially proportional to the size of its workspace. For denser graphs, this algorithm is faster than the random walk but the speed-up factor is smaller.

This paper studies the depth of noisy decision trees in which each node gives the wrong answer with some constant probability. In the noisy Boolean decision tree model, tight bounds are given on the number of queries to input variables required to compute threshold functions, the parity function and symmetric functions. In the noisy comparison tree model, tight bounds are given on the number of noisy comparisons for searching, sorting, selection and merging. The paper also studies parallel selection and sorting with noisy comparisons, giving tight bounds for several problems.

We consider deflection routing on the n x n mesh

We study the extent to which complex hardware can speed up routing.Specifically, we consider the following questions.How much does adaptive routing improve over oblivious routing?How much does randomness help?How does it help if each node can have a large number of neighbors?What benefit is available if a node can send packets to several neighbors within a single time step?Some of these features require complex networking

The design and analysis of randomized on-line algorithms are studied.This problem is shown to be closely related to the synthesis of random wdlks on graphs with positive real costs on their edges.A theory is developed for the synthesis of such wdlks, and it is employed to design competitive on-line algorithms.

Randomizedalgorithms are analyzed as if unlimited amounts of perfect randomness were available, while pseudorandom number generation is usually studied from the perspective of cryptographic security or for the statistical properties of the numbers generated.Bach proposed studying the interaction between pseudorandom number generators and randomized algorithms.This paper follows Bach's lead; the authors assume that a (small) random seed is available to start up a simple pseudorandom number generator that is then used for the randomized algorithm.Randomized algorithms are studied for (1) sorting, (2) selection.and (3) obhvious routing in networks.

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.>

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.>

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.>

Consider a robot that has to travel from a start location s to a target t in an environment with opaque obstacles that lie in its way.The robot always knows its current absolute position and that of the target.It does not, however, know the positions and extents of the obstacles in advance; rather, it finds out about obstacles as it encounters them.We compare the distance walked by the robot in going from .s to t to the length of the shortest path between s and t in the scene.We describe sbar]

The Sleator-Tarjan competitive analysis of paging [19] gives us the ability to make strong theoretical statements about the performance of paging algorithms without making probabilistic assumptions on the input.Nevertheless practitioners voice reservations about the model, citing its inability to discern between is that it is more robust than probabilistic analysis, while more practical than worst-case analysis.With these definitions, Sleator and Tarjan showed that no deterministic on-line paging algorithm can achieve a competitiveness less than k, and that a number of algorithms used in practice (including Least Recently Used or LRU and First-In First-Out or FIFO) are kcompetitive and thus optimal by this measure.

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.>

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).>

We study the design and analysis of randomized on-line algorithms.We show that this problem is closely related to the synthesis of random walks on graphs with positive real costs on their edges.

Article Free AccessComputing with unreliable information Authors: U. Feige The Weizmann Institute of Science, Rehovot, Israel and T.J. Watson and Almaden Research Centers The Weizmann Institute of Science, Rehovot, Israel and T.J. Watson and Almaden Research CentersView Profile , D. Peleg The Weizmann Institute of Science, Rehovot, Israel The Weizmann Institute of Science, Rehovot, IsraelView Profile , P. Raghavan IBM T.J. Watson Research Center, Yorktown Heights, NY IBM T.J. Watson Research Center, Yorktown Heights, NYView Profile , E. Upfal IBM Almaden Research Center, San Jose, CA, and The Weizmann Institute of Science, Rehovot, Israel IBM Almaden Research Center, San Jose, CA, and The Weizmann Institute of Science, Rehovot, IsraelView Profile Authors Info & Claims STOC '90: Proceedings of the twenty-second annual ACM symposium on Theory of ComputingApril 1990 Pages 128–137https://doi.org/10.1145/100216.100230Published:01 April 1990Publication History 46citation775DownloadsMetricsTotal Citations46Total Downloads775Last 12 Months69Last 6 weeks8 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Given an undirected n-vertex graph G and a set of n points in Rd, 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 are 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.

Article Robust algorithms for packet routing in a mesh Share on Author: P. Raghavan IBM Research Division, T.J. Watson Research Center, Yorktown Heights, NY IBM Research Division, T.J. Watson Research Center, Yorktown Heights, NYView Profile Authors Info & Claims SPAA '89: Proceedings of the first annual ACM symposium on Parallel algorithms and architecturesMarch 1989 Pages 344–350https://doi.org/10.1145/72935.72972Online:01 March 1989Publication History 15citation134DownloadsMetricsTotal Citations15Total Downloads134Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

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.

View an n-vertex, m-edge undirected graph as an electrical network with unit resistors as edges. We extend known relations between random walks and electrical networks by showing that resistance in this network is intimately connected with the lengths of random walks on the graph. For example, the commute time between two vertices s and t (the expected length of a random walk from s to t and back) is precisely characterized by the effective resistance Rst between s and t: commute time = 2mRst. Additionally, the cover time (the expected length of a random walk visiting all vertices) is characterized by the maximum resistance R in the graph to within a factor of log n: mR ≤ cover time ≤ O (mR log n). For many graphs, the bounds on cover time obtained in this manner are better than those obtained from previous techniques such as the eigenvalues of the adjacency matrix. In particular, using this approach, we improve known bounds on cover times for various classes of graphs, including high-degree graphs, expanders, and multi-dimensional meshes. Moreover, resistance seems to provide an intuitively appealing and tractable approach to these problems.

We study energy consumption in CMOS-style VLSI circuits, where a wire of length / consumes energy Θ(l)when switching. Three model are considered: the uniswitch model where a wire is assumed to switch at most once if the input changes, the multiswitch model which allows the possibility of multiple switches caused by uncontrolled delays, and the clock model which also takes clock distribution energy into account. Previous lower bound results for the uniswitch model applied only to circuits where intermediate data were not encoded (for example, in unary) by using additional wires and area to reduce the energy. We show that such encodings can be useful for adding two n-bit numbers using synchronous Boolean circuits (energy reduction from Θ(n log n) to Ο(n log n/(log log n)), but not for transitive functions such as the cyclic shift of n bits (energy Θ(n2)). For the multiswitch model, we develop layouts that achieve energy close to the uniswitch case for these problems, and show a separation result between the uniswitch and multiswitch models. Finally, some energy-period tradeoffs are shown for the clock model.

Randomized algorithms are analyzed as if unlimited amounts of perfect randomness were available, while pseudorandom number generation is usually studied from the perspective of cryptographic security. Bach recently proposed studying the interaction between pseudorandom number generators and randomized algorithms. We follow Bach's lead; we assume that a (small) random seed is available to start up a simple pseudorandom number generator which is then used for the randomized algorithm. We study randomized algorithms for (1) sorting; (2) selection; and (3) oblivious routing in networks.

We consider the problem of answering a series of on-line queries on a static data set. The conventional approach to such problems involves a preprocessing phase which constructs a data structure with good search behavior. The data structure representing the data set then remains fixed throughout the processing of the queries. Our approach involves dynamic or query-driven structuring of the data set; our algorithm processes the data set only when doing so is required for answering a query. A data structure constructed progressively in this fashion is called a deferred data structure. We develop the notion of deferred data structures by solving the problem of answering membership queries on an ordered set. We obtain a randomized algorithm which achieves asymptotically optimal performance with high probability. We then present optimal deferred data structures for the following problems in the plane: testing convex-hull membership, half-plane intersection queries and fixed-constraint multi-objective linear programming. We also apply the deferred data structuring technique to multi-dimensional dominance query problems.

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.

We consider the problem of answering a series of on-line queries on a static database. The conventional approach to such problems involves a preprocessing phase which constructs a data structure with good search behavior. The data structure is then used to process a series of queries without any further reordering. Our approach involves dynamic or query-driven structuring of the database, i.e. we process the database only when it is required for answering a query. We present optimal algorithms for the following problems in the plane: testing convex hull membership, half-plane intersection queries and fixed-constraint multi-objective linear programming. This technique is also applied to multidimensional dominance query problems.

We propose a language that can be used to describe configuration of rectilinear Steiner trees. Given a set of points in a plane indexed by integer coordinates, the execution of a pattern-description in our language will list a number of Steiner trees spanning the points. The Steiner trees that are produced will be used as input to a linear-program type global router for VLSI gate-arrays [10]. Other applications for our language include routing printed circuit boards and generating Steiner tree configurations for simulated-annealing type global routers [11].

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.

We examine the problem of routing wires on a VLSI chip where the nodes to be connected are arranged in a two-dimensional array. We develop provably good algorithms that find a solution close to the optimal one with high probability. Our approximation algorithms solve the relevant 0-1 integer optimization problems by solving their relaxed versions and then rounding by an interesting probabilistic technique. One of our algorithms, using multicommodity flow, has applications to routing in circuit switching networks.