Avner Magen, Funda Ergün, Sofya Raskhodnikova, Rahul Sami, Joe Kilian, Ronitt Rubinfeld
Categories and Subject Descriptors
ABSTRACT A Strategic Model for Information Markets (2008)
Information markets, which are designed specifically to aggregate traders ’ information, are becoming increasingly popular as a means for predicting future events. Recent research in information...
Abstract Path Auctions When an Agent Can Own Multiple Edges 1 (2008)
We study path auction games in which multiple edges may be owned by the same agent in this paper. The edge costs and the set of edges owned by the same agent are privately known to the owner of the...
Lower bounds for distributed markov chain problems (2008)
We study the worst-case communication complexity of distributed algorithms computing a path problem based on stationary distributions of random walks in a network $G$ with the caveat that $G$ is also...
Speculative Clustered Caches for Clustered Processors (2008)
Dana S. Henry, Gabriel H. Loh, Rahul Sami
Abstract. Clustering is a technique for partitioning superscalar processor’s execution resources to simultaneously allow for more in-flight instructions, wider issue width, and more aggressive...
Mechanism Design for Policy Routing Received: Accepted: (2008)
Joan Feigenbaum, Rahul Sami, Scott Shenker, J. Feigenbaum, R. Sami, S. Shenker
Abstract The Border Gateway Protocol (BGP) for interdomain routing is designed to allow autonomous systems (ASes) to express policy preferences over alternative routes. We model these preferences as...
Aaron Archer, Joan Feigenbaum, Arvind Krishnamurthy, Rahul Sami, Scott Shenker
We investigate multicast cost sharing from both computational and economic perspectives. Recent work in economics leads to the consideration of two mechanisms: marginal cost (MC), which is ecient and...
Joan Feigenbaum, Christos Papadimitriou, Rahul Sami, Scott Shenker
Summary. The routing of traffic between Internet domains, or Autonomous Systems (ASs), a task known as interdomain routing, is currently handled by the Border Gateway Protocol (BGP). In this paper,...
Aaron Archer, Joan Feigenbaum, Arvind Krishnamurthy, Rahul Sami, Scott Shenker
Multicast routing is a technique for transmitting a packet from a single source to multiple receivers without wasting network bandwidth. To achieve transmission e#ciency, multicast routing constructs...
Dana Henry, Gabriel Loh, Rahul Sami, Ji-jon Sit, Vinod Viswanath, Bradley Kuszmaul
The UltraC2K is a superscalar processor whose integer core is being fabricated as part of the SRC/Novellus/UMC Copper IC Design Challenge contest. The UltraC2K has a peak issue rate of eight...
Joan Feigenbaum, Arvind Krishnamurthy, Rahul Sami, Scott Shenker
We investigate multicast cost sharing from both computational and economic points of view. Recent work in economics (Moulin and Shenker, 2001) leads naturally to the consideration of two mechanisms:...
Joan Feigenbaum, Christos Papadimitriou, Rahul Sami, Scott Shenker
The routing of trac between Internet domains or Autonomous Systems (ASs), a task known as interdomain routing, is currently handled by the Border Gateway Protocol (BGP). In this paper, we address the...
Joan Feigenbaum, David M. Pennock, Lance Fortnow, 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...
The Influence Limiter: Provably Manipulation-Resistant Recommender Systems (Appendix) (2007)
Appendix containing proofs omitted from Resnick and Sami,"The Influence Limiter: Provably Manipulation-Resistant Recommender Systems", ACM Recommender Systems Conference 2007.
The influence limiter: Provably manipulation-resistant recommender systems (2007)
This appendix should be read in conjunction with the article by Resnick and Sami [1]. Here, we include the proofs that were omitted from the main article due to shortage of space. A.1 Lemma 5 Lemma...
Overlay Networks and Future of the Internet (2006)
Dave Clark, Bill Lehr, Steve Bauer, Peyman Faratin, Rahul Sami, John Wroclawski
Abstract: In recent years, we have seen the emergence of numerous types of so-called "overlay " networks in the internet. There are many diverse examples of such overlay networks...
Y.: Path auction games when an agent can own multiple edges. In: NetEcon (2006)
We study path auction games in which multiple edges may be owned by the same agent in this paper. The edge costs and the set of edges owned by the same agent are privately known to the owner of the...
Y.: Path auction games when an agent can own multiple edges. In: NetEcon (2006)
We study path auction games in which multiple edges may be owned by the same agent in this paper. The edge costs and the set of edges owned by the same agent are privately known to the owner of the...
Dave Clark, Bill Lehr, Steve Bauer, Peyman Faratin, Rahul Sami, John Wroclawski
* * Preliminary draft. Please do not cite without contacting authors 1 ** Over the past several years, we have seen the emergence of numerous types of socalled "overlay " networks...
Subjective-cost policy routing (2005)
Joan Feigenbaum, David R. Karger, Vahab S. Mirrokni, Rahul Sami
Abstract. We study a model of interdomain routing in which autonomous systems’ (ASes’) routing policies are based on subjective cost assessments of alternative routes. The routes are constrained...
Joan Feigenbaum, Christos Papadimitriou, Rahul Sami, Scott Shenker
Summary. The routing of traffic between Internet domains, or Autonomous Systems (ASs), a task known as interdomain routing, is currently handled by the Border Gateway Protocol (BGP). In this paper,...
First-price path auctions (2005)
Nicole Immorlica, Evdokia Nikolova, David Karger, Rahul Sami
We study first-price auction mechanisms for auctioning flow between given nodes in a graph. A first-price auction is any auction in which links on winning paths are paid their bid amount; the...
Computation in a Distributed Information Market (2004)
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...
A sublinear algorithm for weakly approximating edit distance (2003)
Batu, Tugkan, Ergun, Funda, Kilian, Joe, Magen, Avner, Raskhodnikova, Sofya, Rubinfeld, Robin, ...
Distributed algorithmic mechanism design / (2003)
Thesis (Ph. D.)--Yale University, 2003.
Distributed algorithmic mechanism design [microform] / (2003)
Thesis (Ph. D.)--Yale University, 2003.
A sublinear algorithm for weakly approximating edit distance (2003)
Tu ˘gkan Batu, Avner Magen, Sofya Raskhodnikova, Rahul Sami, Joe Kilian
We show how to determine whether the edit distance between two given strings is small in sublinear time. Specifically, we present a test which, given two n-character strings A and B, runs in time...
Computation in a distributed information market (2003)
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...
Computation in a distributed information market (2003)
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...
Abstract Distributed Algorithmic Mechanism Design (2003)
Dissertation Director, Joan Feigenbaum, Rahul Sami, Rahul Sami
Distributed algorithmic mechanism design (DAMD) is an approach to designing dis-tributed systems that takes into account both the distributed-computational environment and the incentives of...
Mechanism Design for Policy Routing (2003)
Joan Feigenbaum, Rahul Sami, Scott Shenker
The Border Gateway Protocol (BGP) for interdomain routing is designed to allow autonomous systems (ASes) to express policy preferences over alternative routes. We model these preferences as arising...
Hardness results for multicast cost sharing (2002)
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...
Hardness results for multicast cost sharing (2002)
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...
Memory Bypassing: Not Worth the Effort (2002)
Gabriel H. Loh, Rahul Sami, Daniel H. Friendly
Memory dependence prediction establishes a read after write dependence between a store and a load instruction. If the processor accurately predicts the data dependence between a store and a...
Memory Bypassing: Not Worth the Effort (2002)
Gabriel H. Loh, Rahul Sami, Daniel H. Friendly
Memory dependence prediction establishes a read after write dependence between a store and a load instruction. If the processor accurately predicts the data dependence between a store and a...
Agents’ privacy in distributed algorithmic mechanisms. Position Paper (2002)
Joan Feigenbaum, Noam Nisan, Vijay Ramachandran, Rahul Sami, Scott Shenker
In traditional theoretical computer science (TCS), computational agents are typically assumed either to be obedient (i.e., to follow the prescribed algorithm) or to be adversaries who “play against...
Hardness results for multicast cost sharing (2002)
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...
A BGP-based Mechanism for Lowest-Cost Routing (2002)
Joan Feigenbaum, Christos Papadimitriou, Rahul Sami, Scott Shenker
The routing of tra#c between Internet domains or Autonomous Systems (ASs), a task known as interdomain routing, is currently handled by the Border Gateway Protocol (BGP). In this paper, we address...
Hardness Results for Multicast Cost Sharing (Extended Abstract (2002)
Joan Feigenbaum, Arvind Krishnamurthy, Rahul Sami, Scott Shenker
Abstract. 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...
Hardness Results for Multicast Cost Sharing (Extended Abstract) (2002)
Joan Feigenbaum, Arvind Krishnamurthy, Rahul Sami, Scott Shenker
Joan Feigenbaum Arvind Krishnamurthy Rahul Sami + Yale University, Computer Science Dept., New Haven, CT 06520-8285.
A BGP-based Mechanism for Lowest-Cost Routing (2002)
Joan Feigenbaum, Rahul Sami, Christos Papadimitriou, Scott Shenker
The routing of traffic between Internet domains or Autonomous Systems (ASs), a task known as interdomain routing, is currently handled by the Border Gateway Protocol (BGP). In this paper, we address...
Hardness Results for Multicast Cost Sharing (2002)
Joan Feigenbaum Arvind, 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...
Incentive-Compatible Interdomain Routing (2002)
Joan Feigenbaum Christos, Christos Papadimitriou, Rahul Sami, Scott Shenker
The routing of traffic between Internet domains or Autonomous Systems (ASs), a task known as interdomain routing, is currently handled by the Border Gateway Protocol (BGP). In this paper, we address...
Approximation and collusion in multicast cost sharing (2001)
Aaron Archer, Joan Feigenbaum, Arvind Krishnamurthy, Rahul Sami, Scott Shenker
We investigate multicast cost sharing from both computational and economic perspectives. Recent work in economics leads to the consideration of two mechanisms: marginal cost (MC), which is efficient...
Approximation and collusion in multicast cost sharing (2001)
Joan Feigenbaum, Arvind Krishnamurthy, Rahul Sami, Scott Shenker
We investigate multicast cost sharing from both computational and economic points of view. Recent work in economics [MS97] leads naturally to the consideration of two mechanisms: marginal cost (MC),...
Circuits for wide-window superscalar processors (2000)
Dana S. Henry, Bradley C. Kuszmaul, Gabriel H. Loh, Rahul Sami
Our program benchmarks and simulations of novel circuits indicate that large-window processors are feasible. Using our redesigned superscalar components, a large-window processor implemented in...
Circuits for Wide-Window Superscalar Processors (2000)
Dana Henry, Bradley Kuszmaul, Gabriel Loh, Rahul Sami, Vinod Viswanath
Our program benchmarks and simulations of novel circuits indicate that large-window processors are feasible. Using our redesigned superscalar components, a large-window processor implemented in...
Circuits for wide-window superscalar processors (2000)
Dana S. Henry, Bradley C. Kuszmaul, Gabriel H. Loh, Rahul Sami
Our program benchmarks and simulations of novel circuits indicate that large-window processors are feasible. Using our redesigned superscalar components, a large-window processor implemented in...
Circuits for wide-window superscalar processors (2000)
Dana S. Henry, Bradley C. Kuszmaul, Gabriel H. Loh, Rahul Sami
Our program benchmarks and simulations of novel circuits indicate that large-window processors are feasible. Using our redesigned superscalar components, a large-window processor implemented in...