On Revenue Maximization in Second-Price Ad Auctions (2009)
Azar, Yossi, Birnbaum, Benjamin, Karlin, Anna R., Nguyen, C. Thach
Most recent papers addressing the algorithmic problem of allocating advertisement space for keywords in sponsored search auctions assume that pricing is done via a first-price auction, which does not...
Andrew V. Goldberg, Andrew Wright, Jason D. Hartline, Michael Saks, Anna R. Karlin
We study a class of single-round, sealed-bid auctions for items in unlimited supply, such as digital goods. We introduce the notion of competitive auctions. A competitive auction is truthful (i.e.,...
Abstract Implementing Global Memory Management in a Workstation Cluster (2008)
Michael J. Feeley, William E. Morgan, Frederic H. Pighin, Anna R. Karlin, Henry M. Levy, Chandramohan A. Thekkath
Advances in network and processor technology have greatly changed the communication and computational power of local-area workstation clusters. However, operating systems still treat workstation...
Andrew V. Goldberg, Jason D. Hartline, Michael Saks, Andrew Wright, Anna R. Karlin
We study a class of single-round, sealed-bid auctions for an item in unlimited supply, such as a digital good. We introduce the notion of competitive auctions. A competitive auction is truthful...
Abstract On Profit-Maximizing Envy-free Pricing (2008)
Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe
We study the problem of pricing items for sale to consumers so as to maximize the seller’s revenue. We assume that for each consumer, we know the maximum amount he would be willing to pay for each...
Thinking Twice about Second-Price Ad Auctions (2008)
Azar, Yossi, Birnbaum, Benjamin, Karlin, Anna R., Nguyen, C. Thach
Recent work has addressed the algorithmic problem of allocating advertisement space for keywords in sponsored search auctions so as to maximize revenue, most of which assume that pricing is done via...
Improved Approximation Algorithms for Budgeted Allocations (2008)
Yossi Azar, Benjamin Birnbaum, Anna R. Karlin, Claire Mathieu, C. Thach Nguyen
Abstract. We provide a 3/2-approximation algorithm for an offline budgeted allocations problem, an improvement over the e/(e − 1) approximation of Andelman and Mansour [1] and the e/(e − 1) −...
Abstract On Profit-Maximizing Envy-free Pricing (2008)
Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe
We study the problem of pricing items for sale to consumers so as to maximize the seller’s revenue. We assume that for each consumer, we know the maximum amount he would be willing to pay for each...
Balloon Popping With Applications to Ascending Auctions (2008)
Nicole Immorlica, Anna R. Karlin, Mohammad Mahdian, Kunal Talwar
We study the power of ascending auctions in a scenario in which a seller is selling a collection of identical items to anonymous unit-demand bidders. We show that even with full knowledge of the set...
Abstract Implementing Cooperative Prefetching and Caching in a Globally-Managed Memory System (2008)
Geoffrey M. Voelker, Eric J. Anderson, Tracy Kimbrel, Jeffreys. Chase Z, Anna R. Karlin, ...
This paper presents cooperative prefetching and caching — the use of network-wide global resources (memories, CPUs, and disks) to support prefetching and caching in the presence of hints of future...
Competitive Generalized Auctions Amos Fiat (2008)
Jason D. Hartline, A. Alfred Taubman, Andrew V. Goldberg, Anna R. Karlin
God help us if we ever take the theater out of the auction business or anything else. It would be an awfully boring world.
Competitive Generalized Auctions Amos Fiat (2008)
Jason D. Hartline, A. Alfred Taubman, Andrew V. Goldberg, Anna R. Karlin
God help us if we ever take the theater out of the auction business or anything else. It would be an awfully boring world.
Andrew V. Goldberg, Jason D. Hartline, Michael Saks, Andrew Wright, Anna R. Karlin
We study a class of single-round, sealed-bid auctions for items in unlimited supply, such as digital goods. We introduce the notion of competitive auctions. A competitive auction is truthful (i.e.,...
Abstract Implementing Cooperative Prefetching and Caching in a Globally-Managed Memory System (2008)
Geoffrey M. Voelker, Eric J. Anderson, Tracy Kimbrel, Jeffreys. Chase Z, Anna R. Karlin, ...
This paper presents cooperative prefetching and caching — the use of network-wide global resources (memories, CPUs, and disks) to support prefetching and caching in the presence of hints of future...
Abstract On Profit-Maximizing Envy-free Pricing (2008)
Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe
We study the problem of pricing items for sale to consumers so as to maximize the seller’s revenue. We assume that for each consumer, we know the maximum amount he would be willing to pay for each...
Andrew V. Goldberg, Andrew Wright, Jason D. Hartline, Michael Saks, Anna R. Karlin
We study a class of single-round, sealed-bid auctions for items in unlimited supply, such as digital goods. We introduce the notion of competitive auctions. A competitive auction is truthful (i.e.,...
Abstract Implementing Global Memory Management in a Workstation Cluster (2008)
Michael J, Wdliam E. Morgan, Anna R. Karlin, Henry M. Levy
Advances in network and processor technology have greatly changed the communication and computational power of local-area workstation clusters. However, operating systems still treat work-station...
Dimitris Achlioptas, Amos Fiat, Anna R. Karlin, Frank Mcsherry. Web, In Moni Naor, Proceedings Of The
[2] Nasreen AbdulJaleel and Yan Qu. Domain term extraction and struc-turing via link analysis. In Dunja Mladenic, Natasha Milic-Frayling, and
Kaustubh Deshmukh, Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin
Abstract In this paper we consider the problem of designing a mechanism for double auctions where bidders each bid to buy or sell one unit of a single commodity. We assume that each bidder's...
Competitive Generalized Auctions Amos Fiat (2007)
Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin
God help us if we ever take the theater out of the auction business or anything else. It would be an awfully boring world. | A. Alfred Taubman, Chairman, Sotheby Galleries.
Jared Saia, Steve Gribble, Anna R. Karlin, Stefan Saroiu
We describe a content addressable network which is robust in the face of massive adversarial attacks and in a highly dynamic environment. Our network is robust in the sense that at any time, an...
Abstract Dynamically Fault-Tolerant Content Addressable Networks (2007)
Jared Saia, Amos Fiat, Steve Gribble, Anna R. Karlin, Stefan Saroiu
We describe a content addressable network which is robust in the face of massive adversarial attacks and in a highly dynamic environment. Our network is robust in the sense that at any time, an...
Jared Saia, Steve Gribble, Anna R. Karlin, Stefan Saroiu
We describe a content addressable network which is robust in the face of massive adversarial attacks and in a highly dynamic environment. Our network is robust in the sense that at any time, an...
--- William Shakespeare, Loves Labours Lost. Act i. Sc. 1. (2007)
Dimitris Achlioptas, Anna R. Karlin, Frank Mcsherry
Small have continual plodders ever won save base authority from others books.
Ronald Fagin, Anna R. Karlin, Jon Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld, ...
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...
--- William Shakespeare, Loves Labours Lost. Act i. Sc. 1. (2007)
Dimitris Achlioptas, Anna R. Karlin, Frank Mcsherry
Small have continual plodders ever won save base authority from others books.
Jason Hartline, Anna R. Karlin, Jared Saia, John Wilkes
The data migration problem is the problem of computing an ecient plan for moving data stored on devices in a network from one conguration to another. Load balancing or changing usage patterns could...
Random Walks with \Back Buttons" (2007)
Ronald Fagin, Anna R. Karlin, Jon Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld, ...
We introduce backo 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...
Eric Anderson, Jason Hartline, Michael Hobbs, Anna R. Karlin, Jared Saia, Ram Swaminathan, ...
Abstract. The data migration problem is the problem of computing a plan for moving data objects stored on devices in a network from one con-guration to another. Load balancing or changing usage...
Submitted to Games and Economic Behavior Competitive Auctions (2007)
Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Andrew Wright
We study a class of single-round, sealed-bid auctions for items in unlimited supply, such as digital goods. We introduce the notion of competitive auctions. A competitive auction is truthful (i.e.,...
Cheap labor can be expensive (2007)
We study markets in which consumers are trying to hire a team of agents to perform a complex task. Each agent in the market prices their labor, and based on these prices, consumers hire the cheapest...
Beyond VCG: Frugality of truthful mechanisms (2005)
We study truthful mechanisms for auctions in which the auctioneer is trying to hire a team of agents to perform a complex task, and paying them for their work. As common in the field of mechanism...
Beyond VCG: Frugality of truthful mechanisms (2005)
We study truthful mechanisms for auctions in which the auctioneer is trying to hire a team of agents to perform a complex task, and paying them for their work. As common in the field of mechanism...
A Lower Bound on the Competitive Ratio of Truthful Auctions (2004)
Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Michael Saks
Abstract We study a class of single-round, sealed-bid auctions for a set of identical items. We adopt the worst case competitive framework defined by [1,2] that compares the profit of an auction to...
A Lower Bound on the Competitive Ratio of Truthful Auctions (2004)
Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Michael Saks
Abstract We study a class of single-round, sealed-bid auctions for a set of identical items. We adopt the worst case competitive framework defined by [1,2] that compares the profit of an auction to...
Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Andrew Wright, Michael Saks
We study a class of single-round, sealed-bid auctions for items in unlimited supply, such as digital goods. We introduce the notion of competitive auctions. A competitive auction is truthful (i.e.,...
Abstract Sharing and Caching Characteristics of Internet Content (2002)
Alastair Wolman, Alastair Wolman, Henry M. Levy, Henry M. Levy, Anna R. Karlin, Steven D. Gribble, ...
and have found that it is complete and satisfactory in all respects, and that any and all revisions required by the final examining committee have been made.
Truthful and Competitive Double Auctions (2002)
Kaustubh Deshmukh, Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin
1 Introduction Dynamic pricing mechanisms, and specifically auctions with multiple buyers and sellers, are becoming increasing popular in electronic commerce. We consider double auctions in which...
Truthful and Competitive Double Auctions (2002)
Kaustubh Deshmukh, Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin
1 Introduction Dynamic pricing mechanisms, and specifically auctions with multiple buyers and sellers, are becoming increasing popular in electronic commerce. We consider double auctions in which...
Dynamically fault-tolerant content addressable networks (2002)
Steve Gribble, Anna R. Karlin, Stefan Saroiu
\Lambda Abstract We describe a content addressable network which is robust in the face of massive adversarial attacks and in a highly dynamic environment. Our network is robust in the sense that at...
Truthful and Competitive Double Auctions (2002)
Kaustubh Deshmukh, Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin
Abstract In this paper we consider the problem of designing a mechanism for double auctions where bidders each bid to buy or sell one unit of a single commodity. We assume that each bidder’s...
Competitive Generalized Auctions (2002)
Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, A. Alfred Taubman
We describe mechanisms for auctions that are simultaneously truthful (alternately known as strategy-proof or incentive -compatible) and guarantee high "net" profit. We make use of...
Truthful and Competitive Double Auctions (2002)
Kaustubh Deshmukh, Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin
In this paper we consider the problem of designing a mechanism for double auctions where bidders each bid to buy or sell one unit of a single commodity. We assume that each bidder's utility...
Random walks with ``back buttons'' (2001)
Fagin, Ronald, Karlin, Anna R., Kleinberg, Jon, Raghavan, Prabhakar, Rajagopalan, Sridhar, Rubinfeld, Ronitt, ...
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 World Wide Web. comment, Science, 287:2115a, 2000. (2001)
Webgraph Papers, Daniel M. Abrams, Dimitris Achlioptas, Amos Fiat, Anna R. Karlin, Frank Mcsherry, ...
In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pages 171–180, 2000. [12] William Aiello, Fan R. K. Chung, and Linyuan Lu. Random evolution
Dynamic TCP acknowledgement and other stories about e/(e-1 (2001)
Anna R. Karlin, Claire Kenyon, Dana Randall
x Abstract We present the first optimal randomized online algorithms for the TCP acknowledgment problem [5] and the Bahncard problem [8]. These problems are well-known to be generalizations of the...
Random walks with "back buttons". Annals of Applied Probability (2001)
Ronald Fagin, Anna R. Karlin, Jon Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld, ...
y 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...
Dynamic TCP acknowledgement and other stories about e/(e-1 (2001)
Anna R. Karlin, Claire Kenyon, Dana Randall
We present the first optimal randomized online algorithms for the TCP acknowledgment problem [5] and the Bahncard problem [7]. These problems are wellknown to be generalizations of the classical...
Random walks with "back buttons". Annals of Applied Probability (2001)
Ronald Fagin, Anna R. Karlin, Jon Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld, ...
y 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...
Dynamic TCP acknowledgement and other stories about e/(e-1 (2001)
Anna R. Karlin, Claire Kenyon, Dana Randall
We present the first optimal randomized online algorithms for the TCP acknowledgment problem [5] and the Bahncard problem [7]. These problems are well-known to be generalizations of the classical...
Spectral analysis of data (2001)
Yossi Azar, Amos Fiat, Anna R. Karlin, Frank Mcsherry, Jared Saia
Every action must be due to one or other of seven causes: chance, nature, compulsion, habit, reasoning, anger, or appetite.
Dynamic TCP acknowledgement and other stories about e/(e-1 (2001)
Anna R. Karlin, Claire Kenyon, Dana Randall
x Abstract We present the first optimal randomized online algorithms for the TCP acknowledgment problem [5] and the Bahncard problem [8]. These problems are well-known to be generalizations of the...
Dynamic TCP Acknowledgement and Other Stories about e/(e-1) (2001)
Anna R. Karlin, Claire Kenyon, Dana Randall
We present the rst optimal randomized online algorithms for the TCP acknowledgment problem [5] and the Bahncard problem [8]. These problems are well-known to be generalizations of the classical...
Spectral Analysis of Data (2001)
Yossi Azar, Amos Fiat, Anna R. Karlin, Frank Mcsherry, Jared Saia
Experimental evidence suggests that spectral techniques are valuable for a wide range of applications. A partial list of such applications include (i) semantic analysis of documents used to cluster...
Web search via hub synthesis (2001)
Dimitris Achlioptas, Amos Fiat, Anna R. Karlin, Frank Mcsherry
Small have continual plodders ever won save base authority from others books. — William Shakespeare, Loves Labours Lost. Act i. Sc. 1. They define themselves in terms of what they oppose. —...
Random Walks with "Back Buttons" (2000)
Ronald Fagin, Anna R. Karlin, Jon Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld, ...
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...
On List Update and Work Function Algorithms (1999)
Eric J. Anderson, Kris Hildrum, Anna R. Karlin, April Rasala, Michael Saks
. The list update problem, a well-studied problem in dynamic data structures, can be described abstractly as a metrical task system. In this paper, we prove that a generic metrical task system...
On the Performance Potential of Dynamic Cache Line Sizes (1999)
Eric Anderson, Peter Van Vleet, Lindsay Brown, Jean-loup Baer, Anna R. Karlin
In this paper we present offline algorithms for determining the optimal sequence of loads, superloads and bypasses for direct-mapped caches. We evaluate potential gains in terms of miss rate and...
Implementing cooperative prefetching and caching in a globally-managed memory system (1998)
Michael J. Feeley, Jeffrey S. Chase, Anna R. Karlin, Henry M. Levy
This paper presents cooperative prefetching and caching--- the use of network-wide global resources (memories, CPUs, and disks) to support prefetching and caching in the presence of hints of future...
Implementing Cooperative Prefetching and Caching in a Globally-Managed Memory System (1998)
Geoffrey Voelker, Michael J. Feeley, Jeffrey S. Chase, Anna R. Karlin, Henry M. Levy
This paper presents cooperative prefetching and caching --- the use of network-wide global resources (memories, CPUs, and disks) to support prefetching and caching in the presence of hints of future...
Implementing Cooperative Prefetching and Caching in a Globally-Managed Memory System (1998)
Geoffrey Voelker, Michael J. Feeley, Jeffrey S. Chase, Anna R. Karlin, Henry M. Levy
This paper presents cooperative prefetching and caching --- the use of network-wide global resources (memories, CPUs, and disks) to support prefetching and caching in the presence of hints of future...
Near-Optimal Parallel Prefetching and Caching (1997)
Recently there has been a great deal of interest in the operating systems research community in prefetching and caching data from parallel disks, as a technique for enabling serial applications to...
This chapter presents an introduction to the competitive analysis of online algorithms. In an online problem...
Reducing Network Latency Using Subpages in a Global Memory Environment (1996)
Herve Jamrozik, Michael J. Feeley, Geoffrey M. Voelker, James Evans Ii, Anna R. Karlin, Henry M. Levy, ...
New high-speed networks greatly encourage the use of network memory as a cache for virtual memory and file pages, thereby reducing the need for disk access. Becausepages are the fundamental transfer...
A trace-driven comparison of algorithms for parallel prefetching and caching (1996)
Kai Li, Tracy Kimbrel, Tracy Kimbrel, Andrew Tomkins, Andrew Tomkins, R. Hugo Patterson, ...
High-performance I/O systems depend on prefetching and caching in order to deliver good performance to applications. These two techniques have generally been considered in isolation, even though...
Two Adaptive Hybrid Cache Coherency Protocols (1996)
Craig Anderson, Anna R. Karlin
We present and evaluate adaptive, hybrid cache coherence protocols for bus-based, shared-memory multiprocessors. Such protocols are motivated by the observation that sharing patterns vary...
A Trace-Driven Comparison of Algorithms for Parallel Prefetching and Caching (1996)
Tracy Kimbrel Andrew, Andrew Tomkins, R. Hugo Patterson, Brian Bershad, Pei Cao, Edward W. Felten, ...
1 High-performance I/O systems depend on prefetching and caching in order to deliver good performance to applications. These two techniques have generally been considered in isolation, even though...
A Trace-Driven Comparison of Algorithms for Parallel Prefetching and Caching (1996)
Tracy Kimbrel, Andrew Tomkins, R. Hugo Patterson, Brian Bershad, Pei Cao, Edward W. Felten, ...
High-performance I/O systems depend on prefetching and caching in order to deliver good performance to applications. These two techniques have generally been considered in isolation, even though...
A Trace-Driven Comparison of Algorithms for Parallel Prefetching and Caching (1996)
Tracy Kimbrel, Andrew Tomkins, R. Hugo Patterson, Brian Bershad, Pei Cao, Edward W. Felten, ...
High-performance I/O systems depend on prefetching and caching in order to deliver good performance to applications. These two techniques have generally been considered in isolation, even though...
A Trace-Driven Comparison of Algorithms for Parallel Prefetching and Caching (1996)
Tracy Kimbrel, Andrew Tomkins, R. Hugo Patterson, Brian Bershad, Pei Cao, Edward W. Felten, ...
High-performance I/O systems depend on prefetching and caching in order to deliver good performance to applications. These two techniques have generally been considered in isolation, even though...
Integrated Parallel Prefetching and Caching (1996)
Tracy Kimbrel, Pei Cao, Edward W. Felten, Anna R. Karlin, Kai Li
ing with credit is permitted. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. SIGMETRICS 96-5/96 Philadelphia, PA,...
Near-Optimal Parallel Prefetching and Caching (1996)
Recently there has been a great deal of interest in the operating systems research community in prefetching and caching data from parallel disks, as a technique for enabling serial applications to...
Pei Cao, Edward W. Felten, Anna R. Karlin, Kai Li
Although file caching and prefetching are known techniques to improve the performance of file systems, little work has been done on intergrating caching and prefetching. Optimal prefetching is...
Pei Cao, Edward W. Felten, Anna R. Karlin, Kai Li
As the performance gap between disks and microprocessors continues to increase, effective utilization of the file cache becomes increasingly important. Application-controlled file caching and...
Reducing network latency using subpages in a global memory environment (1996)
Hervé A. Jamrozik, Michael J. Feeley, Geoffrey M. Voelker, James Evans Ii, Anna R. Karlin, Henry M. Levy, ...
New high-speed networks greatly encourage the use of network memory as a cache for virtual memory and file pages, thereby reducing the need for disk access. Because pages are the fundamental transfer...
Reducing network latency using subpages in a global memory environment (1996)
Hervé A. Jamrozik, Michael J. Feeley, Geoffrey M. Voelker, James Evans Ii, Anna R. Karlin, Henry M. Levy, ...
New high-speed networks greatly encourage the use of network memory as a cache for virtual memory and file pages, thereby reducing the need for disk access. Because pages are the fundamental transfer...
Reducing TLB and memory overhead using online superpage promotion (1995)
Theodore H. Romer, Wayne H. Ohlrich, Anna R. Karlin, Brian N. Bershad
Modern microprocessors contain small TLBs that maintain a cache of recently used translations. A TLB’s coverage is the sum of the number of bytes mapped by each entry. Applications with working...
Reducing TLB and memory overhead using online superpage promotion (1995)
Theodore H. Romer, Wayne H. Ohlrich, Anna R. Karlin, Brian N. Bershad
Modern microprocessors contain small TLBs that maintain a cache of recently used translations. A TLB's coverage is the sum of the number of bytes mapped by each entry. Applications with working...
Implementing Global Memory Management in a Workstation Cluster (1995)
Michael Feeley William, William E. Morgan, Frederic H. Pighin, Anna R. Karlin, Henry M. Levy, Chandramohan A. Thekkath
Advances in network and processor technology have greatly changed the communication and computational power of local-area workstation clusters. However, operating systems still treat workstation...
Implementing Global Memory Management in a Workstation Cluster (1995)
Michael Feeley, William E. Morgan, Frederic H. Pighin, Anna R. Karlin, Henry M. Levy, Chandramohan A. Thekkath
Advances in network and processor technology have greatly changedthe communicationand computational power of local-area workstation clusters. However, operating systems still treat workstation...
Implementing Global Memory Management in a Workstation Cluster (1995)
Michael J. Feeley, William E. Morgan, Frederic H. Pighin, Anna R. Karlin, Henry M. Levy, Chandramohan A. Thekkath
Advances in network and processor technology have greatly changed the communication and computational power of local-area workstation clusters. However, operating systems still treat workstation...
Implementing Global Memory Management in a Workstation Cluster (1995)
Michael Feeley, William E. Morgan, Frederic H. Pighin, Anna R. Karlin, Henry M. Levy, Chandramohan A. Thekkath
Advances in network and processor technology have greatly changed the communication and computational power of local-area workstation clusters. However, operating systems still treat workstation...
Reducing TLB and Memory Overhead Using Online Superpage Promotion (1995)
Theodore H. Romer, Wayne H. Ohlrich, Anna R. Karlin, Brian N. Bershad
Modern microprocessors contain small TLBs that maintain a cache of recently used translations. A TLB's coverage is the sum of the number of bytes mapped by each entry. Applications with working...
Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Eli Upfal
Abstract. Suppose that we sequentially place n balls into n boxes by putting each ball into a randomly chosen box. It is well known that when we are done, the fullest box has with high probability (1...
On the Fault Tolerance of the Butterfly (1994)
Anna R. Karlin, Greg Nelson, Hisao Tamaki
We study the robustness of the butterfly network against random static faults. Suppose that each edge of the butterfly is present independently of other edges with probability p. Our main result is...
Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Eli Upfal
Suppose that we sequentially place n balls into n boxes by putting each ball into a randomly chosen box. It is well known that when we are done, the fullest box has with high probability (1 + o(1))...
Factors in the Performance of the AN1 Computer Network (1992)
Susan S. Owicki, Susan S. Owicki, Anna R. Karlin, Anna R. Karlin
AN1 (formerly known as Autonet) is a local area network composedof crossbar switches interconnected by 100Mbit/second, full-duplex links. In this paper, we evaluate the performance impact of certain...
Yossi Azar, Andrei Z. Broder, Anna R. Karlin
The setup for our problem consists of n servers that must complete a set of tasks. Each task can be handled only by a subset of the servers, requires a different level of service, and once assigned...
Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Nathan Linial, Steven Phillips
How much can an imperfect source of randomness affect an algorithm ? We examine several simple questions of this type concerning the long-term behavior of a random walk on a finite graph. In our...
Factors in the performance of the AN1 computer network (1992)
Susan S. Owicki, Susan S. Owicki, Anna R. Karlin, Anna R. Karlin
DEC’s business and technology objectives require a strong research program. The Systems Research Center (SRC) and three other research laboratories are committed to filling that need. SRC began...
Factors in the performance of the AN1 computer network (1992)
Susan S. Owicki, Susan S. Owicki, Anna R. Karlin, Anna R. Karlin
DEC’s business and technology objectives require a strong research program. The Systems Research Center (SRC) and three other research laboratories are committed to filling that need. SRC began...
Trading Space for Time in Undirected s-t Connectivity (1991)
Andrei Z. Broder, Prabhakar Raghavan, Robert W. Taylor, Anna R. Karlin, Anna R. Karlin, Eli Upfal, ...
Aleliunas et al. [1] posed the following question: "The reachability problem for undirected graphs can be solved in logspace and O.mn/ time [m is the number of edges and n is the number of...
Bounds on the cover time (1989)
Andrei Z. Broder, Anna R. Karlin
This work may not be copied or reproduced in whole or in part for any commercial
Trading space for time in undirected s-t connectivity (1989)
Andrei Z. Broder, Anna R. Karlin, Anna R. Karlin, Prabhakar Raghavan, Prabhakar Raghavan, ...
DEC’s business and technology objectives require a strong research program. The Systems Research Center (SRC) and three other research laboratories are committed to filling that need. SRC began...
Trading space for time in undirected s-t connectivity (1989)
Andrei Z. Broder, Anna R. Karlin, Anna R. Karlin, Prabhakar Raghavan, Prabhakar Raghavan, ...
DEC’s business and technology objectives require a strong research program. The Systems Research Center (SRC) and three other research laboratories are committed to filling that need. SRC began...
Bounds On The Cover Time (1988)
Andrei Z. Broder, Anna R. Karlin
. Consider a particle that moves on a connected, undirected graph G with n vertices. At each step the particle goes from the current vertex to one of its neighbors, chosen uniformly at random. The...
Sharing memory in distributed systems :--methods and applications /--by Anna Rochelle Karlin. (1987)
"January 1987."
"January 1987."
On Best-Response Bidding in GSP Auctions
Matthew Cary, Aparna Das, Benjamin Edelman, Ioannis Giotis, Kurtis Heimerl, Anna R. Karlin, ...
How should players bid in keyword auctions such as those used by Google, Yahoo! and MSN? We model ad auctions as a dynamic game of incomplete information, so we can study the convergence and...