Arrow Research search

Author name cluster

Eli Upfal

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.

58 papers
2 author rows

Possible papers

58

NeurIPS Conference 2023 Conference Paper

An Adaptive Algorithm for Learning with Unknown Distribution Drift

  • Alessio Mazzetto
  • Eli Upfal

We develop and analyze a general technique for learning with an unknown distribution drift. Given a sequence of independent observations from the last $T$ steps of a drifting distribution, our algorithm agnostically learns a family of functions with respect to the current distribution at time $T$. Unlike previous work, our technique does not require prior knowledge about the magnitude of the drift. Instead, the algorithm adapts to the sample data. Without explicitly estimating the drift, the algorithm learns a family of functions with almost the same error as a learning algorithm that knows the magnitude of the drift in advance. Furthermore, since our algorithm adapts to the data, it can guarantee a better learning error than an algorithm that relies on loose bounds on the drift. We demonstrate the application of our technique in two fundamental learning scenarios: binary classification and linear regression.

PDF Details

ICML Conference 2023 Conference Paper

Nonparametric Density Estimation under Distribution Drift

  • Alessio Mazzetto
  • Eli Upfal

We study nonparametric density estimation in non-stationary drift settings. Given a sequence of independent samples taken from a distribution that gradually changes in time, the goal is to compute the best estimate for the current distribution. We prove tight minimax risk bounds for both discrete and continuous smooth densities, where the minimum is over all possible estimates and the maximum is over all possible distributions that satisfy the drift constraints. Our technique handles a broad class of drift models and generalizes previous results on agnostic learning under drift.

Details

NeurIPS Conference 2022 Conference Paper

Tight Lower Bounds on Worst-Case Guarantees for Zero-Shot Learning with Attributes

  • Alessio Mazzetto
  • Cristina Menghini
  • Andrew Yuan
  • Eli Upfal
  • Stephen Bach

We develop a rigorous mathematical analysis of zero-shot learning with attributes. In this setting, the goal is to label novel classes with no training data, only detectors for attributes and a description of how those attributes are correlated with the target classes, called the class-attribute matrix. We develop the first non-trivial lower bound on the worst-case error of the best map from attributes to classes for this setting, even with perfect attribute detectors. The lower bound characterizes the theoretical intrinsic difficulty of the zero-shot problem based on the available information---the class-attribute matrix---and the bound is practically computable from it. Our lower bound is tight, as we show that we can always find a randomized map from attributes to classes whose expected error is upper bounded by the value of the lower bound. We show that our analysis can be predictive of how standard zero-shot methods behave in practice, including which classes will likely be confused with others.

PDF Details

ICML Conference 2021 Conference Paper

Adversarial Multi Class Learning under Weak Supervision with Performance Guarantees

  • Alessio Mazzetto
  • Cyrus Cousins
  • Dylan Sam
  • Stephen H. Bach
  • Eli Upfal

We develop a rigorous approach for using a set of arbitrarily correlated weak supervision sources in order to solve a multiclass classification task when only a very small set of labeled data is available. Our learning algorithm provably converges to a model that has minimum empirical risk with respect to an adversarial choice over feasible labelings for a set of unlabeled data, where the feasibility of a labeling is computed through constraints defined by rigorously estimated statistics of the weak supervision sources. We show theoretical guarantees for this approach that depend on the information provided by the weak supervision sources. Notably, this method does not require the weak supervision sources to have the same labeling space as the multiclass classification task. We demonstrate the effectiveness of our approach with experiments on various image classification tasks.

Details

NeurIPS Conference 2021 Conference Paper

Fast Doubly-Adaptive MCMC to Estimate the Gibbs Partition Function with Weak Mixing Time Bounds

  • Shahrzad Haddadan
  • Yue Zhuang
  • Cyrus Cousins
  • Eli Upfal

We present a novel method for reducing the computational complexity of rigorously estimating the partition functions of Gibbs (or Boltzmann) distributions, which arise ubiquitously in probabilistic graphical models. A major obstacle to applying the Gibbs distribution in practice is the need to estimate their partition function (normalizing constant). The state of the art in addressing this problem is multi-stage algorithms which consist of a cooling schedule and a mean estimator in each step of the schedule. While the cooling schedule in these algorithms is adaptive, the mean estimate computations use MCMC as a black-box to draw approximately-independent samples. Here we develop a doubly adaptive approach, combining the adaptive cooling schedule with an adaptive MCMC mean estimator, whose number of Markov chain steps adapts dynamically to the underlying chain. Through rigorous theoretical analysis, we prove that our method outperforms the state of the art algorithms in several factors: (1) The computational complexity of our method is smaller; (2) Our method is less sensitive to loose bounds on mixing times, an inherent components in these algorithms; and (3) The improvement obtained by our method is particularly significant in the most challenging regime of high precision estimates. We demonstrate the advantage of our method in experiments run on classic factor graphs, such as voting models and Ising models.

PDF Details

AAMAS Conference 2019 Conference Paper

Learning Simulation-Based Games from Data

  • Enrique Areyan Viqueira
  • Amy Greenwald
  • Cyrus Cousins
  • Eli Upfal

We tackle a fundamental problem in empirical game-theoretic analysis (EGTA), that of learning equilibria of simulation-based games. Such games cannot be described in analytical form; instead, a blackbox simulator can be queried to obtain noisy samples of utilities. Our approach to EGTA is in the spirit of probably approximately correct learning. We design algorithms that learn empirical games, which uniformly approximate the utilities of simulation-based games from finitely many samples. Our methodology learns all the equilibria of simulation-based games, as opposed to a single one.

PDF

TCS Journal 2019 Journal Article

Optimizing static and adaptive probing schedules for rapid event detection

  • Ahmad Mahmoody
  • Eli Upfal

We formulate and study a fundamental search and detection problem, Schedule Optimization, motivated by a variety of real-world applications, ranging from monitoring content changes on the web, social networks, and user activities to detecting failure on large systems with many individual machines. We consider a large system consists of many nodes, where each node has its own rate of generating new events, or items. A monitoring application can probe a small number of nodes at each step, and our goal is to compute a probing schedule that minimizes the expected number of undiscovered items at the system, or equivalently, minimizes the expected time to discover a new item in the system. We study the Schedule Optimization problem both for deterministic and randomized memoryless algorithms. We provide lower bounds on the cost of an optimal schedule and construct close to optimal schedules with rigorous mathematical guarantees.

Details DOI

AAAI Conference 2016 Conference Paper

Reconstructing Hidden Permutations Using the Average-Precision (AP) Correlation Statistic

  • Lorenzo De Stefani
  • Alessandro Epasto
  • Eli Upfal
  • Fabio Vandin

We study the problem of learning probabilistic models for permutations, where the order between highly ranked items in the observed permutations is more reliable (i. e. , consistent in different rankings) than the order between lower ranked items, a typical phenomena observed in many applications such as web search results and product ranking. We introduce and study a variant of the Mallows model where the distribution is a function of the widely used Average-Precision (AP) Correlation statistic, instead of the standard Kendall’s tau distance. We present a generative model for constructing samples from this distribution and prove useful properties of that distribution. Using these properties we develop an efficient algorithm that provably computes an asymptotically unbiased estimate of the center permutation, and a faster algorithm that learns with high probability the hidden central permutation for a wide range of the parameters of the model. We complement our theoretical analysis with extensive experiments showing that unsupervised methods based on our model can precisely identify ground-truth clusters of rankings in real-world data. In particular, when compared to the Kendall’s tau based methods, our methods are less affected by noise in low-rank items.

PDF Details

FOCS Conference 2015 Conference Paper

Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks

  • John Augustine 0001
  • Gopal Pandurangan
  • Peter Robinson 0002
  • Scott T. Roche
  • Eli Upfal

Motivated by the need for designing efficient and robust fully-distributed computation in highly dynamic networks such as Peer-to-Peer (P2P) networks, we study distributed protocols for constructing and maintaining dynamic network topologies with good expansion properties. Our goal is to maintain a sparse (bounded degree) expander topology despite heavy churn (i. e. , Nodes joining and leaving the network continuously over time). We assume that the churn is controlled by an adversary that has complete knowledge and control of what nodes join and leave and at what time and has unlimited computational power, but is oblivious to the random choices made by the algorithm. Our main contribution is a randomized distributed protocol that guarantees with high probability the maintenance of a constant degree graph with high expansion even under continuous high adversarial churn. Our protocol can tolerate a churn rate of up to O(n/polylog(n)) per round (where n is the stable network size). Our protocol is efficient, lightweight, and scalable, and it incurs only O(polylog(n)) overhead for topology maintenance: only polylogarithmic(in n) bits needs to be processed and sent by each node per round and any node's computation cost per round is also polylogarithmic. The given protocol is a fundamental ingredient that is needed for the design of efficient fully-distributed algorithms for solving fundamental distributed computing problems such as agreement, leader election, search, and storage in highly dynamic P2P networks and enables fast and scalable algorithms for these problems that can tolerate a large amount of churn.

Details

TCS Journal 2015 Journal Article

Fast distributed PageRank computation

  • Atish Das Sarma
  • Anisur Rahaman Molla
  • Gopal Pandurangan
  • Eli Upfal

Over the last decade, PageRank has gained importance in a wide range of applications and domains, ever since it first proved to be effective in determining node importance in large graphs (and was a pioneering idea behind Google's search engine). In distributed computing alone, PageRank vector, or more generally random walk based quantities have been used for several different applications ranging from determining important nodes, load balancing, search, and identifying connectivity structures. Surprisingly, however, there has been little work towards designing provably efficient fully-distributed algorithms for computing PageRank. The difficulty is that traditional matrix–vector multiplication style iterative methods may not always adapt well to the distributed setting owing to communication bandwidth restrictions and convergence rates. In this paper, we present fast random walk-based distributed algorithms for computing PageRanks in general graphs and prove strong bounds on the round complexity. We first present a distributed algorithm that takes O ( log ⁡ n / ϵ ) rounds with high probability on any graph (directed or undirected), where n is the network size and ϵ is the reset probability used in the PageRank computation (typically ϵ is a fixed constant). We then present a faster algorithm that takes O ( log ⁡ n / ϵ ) rounds in undirected graphs. Both of the above algorithms are scalable, as each node sends only small (polylog n) number of bits over each edge per round. To the best of our knowledge, these are the first fully distributed algorithms for computing PageRank vector with provably efficient running time.

Details DOI

SODA Conference 2012 Conference Paper

Towards robust and efficient computation in dynamic peer-to-peer networks

  • John Augustine 0001
  • Gopal Pandurangan
  • Peter Robinson 0002
  • Eli Upfal

Motivated by the need for robust and fast distributed computation in highly dynamic Peer-to-Peer (P2P) networks, we study algorithms for the fundamental distributed agreement problem. P2P networks are highly dynamic networks that experience heavy node churn (i. e. , nodes join and leave the network continuously over time). Our goal is to design fast algorithms (running in a small number of rounds) that guarantee, despite high node churn rate, that almost all nodes reach a stable agreement. Our main contributions are randomized distributed algorithms that guarantee stable almost-everywhere agreement with high probability even under high adversarial churn in a polylogarithmic number of rounds. In particular, we present the following results: 1. An O (log n )-round ( n is the stable network size) randomized algorithm that achieves almost-everywhere agreement with high probability under up to linear churn per round (i. e. , ε n, for some small constant ε > 0), assuming that the churn is controlled by an oblivious adversary (that has complete knowledge and control of what nodes join and leave and at what time and has unlimited computational power, but is oblivious to the random choices made by the algorithm). 2. An O (log m log 3 n )-round randomized algorithm that achieves almost-everywhere agreement with high probability under up to ε√ n churn per round (for some small ε > 0), where m is the size of the input value domain, that works even under an adaptive adversary (that also knows the past random choices made by the algorithm). Our algorithms are the first-known, fully-distributed, agreement algorithms that work under highly dynamic settings (i. e. , high churn rates per step). Furthermore, they are localized (i. e. , do not require any global topological knowledge), simple, and easy to implement. These algorithms can serve as building blocks for implementing other non-trivial distributed computing tasks in dynamic P2P networks.

Details

TCS Journal 2011 Journal Article

Sorting and selection on dynamic data

  • Aris Anagnostopoulos
  • Ravi Kumar
  • Mohammad Mahdian
  • Eli Upfal

We formulate and study a new computational model for dynamic data. In this model, the data changes gradually and the goal of an algorithm is to compute the solution to some problem on the data at each time step, under the constraint that it only has limited access to the data each time. As the data is constantly changing and the algorithm might be unaware of these changes, it cannot be expected to always output the exact right solution; we are interested in algorithms that guarantee to output an approximate solution. In particular, we focus on the fundamental problems of sorting and selection, where the true ordering of the elements changes slowly. We provide algorithms with performance close to the optimal in expectation and with high probability.

Details DOI

TCS Journal 2008 Journal Article

Commitment under uncertainty: Two-stage stochastic matching problems

  • Irit Katriel
  • Claire Kenyon-Mathieu
  • Eli Upfal

We define and study two versions of the bipartite matching problem in the framework of two-stage stochastic optimization with recourse. In one version, the uncertainty is in the second stage costs of the edges, and in the other version, the uncertainty is in the set of vertices that needs to be matched. We prove lower bounds, and analyze efficient strategies for both cases. These problems model real-life stochastic integral planning problems, such as commodity trading, reservation systems and scheduling under uncertainty.

Details DOI

NeurIPS Conference 2008 Conference Paper

Mortal Multi-Armed Bandits

  • Deepayan Chakrabarti
  • Ravi Kumar
  • Filip Radlinski
  • Eli Upfal

We formulate and study a new variant of the $k$-armed bandit problem, motivated by e-commerce applications. In our model, arms have (stochastic) lifetime after which they expire. In this setting an algorithm needs to continuously explore new arms, in contrast to the standard $k$-armed bandit model in which arms are available indefinitely and exploration is reduced once an optimal arm is identified with near-certainty. The main motivation for our setting is online-advertising, where ads have limited lifetime due to, for example, the nature of their content and their campaign budget. An algorithm needs to choose among a large collection of ads, more than can be fully explored within the ads' lifetime. We present an optimal algorithm for the state-aware (deterministic reward function) case, and build on this technique to obtain an algorithm for the state-oblivious (stochastic reward function) case. Empirical studies on various reward distributions, including one derived from a real-world ad serving application, show that the proposed algorithms significantly outperform the standard multi-armed bandit approaches applied to these settings.

PDF Details

AAAI Conference 2007 Conference Paper

Propagating Knapsack Constraints in Sublinear Time

  • Irit Katriel
  • Eli Upfal

We develop an efficient incremental version of an existing cost-based filtering algorithm for the knapsack constraint. On a universe of n elements, m invocations of the algorithm require a total of O(n log n+mk log(n/k)) time, where k ≤ n depends on the specific knapsack instance. We show that the expected value of k is significantly smaller than n on several interesting input distributions, hence while keeping the same worst-case complexity, on expectation the new algorithm is faster than the previously best method which runs in amortized linear time. After a theoretical study, we introduce heuristic enhancements and demonstrate the new algorithm’s performance experimentally.

PDF Details

FOCS Conference 2003 Conference Paper

Performance Analysis of Dynamic Network Processes

  • Eli Upfal

The article covers various approaches for modeling and analyzing dynamic processes in networks. Modeling the dynamic performance as a stochastic process, we apply tools from discrete and continuous time Markov processes theory, renewal theory and queuing theory to analyze the long term, steady state performance of the processes. Non-stochastic approaches include adversarial queuing theory, and game theory techniques.

Details

FOCS Conference 2003 Conference Paper

Stability and Efficiency of a Random Local Load Balancing Protocol

  • Aris Anagnostopoulos
  • Adam Kirsch
  • Eli Upfal

We study the long term (steady state) performance of a simple, randomized, local load balancing technique. We assume a system of n processors connected by an arbitrary network topology. Jobs are placed in the processors by a deterministic or randomized adversary. The adversary knows the current and past load distribution in the network and can use this information to place the new tasks in the processors. The adversary can put a number of new jobs in each processor, in each step, as long as the (expected) total number of new jobs arriving at a given step is bounded by /spl lambda/n. A node can execute one job per step, and also participate in one load balancing operation in which it can move tasks to a direct neighbor in the network. In the protocol we analyze here, a node equalizes its load with a random neighbor in the graph. We first study the stability of a system running our load balancing protocol. Clearly, if /spl lambda/ > 1 the system cannot be stable. We show that for any /spl lambda/ < 1, and any connected network topology, the system is stable. When the system is stable, the next performance parameter of interest is the waiting time of jobs. We develop high probability bounds and bounds on the expectation of the waiting time of jobs in terms of the network topology. In particular, if the network is an expander graph the expected wait of a task is O(log n), and the waiting time of a task that enters the network at an arbitrary time is O(log n) with high probability. We contrast these results with the work stealing load balancing protocol, where we show that, in sparse networks, the load in the system and the waiting time can be exponential in the network size.

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

ICAPS Conference 2000 Conference Paper

Computing Global Strategies for Multi-Market Commodity Trading

  • Milos Hauskrecht
  • Luis E. Ortiz
  • Ioannis Tsochantaridis
  • Eli Upfal

The focus of this workis the computationof efficient strategies for commoditytrading in a multi-market environment. In today’s "global economy"commodities are often bought in one location and then sold (right away, or after somestorage period) in different markets. Thus, a trading decision in one location must be based on expectations about future price curves in all other relevant markets, and on current and future storage and transportation costs. Investors try to compute a strategy that maximizesexpected return, usually with somelimitations on assumedrisk. With standard stochastic assumptions on commodity price fluctuations, computingan optimal strategy can be modeled as a Markovdecision process (MDP). However, in general such a formulation does not lead to efficient algorithms. In this work we propose a modelfor representing the multi-market trading problem and showhowto obtain efficient structured algorithms for computingoptimal strategies for a numberof commonlyused trading objective functions (Expected NPV, Mean-Variance, and Value at Risk).

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

IJCAI Conference 1999 Conference Paper

Computing Near Optimal Strategies for Stochastic Investment Planning Problems

  • Milos Haushecht
  • Gopal Pandumngan
  • Eli Upfal

We present efficient techniques for computing near optimal strategies for a class of stochastic commodity trading problems modeled as Markov decision processes (MDPs). The process has a continuous state space and a large action space and cannot be solved efficiently by standard dynamic programming methods. We exploit structural properties of the process, and combine it with Monte- Carlo estimation techniques to obtain novel and efficient algorithms that closely approximate the optimal strategies.

PDF

FOCS Conference 1999 Conference Paper

Reducing Network Congestion and Blocking Probability Through Balanced Allocation

  • Malwina J. Luczak
  • Eli Upfal

We compare the performance of a variant of the standard dynamic alternative routing (DAR) technique commonly used in telephone and ATM networks to a path selection algorithm that is based on the balanced allocations principle-the Balanced Dynamic Alternative Routing (BDAR) algorithm. While the standard technique checks alternative routes sequentially until available bandwidth is found, the BDAR algorithm compares and chooses the best among a small number of alternatives. We show that, at the expense of a minor increase in routing overhead, the BDAR gives a substantial improvement in network performance in terms of both network congestion and blocking probabilities.

Details

FOCS Conference 1996 Conference Paper

A General Approach to Dynamic Packet Routing with Bounded Buffers (extended abstract)

  • Andrei Z. Broder
  • Alan M. Frieze
  • Eli Upfal

We prove a sufficient condition for the stability of dynamic packet routing algorithms. Our approach reduces the problem of steady state analysis to the easier and better understood question of static routing. We show that certain high probability and worst case bounds on the quasistatic (finite past) performance of a routing algorithm imply bounds on the performance of the dynamic version of that algorithm. Our technique is particularly useful in analyzing routing on networks with bounded buffers where complicated dependencies make standard queuing techniques inapplicable. We present several applications of our approach. In all cases we start from a known static algorithm, and modify it to fit our framework. In particular we give the first dynamic algorithm for routing on a butterfly with bounded buffers. Both the injection rate for which the algorithm is stable, and the expected time a packet spends in the system are optimal up to constant factors. Our approach is also applicable to the recently introduced adversarial input model.

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 1990 Conference Paper

Fault Tolerant Sorting Network

  • Shay Assaf
  • Eli Upfal

A general technique for enhancing the reliability of sorting networks and other comparator-based networks is presented. The technique converts any network that uses unreliable comparators to a fault-tolerant network that produces the correct output with overwhelming probability, even if each comparator is faulty with some probability smaller than 1/2, independently of other comparators. The depth of the fault-tolerant network is only a constant times the depth of the original network, and the width of the network is increased by a logarithmic factor. >

Details

TCS Journal 1988 Journal Article

A tradeoff between search and update time for the implicit dictionary problem

  • Allan Borodin
  • Faith E. Fich
  • Friedhelm Meyer auf der Heide
  • Eli Upfal
  • Avi Wigderson

This paper proves a tradeoff between the time it takes to search for elements in an implicit dictionary and the time it takes to update the value of elements in specified locations of the dictionary. It essentially shows that if the update time is constant, then the search time is Ω(nε) for some constant ε>0.

Details DOI

TCS Journal 1987 Journal Article

The generalized packet routing problem

  • David Peleg
  • Eli Upfal

The problem of efficient packet routing is central to the area of communication networks. The special case of permutation packet routing has been extensively studied in the past. While optimal algorithms for permutation routing exist, they do not ‘scale up’ to give optimal solutions for the general case. Using a novel technique we obtain an optimal algorithm for the general packet routing problem. The core of our solution is an algorithm for a generalized version of the token distribution problem. This result has direct applications to the solution of the load balancing problem in distributed systems.

Details DOI

FOCS Conference 1985 Conference Paper

The Complexity of Parallel Computation on Matroids

  • Richard M. Karp
  • Eli Upfal
  • Avi Wigderson

In [KUW1] we have proposed the setting of independence systems to study the relation between the computational complexity of search and decision problems. The universal problem that captures this relation, which we termed the S-search problem, is: "Given an oracle for the input system, find a maximal independent subset in it". Many interesting and important search problems can be described by a special class of independence systems, called matroids. This paper is devoted to die complexity of the S- search problem for matroids. Our main result is a lower bound on any probabilistic algorithm for the S-search problem that acquires information about the input system by interrogating an independence oracle. We prove that the expected time of any such probabilistic algorithm that uses a sub-exponential number of processors is Ω(n1/3-ε). This is one of the first nontrivial, super-logarithmic lower bounds on a randomized parallel computation. It implies that in our model of computation Random-NC is strictly contained in P. Another consequence of the lower bound is that the O(√n) time probabilistic upper bound for arbitrary independence systems, presented in [KUW1], is close to optimal and cannot be significantly improved, even for matroids. However, fills O(√n) upper bound can be improved in a different sense for matroids -it can be made deterministic, still with polynomially many processors. Finally, we show that the lower bound can be beaten for the special case of graphic matroids. Here, the S-search problem is simply to find a spanning forest of a graph, when the algorithm cannot see the graph, but can only ask whether subsets of edges are forests or not. We give an O(logn) time deterministic parallel algoritlun that uses nO(logn) processors. From the upper bounds on parallel time above we deduce similar bounds (up to a poly-log factor) on thc sequential space required by a deterministic Turing machine with an independence oracle to solve the S-search problem.

Details

FOCS Conference 1984 Conference Paper

How to Share Memory in a Distributed System (A Preliminary Version)

  • Eli Upfal
  • Avi Wigderson

We study the power of shared-memory in models of parallel computation. We describe a novel distributed data structure that eliminates the need for shared mernory without significantly increasing the run time of the parallel computation. We also show how a complete network of processors can deterministicly simulate one PRAM step in O(log n(loglog n) 2 ) time, when both models use n processors, and ttie size of the PRAM'S shared memory is polynomial in n. (The best previously known upper bound was the trivial O(n)). We also establish that this upper bound is nearly optimal. We prove that an online simulation of T PRAM steps by a complete network of processors requires Ω(Tlog n/loglog n) time.

Details