Arrow Research search

Author name cluster

Joan Feigenbaum

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.

13 papers
2 author rows

Possible papers

13

TCS Journal 2007 Journal Article

Subjective-cost policy routing

  • Joan Feigenbaum
  • David R. Karger
  • Vahab S. Mirrokni
  • Rahul Sami

We study a model of path-vector routing in which nodes’ routing policies are based on subjective cost assessments of alternative routes. The routes are constrained by the requirement that all routes to a given destination must be confluent. We show that it is NP-hard to determine whether there is a set of stable routes. We also show that it is NP-hard to find a set of confluent routes that minimizes the total subjective cost; it is hard even to approximate the minimum cost closely. These hardness results hold even for very restricted classes of subjective costs. We then consider a model in which the subjective costs are based on the relative importance nodes place on a small number of objective cost measures. We show that a small number of confluent routing trees is sufficient for each node to have a route that nearly minimizes its subjective cost. We show that this scheme is trivially strategy proof and that it can be computed easily with a distributed algorithm. Furthermore, we prove a lower bound on the number of trees required to contain a ( 1 + ϵ ) -approximately optimal route for each node and show that our scheme is nearly optimal in this respect.

Details DOI

TCS Journal 2007 Journal Article

Towards a theory of data entanglement

  • James Aspnes
  • Joan Feigenbaum
  • Aleksandr Yampolskiy
  • Sheng Zhong

We give a formal model for systems that store data in entangled form. We propose a new notion of entanglement, called all-or-nothing integrity (AONI) that binds the users’ data in a way that makes it hard to corrupt the data of any one user without corrupting the data of all users. AONI can be a useful defense against negligent or dishonest storage providers who might otherwise be tempted to discard documents belonging to users without much clout. We show that, if all users use a fixed standard recovery algorithm, we can implement AONI using a MAC, but, if some of the users adopt instead a non-standard recovery algorithm provided by the dishonest storage provider, AONI can no longer be achieved. However, even for the latter scenario, we describe a simple entangling mechanism that provides AONI for a restricted class of destructive adversaries.

Details DOI

TCS Journal 2005 Journal Article

Computation in a distributed information market

  • Joan Feigenbaum
  • Lance Fortnow
  • David M. Pennock
  • Rahul Sami

According to economic theory—supported by empirical and laboratory evidence—the equilibrium price of a financial security reflects all of the information regarding the security's value. We investigate the computational process on the path toward equilibrium, where information distributed among traders is revealed step-by-step over time and incorporated into the market price. We develop a simplified model of an information market, along with trading strategies, in order to formalize the computational properties of the process. We show that securities whose payoffs cannot be expressed as weighted threshold functions of distributed input bits are not guaranteed to converge to the proper equilibrium predicted by economic theory. On the other hand, securities whose payoffs are threshold functions are guaranteed to converge, for all prior probability distributions. Moreover, these threshold securities converge in at most n rounds, where n is the number of bits of distributed information. We also prove a lower bound, showing a type of threshold security that requires at least n / 2 rounds to converge in the worst case.

Details DOI

TCS Journal 2005 Journal Article

On graph problems in a semi-streaming model

  • Joan Feigenbaum
  • Sampath Kannan
  • Andrew McGregor
  • Siddharth Suri
  • Jian Zhang

We formalize a potentially rich new streaming model, the semi-streaming model, that we believe is necessary for the fruitful study of efficient algorithms for solving problems on massive graphs whose edge sets cannot be stored in memory. In this model, the input graph, G = ( V, E ), is presented as a stream of edges (in adversarial order), and the storage space of an algorithm is bounded by O ( n · polylog n ), where n = | V |. We are particularly interested in algorithms that use only one pass over the input, but, for problems where this is provably insufficient, we also look at algorithms using constant or, in some cases, logarithmically many passes. In the course of this general study, we give semi-streaming constant approximation algorithms for the unweighted and weighted matching problems, along with a further algorithmic improvement for the bipartite case. We also exhibit log n / log log n semi-streaming approximations to the diameter and the problem of computing the distance between specified vertices in a weighted graph. These are complemented by Ω ( log ( 1 - ε ) n ) lower bounds.

Details DOI

TCS Journal 2003 Journal Article

Hardness results for multicast cost sharing

  • Joan Feigenbaum
  • Arvind Krishnamurthy
  • Rahul Sami
  • Scott Shenker

We continue the study of multicast cost sharing from the viewpoints of both computational complexity and economic mechanism design. We provide fundamental lower bounds on the network complexity of group-strategyproof, budget-balanced mechanisms. We also extend a classical impossibility result in game theory to show that no strategyproof mechanism can be both approximately efficient and approximately budget-balanced. Our results show that one important and natural case of multicast cost sharing is an example of a canonical hard problem in distributed, algorithmic mechanism design; in this sense, they represent progress toward the development of a complexity theory of Internet computation.

Details DOI

FOCS Conference 1999 Conference Paper

An Approximate L 1 -Difference Algorithm for Massive Data Streams

  • Joan Feigenbaum
  • Sampath Kannan
  • Martin J. Strauss
  • Mahesh Viswanathan 0001

We give a space-efficient, one-pass algorithm for approximating the L/sup 1/ difference /spl Sigma//sub i/|a/sub i/-b/sub i/| between two functions, when the function values a/sub i/ and b/sub i/ are given as data streams, and their order is chosen by an adversary. Our main technical innovation is a method of constructing families {V/sub j/} of limited independence random variables that are range summable by which we mean that /spl Sigma//sub j=0//sup c-1/ V/sub j/(s) is computable in time polylog(c), for all seeds s. These random variable families may be of interest outside our current application domain, i. e. , massive data streams generated by communication networks. Our L/sup 1/-difference algorithm can be viewed as a "sketching" algorithm, in the sense of (A. Broder et al. , 1998), and our algorithm performs better than that of Broder et al. , when used to approximate the symmetric difference of two sets with small symmetric difference.

Details

FOCS Conference 1991 Conference Paper

Languages that Are Easier than their Proofs

  • Richard Beigel
  • Mihir Bellare
  • Joan Feigenbaum
  • Shafi Goldwasser

Languages in NP are presented for which it is harder to prove membership interactively than it is to decide this membership. Similarly, languages where checking is harder than computing membership are presented. Under assumptions about triple-exponential time, incoherent sets in NP are constructed. Without any assumptions, incoherent sets are constructed in DSPACE (n to the log n), yielding the first uncheckable and non-random-self-reducible sets in that space. >

Details