Understanding and Supporting Directed Content Sharing on the Web (2009)
Miller, Rob, Karger, David, Marcus, Adam, Bernstein, Michael
To find interesting, personally relevant web content, we often rely on friends and colleagues to pass links along as they encounter them. In this paper, we study and augment link-sharing via e-mail,...
Personalized Experiences for End-User Programming on the Web (2009)
Van Kleek, Max, André, Paul, Karger, David, Schraefel, M.c.
In this position paper we explore current work in AtomsMasher, an end-user reactive programming environment for the Web, highlight ongoing work in user interface design, privacy, and sharing, and...
The Perfect Search Engine is Not Enough: A Study of Orienteering Behavior in Directed Search (2009)
Mark S. Ackerman, Christine Alvarado, David Karger, Jaime Teevan
What: Sometimes, searching for electronic information can be a complex, multistage process, where a user’s information need evolves throughout the course of the search. On the other hand, often a...
Note to Self: Examining Personal Information Keeping in a Lightweight Note-Taking Tool (2009)
Van Kleek, Max, Bernstein, Michael, Panovich, Katrina, Vargas, Greg, Karger, David, Schraefel, Mc
This paper describes a longitudinal field experiment in personal note-taking that examines how people capture and use information in short textual notes. Study participants used our tool, a simple...
General Terms: Economics, Theory. (2008)
David Karger, Evdokia Nikolova
The VCG mechanism for buying a path from s to t in a network with selfish edges, selects the lowest-cost path (LCP) and pays each edge e on the path the edge’s cost plus a bonus equal to the...
Abstract Wide-area cooperative storage with CFS (2008)
Frank Dabek, M. Frans Kaashoek, David Karger, Robert Morris, Ion Stoica
The Cooperative File System (CFS) is a new peer-to-peer readonly storage system that provides provable guarantees for the efficiency, robustness, and load-balance of file storage and retrieval. CFS...
Max Van Kleek, Paul André, Daniel A. Smith, Max L. Wilson, Michael Bernstein, David Karger, ...
Over the past two years, social networking sites have fostered a new kind of data publication: personal feeds about schedule, location, music playing, activity and so on. While these feeds have been...
The multidimensional bin packing and vector bin packing problems are known to not have asymptotic polynomial-time approximation schemes (unless P = NP). Nevertheless, we show that: • Any smoothed...
AtomsMasher: Personal Reactive Automation for the Web (2008)
Van Kleek, Max, André, Paul, Perttunen, Mikko, Bernstein, Michael, Karger, David, Miller, Rob, ...
The rise of "Web 2.0" has seen an explosion of web sites for the social sharing of personal information. To enable users to make valuable use of the rich yet fragmented sea of public, social, and...
Inky: A Sloppy Command Line for the Web with Rich Visual Feedback (2008)
Miller, Robert C., Chou, Victoria H., Bernstein, Michael, Little, Greg, Van Kleek, Max, Karger, David, ...
We present Inky, a command line for shortcut access to common web tasks. Inky aims to capture the efficiency benefits of typed commands while mitigating their usability problems. Inky commands have...
Abstract The multidimensional bin packing and vector bin packingproblems are known to not have asymptotic polynomial-time approximation schemes (unless P = NP). Nevertheless, weshow that: * Any...
Abstract Web caching with consistent hashing (2008)
David Karger, Alexsherman Ł, Andy Berkheimer, Bill Bogstad, Rizwan Dhanidina, Ken Iwamoto, ...
A key performance measure for the World Wide Web is the speed with which content is served to users. As traffic on the Web increases, users are faced with increasing delays and failures in data...
Finding an Exponential Model for Text Retrieval through Textual Analysis (2008)
The Problem: Text retrieval is a difficult problem that has become both more difficult and more important in recent years. The problem has grown due to the increased amount of electronic information...
Jason Rennie, Jaime Teevan, David Karger
• Multinomial Naive Bayes assumes that words are drawn independently from a multinomial p(�x; � θ) = (��x�1)! � d k=1 xk! • θk- chance of seeing word k d� (θk) xk (1) k=1 • xk-...
Surviving the Information Explosion (2008)
Mark Ackerman, Christine Alvarado, David Karger, Jaime Teevan
The Problem: A typical person deals with a great deal of electronic information, and it can be overwhelming to keep track of it all. The problems that people have in interacting with large amounts of...
Bringing the Semantic Web home: a research agenda for local, personalized SWUI (2008)
André, Paul, Schraefel, Mc, Van Kleek, Max, Karger, David
We suggest that by taking the Semantic Web local and personal, and deploying it as a shared "data sea" for all applications to trawl, new types of interaction are possible (even necessitated) with...
Simplifying knowledge creation and access for end-users on the SW (2008)
Van Kleek, Max, Bernstein, Michael, André, Paul, Perttunen, Mikko, Karger, David, Schraefel, Mc
In this position paper, we argue that improved mechanisms for knowledge acquisition and access on the semantic web (SW) will be necessary before it will be adopted widely by end-users. In particular,...
Bringing the Semantic Web home: a research agenda for local, personalized SWUI (2008)
André, Paul, Schraefel, Mc, Van Kleek, Max, Karger, David
We suggest that by taking the Semantic Web local and personal, and deploying it as a shared "data sea" for all applications to trawl, new types of interaction are possible (even necessitated) with...
Simplifying knowledge creation and access for end-users on the SW (2008)
Van Kleek, Max, Bernstein, Michael, André, Paul, Perttunen, Mikko, Karger, David, Schraefel, Mc
In this position paper, we argue that improved mechanisms for knowledge acquisition and access on the semantic web (SW) will be necessary before it will be adopted widely by end-users. In particular,...
AtomsMasher: Personalised Context-Sensitive Automation for the Web (2008)
Van Kleek, Max, Andre, Paul, Perttunen, Mikko, Bernstein, Michael, Karger, David, Miller, Rob, ...
This paper introduces AtomsMasher, an environment for creating reactive scripts that can draw upon widely heterogeneous information to automate common information-intensive tasks. AtomsMasher is...
AtomsMasher: Personalised Context-Sensitive Automation for the Web (2008)
Van Kleek, Max, Andre, Paul, Perttunen, Mikko, Bernstein, Michael, Karger, David, Miller, Rob, ...
This paper introduces AtomsMasher, an environment for creating reactive scripts that can draw upon widely heterogeneous information to automate common information-intensive tasks. AtomsMasher is...
Distributed Job Scheduling in Rings Perry Fizzano (2008)
David Karger, Clifford Stein, Joel Wein, Perry Fizzano, Perry Fizzano
We give a distributed approximation algorithm for job scheduling in a ring architecture. In contrast to almost all other parallel scheduling models, the model we consider captures the influence of...
Exact Algorithms for the Canadian Traveller Problem on Paths and Trees (2008)
Karger, David, Nikolova, Evdokia
The Canadian Traveller problem is a stochastic shortest paths problem in which one learns the cost of an edge only when arriving at one of its endpoints. The goal is to find an adaptive policy...
Exact Algorithms for the Canadian Traveller Problem on Paths and Trees (2008)
Karger, David, Nikolova, Evdokia
The Canadian Traveller problem is a stochastic shortest paths problem in which one learns the cost of an edge only when arriving at one of its endpoints. The goal is to find an adaptive policy...
Max Van Kleek, Michael Bernstein, Paul André, Mikko Perttunen, David Karger
Copyright is held by the author/owner(s).
Sanjeev Arora, Princeton U, David Karger, Philip Klein, Brown U, Andrzej Woloszyn, ...
Given a planar graph on n nodes with costs (weights) on its edges, define the distance between nodes i and j as the length of the shortest path between i and j. Consider this as an instance of metric...
6.856 | Randomized Algorithms (2007)
We will use the two-point sampling scheme described in class, which only requires O(log n) random bits, to choose the random elements needed for the selection algorithm. This sampling scheme assumed...
6.856 | Randomized Algorithms (2007)
We observed in class that the size of the partition is equal to n plus the number of \split " events that occur when an edge crosses some autopartition line (cf. section 1.3 in the text). We...
(a) We rely on the fact that ips are independent, even if biased. To try to generate one bit, ip the coin twice. If you get heads followed by tails (HT) then output heads. If tails followed by heads...
Sanjeev Arora, Princeton U, David Karger, Philip Klein, Brown U, Andrzej Woloszyn, ...
Given a planar graph on n nodes with costs (weights) on its edges, define the distance between nodes i and j as the length of the shortest path between i and j. Consider this as an instance of metric...
Perry Fizzano, David Karger, Clifford Stein, Joel Wein
We give distributed approximation algorithms for job scheduling in a ring architecture. In contrast to almost all other parallel scheduling models, the model we consider captures the influence of the...
Distributed Job Scheduling in Rings (2007)
David Karger, Clifford Stein, Joel Wein, Perry Fizzano, Perry Fizzano
We give a distributed approximation algorithm for job scheduling in a ring architecture. In contrast to many other parallel scheduling models, the model we consider captures the influence of the...
LOOKING UP DATA in P2P Systems � By Hari Balakrishnan, (2007)
M. Frans Kaashoek, David Karger, Robert Morris, Ion Stoica
The main challenge in P2P computing is to design and implement a robust and scalable distributed system composed of inexpensive, individually unreliable computers in unrelated administrative domains....
Haystack’s User Experience for Interacting with Semistructured Information (2007)
David Huynh, Dennis Quan, David Karger
A major stumbling block in the use of information management tools such as desktops, email managers, file browsers and web browsers is the mismatch between the user’s mental model of information...
Explosion: How People Find Their Electronic Information (2007)
Christine Alvarado, Jaime Teevan, Mark S. Ackerman, David Karger
Abstract: We report on a study of how people look for information within email, files, and the Web. When locating a document or searching for a specific answer, people relied on their contextual...
Flexible and Robust Data Storage and Retrieval in the Haystack System (2007)
David Karger, Kenneth D. Mccracken, Kenneth D. Mccracken
in partial fulllment of the requirements for the degree of
MIT-LCS-TR-819 Chord: A scalable peer-to-peer lookup service for Internet applications Ion (2007)
Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan
Efficiently determining the node that stores a data item in a distributed network is an important and challenging problem. This paper describes the motivation and design of the Chord �system, a...
Chord: A scalable peer-to-peer lookup service for Internet applications (2007)
L Lscal, L L Appl, Ion Stoica Robert, Ion Stoica, Robert Morris, David Karger, ...
Efficiently determining the node that stores a data item in a distributed network is an important and challenging problem. This paper describes the motivation and design of the Chord system, a...
The Semantic User Interface Paradigm for Presenting Semi-structured Information (2007)
David F. Huynh, Dennis Quan, Vineet Sinha, David Karger
seeks to store and manage semi-structured data in the user’s personal information corpus. There arises a need to present and allow the user to interact with such semi-structured
Adenine: A Metadata Programming Language (2007)
Dennis Quan, David F. Huynh, Vineet Sinha, David Karger
Haystack (Huynh et al., 2002), our personal information repository, uses a shared metadata store and a system of agents for helping the user manage his or her information. Agents use the shared...
Metadata-supported Agent Infrastructure (2007)
Dennis Quan, David F. Huynh, Vineet Sinha, David Karger
Agents are often useful for allowing users to delegate tedious or complicated tasks to the system. In many systems, multiple agents work in concert to achieve desired objectives. In these...
Semantic Navigation Through Semi-structured Information (2007)
Vineet Sinha, Dennis Quan, David F. Huynh, David Karger
The Haystack project seeks to help users effectively visualize and manage their information. To support the customizability and flexibility needed to let users store and navigate through information...
Abstract Wide-area cooperative storage with CFS (2007)
Frank Dabek, M. Frans Kaashoek, David Karger, Robert Morris, Ion Stoica
The Cooperative File System (CFS) is a new peer-to-peer readonly storage system that provides provable guarantees for the efficiency, robustness, and load-balance of file storage and retrieval. CFS...
We consider the problem of coloring k-colorable graphs with the fewest possible colors. We give a randomized polynomial time algorithm which colors a 3-colorable graph on n vertices with minfO(
Masters of Engineering in Computer Science (2007)
David Karger, Wendy S. Chien, Wendy S. Chien
in partial fulllment of the requirements for the degree of
David Karger Handout, David Karger
obability that we obtain one of the two s-t-min-cuts is at most 2 (2=3) , which is exponentially small. (This proof crucially used that the Handshaking Lemma is not satis ed anymore: although the...
David Karger Handout, David Karger
ood subproblems. To do this, note that since the pivot that yields S k+1 is chosen uniformly at random from S k , the probability that S k is good is at least 1=2, independent of the goodness of all...
David Karger Handout, David Karger
e. 0 = 1, one of the input numbers will not be assigned to any output { if we encounter it, we output nothing. Luckily, this case will become increasingly unlikely as N grows. It remains to be seen...
AtomsMasher: PeRSSonalized Information Delivery and Management on the Web (2007)
Van Kleek, Max, André, Paul, A. Smith, Daniel, L. Wilson, Max, Bernstein, Michael, Karger, David, ...
Over the past two years, social networking sites have fostered a new kind of data publication: personal feeds about schedule, location, music playing, activity and so on. While these feeds have been...
AtomsMasher: PeRSSonalized Information Delivery and Management on the Web (2007)
Van Kleek, Max, André, Paul, A. Smith, Daniel, L. Wilson, Max, Bernstein, Michael, Karger, David, ...
Over the past two years, social networking sites have fostered a new kind of data publication: personal feeds about schedule, location, music playing, activity and so on. While these feeds have been...
Management of Personal Information Scraps (2007)
Bernstein, Michael, Van Kleek, Max, Schraefel, M.c., Karger, David
We introduce research on information scraps – short, self-contained personal notes that fall outside of traditional filing schemes. We report on a preliminary study of information scraps’ nature...
GUI— Phooey! : The Case for Text Input (2007)
Van Kleek, Max, Bernstein, Michael, Karger, David, Schraefel, M.c.
Information cannot be found if it is not entered. Research shows that existing rich graphical application approaches interfere with user input in many ways, forcing complex interactions to enter...
Bernstein, Michael, Van Kleek, Max, Karger, David, Schraefel, Mc
In this paper we describe information scraps -- a class of personal information whose content is scribbled on Post-it notes, scrawled on corners of random sheets of paper, buried inside the bodies of...
Management of Personal Information Scraps (2007)
Bernstein, Michael, Van Kleek, Max, Schraefel, M.c., Karger, David
We introduce research on information scraps – short, self-contained personal notes that fall outside of traditional filing schemes. We report on a preliminary study of information scraps’ nature...
GUI— Phooey! : The Case for Text Input (2007)
Van Kleek, Max, Bernstein, Michael, Karger, David, Schraefel, M.c.
Information cannot be found if it is not entered. Research shows that existing rich graphical application approaches interfere with user input in many ways, forcing complex interactions to enter...
Bernstein, Michael, Van Kleek, Max, Karger, David, Schraefel, Mc
In this paper we describe information scraps -- a class of personal information whose content is scribbled on Post-it notes, scrawled on corners of random sheets of paper, buried inside the bodies of...
Management of Personal Information Scraps (2007)
Bernstein, Michael, Van Kleek, Max, Schraefel, M.c., Karger, David
We introduce research on information scraps – short, self-contained personal notes that fall outside of traditional filing schemes. We report on a preliminary study of information scraps’ nature...
GUI— Phooey! : The Case for Text Input (2007)
Van Kleek, Max, Bernstein, Michael, Karger, David, Schraefel, M.c.
Information cannot be found if it is not entered. Research shows that existing rich graphical application approaches interfere with user input in many ways, forcing complex interactions to enter...
Bernstein, Michael, Van Kleek, Max, Karger, David, Schraefel, Mc
In this paper we describe information scraps -- a class of personal information whose content is scribbled on Post-it notes, scrawled on corners of random sheets of paper, buried inside the bodies of...
Bernstein, Michael, Van Kleek, Max, Karger, David, Schraefel, M.c.
This paper is a case study of an artifact design and evaluation process; it is a reflection on how right thinking about design methods may at times result in sub-optimal results. Our goal has been to...
Bernstein, Michael, Van Kleek, Max, Karger, David, Schraefel, M.c.
This paper is a case study of an artifact design and evaluation process; it is a reflection on how right thinking about design methods may at times result in sub-optimal results. Our goal has been to...
Information Scraps: How and Why Information Eludes our Personal Information Management Tools (2007)
Bernstein, Michael, Van Kleek, Max, Karger, David, Schraefel, Mc
In this paper we describe information scraps -- a class of personal information whose content is scribbled on Post-it notes, scrawled on corners of random sheets of paper, buried inside the bodies of...
Management of Personal Information Scraps (2007)
Michael Bernstein, David Karger, Max Van Kleek
Copyright is held by the author/owner(s).
Exact Algorithms for the Canadian Traveller Problem on Paths and Trees (2007)
David Karger, Evdokia Nikolova, David Karger, Evdokia Nikolova
The Canadian Traveller problem is a stochastic shortest paths problem in which one learns the cost of an edge only when arriving at one of its endpoints. The goal is to find an adaptive policy...
Supplement to "Distributed Quota Enforcement for Spam Control" (2006)
Walfish, Michael, Zamfirescu, J.D., Balakrishnan, Hari, Karger, David, Shenker, Scott
This report is a supplement to our paper "Distributed Quota Enforcement forSpam Control" (NSDI 2006). We assume here that the reader has readthe main paper. In this report, we first analyze the...
Supplement to "Distributed Quota Enforcement for Spam Control" (2006)
Walfish, Michael, Zamfirescu, J.D., Balakrishnan, Hari, Karger, David, Shenker, Scott
This report is a supplement to our paper "Distributed Quota Enforcement forSpam Control" (NSDI 2006). We assume here that the reader has readthe main paper. In this report, we first analyze the...
On Separation, Randomness and Linearity for Network Codes over Finite Fields (2006)
Ray, Siddharth, Effros, Michelle, Medard, Muriel, Koetter, Ralf, Ho, Tracey, Karger, David, ...
We examine the issue of separation and code design for networks that operate over finite fields. We demonstrate that source-channel (or source-network) separation holds for several canonical network...
The Pathetic Fallacy of RDF (2006)
Schraefel, M.c., Karger, David
The most popular visualization of RDF - the underlying language to represent the Semantic Web – is a Great Big Graph (GBG) or Big Fat Graph (BFG) if one prefers. By graph, we mean representations...
The Pathetic Fallacy of RDF (2006)
Schraefel, M.c., Karger, David
The most popular visualization of RDF - the underlying language to represent the Semantic Web – is a Great Big Graph (GBG) or Big Fat Graph (BFG) if one prefers. By graph, we mean representations...
Fresnel: A Browser-Independent Presentation Vocabulary for RDF (2006)
Pietriga, Emmanuel, Bizer, Christian, Karger, David, Lee, Ryan
Semantic Web browsers and other tools aimed at displaying RDF data to end users are all concerned with the same problem: presenting content primar- ily intended for machine consumption in a...
Fresnel: A Browser-Independent Presentation Vocabulary for RDF (2006)
Pietriga, Emmanuel, Bizer, Christian, Karger, David, Lee, Ryan
Semantic Web browsers and other tools aimed at displaying RDF data to end users are all concerned with the same problem: presenting content primar- ily intended for machine consumption in a...
The Pathetic Fallacy of RDF (2006)
Schraefel, M.c., Karger, David
The most popular visualization of RDF - the underlying language to represent the Semantic Web – is a Great Big Graph (GBG) or Big Fat Graph (BFG) if one prefers. By graph, we mean representations...
Fresnel - A Browser-Independent Presentation Vocabulary for RDF (2006)
Emmanuel Pietriga, Christian Bizer, David Karger, Ryan Lee
Abstract. Semantic Web browsers and other tools aimed at displaying RDF data to end users are all concerned with the same problem: presenting content primarily intended for machine consumption in a...
Distributed quota enforcement for spam control (2006)
Michael Walfish, J. D. Zamfirescu, Hari Balakrishnan, David Karger, Scott Shenker
Spam, by overwhelming inboxes, has made email a less reliable medium than it was just a few years ago. Spam filters are undeniably useful but unfortunately can flag non-spam as spam. To restore...
Vineet Sinha, Rob Miller, David Karger
As software systems grow in size and use more third-party libraries and frameworks, the need for developers to understand unfamiliar large codebases is rapidly increasing. In this paper, we present a...
DDoS Defense by Offense (2006)
Michael Walfish, Mythili Vutukuru, Hari Balakrishnan, David Karger, Scott Shenker
This paper presents the design, implementation, analysis, and experimental evaluation of speak-up, a defense against applicationlevel distributed denial-of-service (DDoS), in which attackers cripple...
DDoS Defense by Offense (2006)
Michael Walfish, Mythili Vutukuru, Hari Balakrishnan, David Karger, Scott Shenker
This paper presents the design, implementation, analysis, and experimental evaluation of speak-up, a defense against applicationlevel distributed denial-of-service (DDoS), in which attackers cripple...
DDoS Defense by Offense (2006)
Michael Walfish, Mythili Vutukuru, Hari Balakrishnan, David Karger, Scott Shenker
This paper presents the design, implementation, analysis, and experimental evaluation of speak-up, a defense against applicationlevel distributed denial-of-service (DDoS), in which attackers cripple...
Distributed quota enforcement for spam control (2006)
Michael Walfish, J. D. Zamfirescu, Hari Balakrishnan, David Karger, Scott Shenker
Spam, by overwhelming inboxes, has made email a less reliable medium than it was just a few years ago. Spam filters are undeniably useful but unfortunately can flag non-spam as spam. To restore...
Vineet Sinha, David Karger, Rob Miller
As software systems grow in size and use more third-party libraries and frameworks, the need for developers to understand unfamiliar large codebases is rapidly increasing. In this paper, we present a...
Vineet Sinha, David Karger, Rob Miller
As software systems grow in size and use more third-party libraries and frameworks, the need for developers to understand unfamiliar large codebases is rapidly increasing. In this paper, we present a...
Supplement to “Distributed Quota Enforcement for Spam Control (2006)
Michael Walfish, Michael Walfish, J. D. Zamfirescu, J. D. Zamfirescu, Hari Balakrishnan, David Karger, ...
This report is a supplement to our paper “Distributed Quota Enforcement for Spam Control ” [1]. We assume here that the reader has read the main paper. In this report, we first analyze the...
Piggy Bank: Experience the Semantic Web Inside Your Web Browser (2005)
Huynh, David, Mazzocchi, Stefano, Karger, David
The original publication is available at www.springerlink.com http://dx.doi.org/10.1007/11574620_31
Piggy Bank: Experience the Semantic Web Inside Your Web Browser (2005)
Huynh, David, Mazzocchi, Stefano, Karger, David
The original publication is available at www.springerlink.com http://dx.doi.org/10.1007/11574620_31
Towards a unification & integration of PIM support (2005)
William Jones, David Karger, Ofer Bergman, Mike Franklin, A Pratt, Marcia Bates
Information fragmentation is a pervasive problem which is felt in several stages of personal information management (PIM). As the example in the introduction to this special issue on PIM illustrates,...
Piggy Bank: Experience the semantic web inside your Web browser (2005)
David Huynh, Stefano Mazzocchi, David Karger
Abstract. The Semantic Web Initiative envisions a Web wherein information is offered free of presentation, allowing more effective exchange and mixing across web sites and across web pages. But...
Thresher: Automating the Unwrapping of Semantic Content from the World Wide Web (2005)
We describe Thresher, a system that lets non-technical users teach their browsers how to extract semantic web content from HTML documents on the World Wide Web. Users specify examples of semantic...
DoS: Fighting Fire with Fire (2005)
Michael Walfish Hari, Hari Balakrishnan, David Karger, Scott Shenker
We consider DoS attacks on servers in which attackers' requests are indistinguishable from legitimate requests. Most current defenses against this class of attack rely on legitimate users in...
Piggy Bank: Experience the semantic web inside your Web browser (2005)
David Huynh, Stefano Mazzocchi, David Karger
Abstract. The Semantic Web Initiative envisions a Web wherein information is offered free of presentation, allowing more effective exchange and mixing across web sites and across web pages. But...
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...
Wrapper Induction for End-User Semantic Content Development (2004)
The transition from existing World Wide Web content to the Semantic Web relies on the labeling and classification of existing information before it is useful to end-users and their agents. This paper...
Towards using the network as a switch: On the use of TDM in linear optical networks (2004)
A common problem in optical networking is that the large quantity of raw bandwidth available in such networks is often difficult to access. We show that time-division multiplexing (TDM) can be used...
On the Feasibility of Peer-to-Peer Web Indexing and Search (2003)
Li, Jiyang, Loo, Boon Thau, Hellerstein, Joseph M, Kaashoek, M Frans, Karger, David, Morris, Robert
This paper discusses the feasibility of peer-to-peer full-text keyword search of the Web. Two classes of keyword search techniques are in use or have been proposed: flooding of queries over an...
New Algorithms for Load Balancing in Peer-to-Peer Systems (2003)
Load balancing is a critical issue for the efficient operation of peer-to-peer networks. We give new protocols for several scenarios, whose provable performance guarantees are within a constant...
New Algorithms for Load Balancing in Peer-to-Peer Systems (2003)
Load balancing is a critical issue for the efficient operation of peer-to-peer networks. We give new protocols for several scenarios, whose provable performance guarantees are within a constant...
Learning Classes Correlated to a Hierarchy (2003)
Trees are a common way of organizing large amounts of information by placing items with similar characteristics near one another in the tree. We introduce a classification problem where a given tree...
Learning Classes Correlated to a Hierarchy (2003)
Trees are a common way of organizing large amounts of information by placing items with similar characteristics near one another in the tree. We introduce a classification problem where a given tree...
Surviving the Information Explosion: How People Find Their Electronic Information (2003)
Alvarado, Christine, Teevan, Jaime, Ackerman, Mark S., Karger, David
We report on a study of how people look for information within email, files, and the Web. When locating a document or searching for a specific answer, people relied on their contextual knowledge of...
Surviving the Information Explosion: How People Find Their Electronic Information (2003)
Alvarado, Christine, Teevan, Jaime, Ackerman, Mark S., Karger, David
We report on a study of how people look for information within email, files, and the Web. When locating a document or searching for a specific answer, people relied on their contextual knowledge of...
Tackling the Poor Assumptions of Naive Bayes Text Classifiers (2003)
Naive Bayes is often used as a baseline in text classication because it is fast and easy to implement. Its severe assumptions make such eciency possible but also adversely affect the quality of its...
On the Feasibility of Peer-to-Peer Web Indexing and Search (2003)
Jinyang Li, Boon Thau, Loo Joseph, M. Hellerstein, M. Frans Kaashoek, David Karger, ...
This paper discusses the feasibility of peer-to-peer full-text keyword search of the Web. Two classes of keyword search techniques are in use or have been proposed: flooding of queries over an...
Much work in information retrieval focuses on using a model of documents and queries to derive retrieval algorithms. Model based development is a useful alternative to heuristic development because...
Thwarting web censorship with untrusted messenger discovery (2003)
Nick Feamster, Magdalena Balazinska, Winston Wang, Hari Balakrishnan, David Karger
Abstract. All existing anti-censorship systems for the Web rely on proxies to grant clients access to censored information. Therefore, they face the proxy discovery problem: how can clients discover...
On the Feasibility of Peer-to-Peer Web Indexing and Search (2003)
Jinyang Li Boon, Boon Thau, Loo Joseph, M. Hellerstein, M. Frans Kaashoek, David Karger, ...
This paper discusses the feasibility of peer-to-peer full-text keyword search of the Web. Two classes of keyword search techniques are in use or have been proposed: flooding of queries over an...
Looking Up Data In P2p Systems (2003)
Hari Balakrishnan Frans, M. Frans Kaashoek, David Karger, Robert Morris, Ion Stoica
this article discusses four recent P2P lookup algorithms that have provable guarantees: CAN, Chord, Pastry, and Tapestry. These algorithms stress the ability to scale well to large numbers of nodes,...
Linear Network Codes: A Unified Framework for Source, Channel, and Network Coding (2003)
Michelle Effros, Muriel Medard, Tracey Ho, Siddharth Ray, David Karger, Ralf Koetter, ...
We examine the issue of separation and code design for network data transmission environments. We demonstrate that source-channel separation holds for several canonical network channel models when...
Learning classes correlated to a hierarchy (2003)
Trees are a common way of organizing large amounts of information by placing items with similar characteristics near one another in the tree. We introduce a classification problem where a given tree...
On Coding for Non-Multicast Networks (2003)
Muriel Medard, Michelle Effros, David Karger, Tracey Ho
We consider the issue of coding for non-multicast networks. For multicast networks, it is known that linear operations over a field no larger than the number of receivers are su#cient to achieve all...
On the Feasibility of Peer-to-Peer Web Indexing and Search (2003)
Jinyang Li Boon, Boon Thau, Loo Joseph, M. Hellerstein, M. Frans Kaashoek, David Karger, ...
This paper discusses the feasibility of peer-to-peer full-text keyword search of the Web. Two classes of keyword search techniques are in use or have been proposed: flooding of queries over an...
Surviving the information explosion: how people find their electronic information (2003)
Christine Alvarado, Jaime Teevan, Mark S. Ackerman, David Karger
Abstract: We report on a study of how people look for information within email, files, and the Web. When locating a document or searching for a specific answer, people relied on their contextual...
Looking up data in P2P systems (2003)
Hari Balakrishnan, M. Frans Kaashoek, David Karger, Robert Morris, Ion Stoica
The recent success of some widely deployed peer-to-peer (P2P) file sharing applications has sparked new research in this area. We are interested in the P2P systems that have no centralized control or...
Thwarting web censorship with untrusted messenger discovery (2003)
Nick Feamster, Magdalena Balazinska, Winston Wang, Hari Balakrishnan, David Karger
Abstract. All existing anti-censorship systems for the Web rely on proxies to grant clients access to censored information. Therefore, they face the proxy discovery problem: how can clients discover...
Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut (2002)
Karger, David, Klein, Phil, Stein, Cliff, Thorup, Mikkel, Young, Neal E.
The multiway-cut problem is, given a weighted graph and k >= 2 terminal nodes, to find a minimum-weight set of edges whose removal separates all the terminals. The problem is NP-hard, and even...
INS/Twine: A Scalable Peer-to-Peer Architecture for Intentional Resource Discovery (2002)
Magdalena Balazinska, Hari Balakrishnan, David Karger
Abstract. The decreasing cost of computing technology is speeding the deployment of abundant ubiquitous computation and communication. With increasingly large and dynamic computing environments comes...
Not too hot, not too cold: The Bundled-SVM is just right (2002)
Lawrence Shih, Jason Rennie, David Karger
The Support Vector Machine (SVM) typically outperforms other algorithms on text classification problems, but requires training time roughly quadratic in the number of training documents. In contrast,...
Observations on the dynamic evolution of peer-to-peer networks (2002)
David Liben-nowell, Hari Balakrishnan, David Karger
A fundamental theoretical challenge in peer-to-peer systems is proving statements about the evolution of the system while nodes are continuously joining and leaving. Because the system will operate...
Analysis of the evolution of peer-to-peer systems (2002)
David Liben-nowell, Hari Balakrishnan, David Karger
In this paper, we give a theoretical analysis of peer-to-peer (P2P) networks operating in the face of concurrent joins and unexpected departures. We focus on Chord, a recently developed P2P system...
INS/Twine: A Scalable Peer-to-Peer Architecture for Intentional Resource Discovery (2002)
Magdalena Balazinska, Hari Balakrishnan, David Karger
Abstract. The decreasing cost of computing technology is speeding the deployment of abundant ubiquitous computation and communication. With increasingly large and dynamic computing environments comes...
Infranet: Circumventing Web censorship and surveillance (2002)
Nick Feamster, Magdalena Balazinska, Greg Harfst, Hari Balakrishnan, David Karger
An increasing number of countries and companies routinely block or monitor access to parts of the Internet. To counteract these measures, we propose Infranet, a system that enables clients to...
Dennis Quan, David F. Huynh, Vineet Sinha, David Karger
The Haystack platform (Huynh et al., 2002) is designed to store and manage personal information such as e-mail, documents, contacts, meetings, etc. These types of data are semi-structured in nature...
Observations on the Dynamic Evolution of Peer-to-Peer Networks (2002)
David Liben-nowell, Hari Balakrishnan, David Karger
A fundamental theoretical challenge in peer-to-peer systems is proving statements about the evolution of the system while nodes are continuously joining and leaving. Because the system will operate...
Analysis of the Evolution of Peer-to-Peer Systems (2002)
Hari Balakrishnan, David Karger
In this paper, we give a theoretical analysis of peer-to-peer (P2P) networks operating in the face of concurrent joins and unexpected departures. We focus on Chord, a recently developed P2P system...
Analysis of the Evolution of Peer-to-Peer Systems (2002)
Hari Balakrishnan, David Karger
In this paper, we give a theoretical analysis of peer-to-peer (P2P) networks operating in the face of concurrent joins and unexpected departures. We focus on Chord, a recently developed P2P system...
Infranet: Circumventing Web censorship and surveillance (2002)
Nick Feamster, Magdalena Balazinska, Greg Harfst, Hari Balakrishnan, David Karger
An increasing number of countries and companies routinely block or monitor access to parts of the Internet. To counteract these measures, we propose Infranet, a system that enables clients to...
Not too hot, not too cold: The Bundled-SVM is just right (2002)
Lawrence Shih, Yu-han Chang, Jason Rennie, David Karger
The Support Vector Machine (SVM) typically outperforms other algorithms on text classification problems, but requires training time roughly quadratic in the number of training documents. In contrast,...
Infranet: Circumventing Web censorship and surveillance (2002)
Nick Feamster, Magdalena Balazinska, Greg Harfst, Hari Balakrishnan, David Karger
Symposium
Analysis of the Evolution of Peer-to-Peer Systems (2002)
Hari Balakrishnan, David Karger
In this paper, we give a theoretical analysis of peer-to-peer (P2P) networks operating in the face of concurrent joins and unexpected departures. We focus on Chord, a recently developed P2P system...
Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications (2001)
Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan
A fundamental problem that confronts peer-to-peer applications is to efficiently locate the node that stores a particular data item. This paper presents Chord, a distributed lookup protocol that...
Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications (2001)
Ion Stoica, Robert Morris, David Liben-nowell, David Karger, M. Frans, Kaashoek Frank Dabek, ...
A fundamental problem that confronts peer-to-peer applications is to e#ciently locate the node that stores a particular data item. This paper presents Chord, a distributed lookup protocol that...
Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications (2001)
Ion Stoica, Robert Morris, David Liben-nowell, David Karger, M. Frans, Kaashoek Frank Dabek, ...
A fundamental problem that confronts peer-to-peer applications is to efficiently locate the node that stores a particular data item. This paper presents Chord, a distributed lookup protocol that...
Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications (2001)
Ion Stoica, Robert Morris, David Liben-nowell, David Karger, M. Frans, Kaashoek Frank Dabek, ...
A fundamental problem that confronts peer-to-peer applications is to efficiently locate the node that stores a particular data item. This paper presents Chord, a distributed lookup protocol that...
Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications (2001)
Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan
A fundamental problem that confronts peer-to-peer applications is to efficiently locate the node that stores a particular data item. This paper presents Chord, a distributed lookup protocol that...
Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications (2001)
Ion Stoica, Robert Morris, David Liben-nowell, David Karger, M. Frans, Kaashoek Frank Dabek, ...
A fundamental problem that confronts peer-to-peer applications is to efficiently locate the node that stores a particular data item. This paper presents Chord, a distributed lookup protocol that...
Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications (2001)
Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan
A fundamental problem that confronts peer-to-peer applications is to efficiently locate the node that stores a particular data item. This paper presents Chord, a distributed lookup protocol that...
Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications (2001)
Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan
Efficiently determining the node that stores a data item in a distributed network is an important and challenging problem. This paper describes the motivation and design of the Chord system, a...
Wide-area cooperative storage with CFS (2001)
Frank Dabek, M. Frans Kaashoek, David Karger, Robert Morris, Ion Stoica
The Cooperative File System (CFS) is a new peer-to-peer readonly storage system that provides provable guarantees for the efficiency, robustness, and load-balance of file storage and retrieval. CFS...
Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications (2001)
Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan
A fundamental problem that confronts peer-to-peer applications is to efficiently locate the node that stores a particular data item. This paper presents Chord, a distributed lookup protocol that...
Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications (2001)
Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan
A fundamental problem that confronts peer-to-peer applications is to efficiently locate the node that stores a particular data item. This paper presents Chord, a distributed lookup protocol that...
Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications (2001)
Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan
A fundamental problem that confronts peer-to-peer applications is to efficiently locate the node that stores a particular data item. This paper presents Chord, a distributed lookup protocol that...
Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications (2001)
Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan
A fundamental problem that confronts peer-to-peer applications is to efficiently locate the node that stores a particular data item. This paper presents Chord, a distributed lookup protocol that...
Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications (2001)
Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan
Efficiently determining the node that stores a data item in a distributed network is an important and challenging problem. This paper describes the motivation and design of the Chord system, a...
Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications (2001)
Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan Ý
A fundamental problem that confronts peer-to-peer applications is to efficiently locate the node that stores a particular data item. This paper presents Chord, a distributed lookup protocol that...
Learning Markov Networks : Maximum Bounded Tree-Width Graphs (2001)
David Karger, Nathan Srebro, Om Variables (x, Xn Are Distributed, Choosing D
according to the distribution Ptrue [·]. • The problem is that this distribution is unknown to us, and we wish to estimate or learn it by sampling from it. • Let x (1) , x (2) , x (3) ,..., x...
Maximum likelihood Markov networks: An algorithmic approach (2000)
David Karger, Nathan Srebro, Nathan Srebro
We show how a graphical model learning problem can be presented as a purely combinatorial problem. This allows us to analyze the computational hardness of the learning problem, and devise global...
An Experimental Study of Poly-Logarithmic Fully-Dynamic Connectivity Algorithms (2000)
Raj D. Iyer, David Karger, Hariharan S. Rahul, Mikkel Thorup, Name David, ...
ing with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works, requires prior specific permission...
An Experimental Study of Poly-Logarithmic Fully-Dynamic Connectivity Algorithms (2000)
Raj D. Iyer, David Karger, Hariharan S. Rahul, Mikkel Thorup
this paper we study some algorithms in which t(n) is polylogarithmic.
An Experimental Study of Poly-Logarithmic Fully-Dynamic Connectivity Algorithms (2000)
Raj Iyer Jr, David Karger, Hariharan S. Rahul, Mikkel Thorup
ing with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works, requires prior specific permission...
6.854J / 18.415J Advanced Algorithms, Fall 1999 (1999)
A first-year graduate course in algorithms. Emphasizes fundamental algorithms and advanced methods of algorithmic design, analysis, and implementation. Data structures. Network flows. Linear...
6.854J / 18.415J Advanced Algorithms, Fall 1999 (1999)
A first-year graduate course in algorithms. Emphasizes fundamental algorithms and advanced methods of algorithmic design, analysis, and implementation. Data structures. Network flows. Linear...
Approximation schemes for minimizing average weighted completion time with release dates (1999)
Foto Afrati, Evripidis Bampis, Chandra Chekuri, David Karger, Claire Kenyon, Sanjeev Khanna, ...
We consider the problem of scheduling n jobs with release dates on m machines so as to minimize their average weighted completion time. We present the first known polynomial time approximation...
Approximation schemes for minimizing average weighted completion time with release dates (1999)
Foto Afrati, Evripidis Bampis, Chandra Chekuri, David Karger, Claire Kenyon, Sanjeev Khanna, ...
We consider the problem of scheduling n jobs with release dates on m machines so as to minimize their average weighted completion time. We present the first known polynomial time approximation...
Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates (1999)
Foto Afrati Evripidis, Evripidis Bampis, Chandra Chekuri, David Karger, Claire Kenyon, Sanjeev Khanna, ...
We consider the problem of scheduling n jobs with release dates on m machines so as to minimize their average weighted completion time. We present the first known polynomial time approximation...
Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates (1999)
Foto Afrati, Evripidis Bampis, Chandra Chekuri, David Karger, Claire Kenyon, Sanjeev Khanna, ...
We consider the problem of scheduling n jobs with release dates on m machines so as to minimize their average weighted completion time. We present the first known polynomial time approximation...
Approximate Graph Coloring by Semidefinite Programming (1998)
Karger, David, Motwani, Rajeev, Sudan, Madhu
We consider the problem of coloring k-colorable graphs with the fewest possible colors. We present a randomized polynomial time algorithm that colors a 3-colorable graph on $n$ vertices with min...
Society for his thesis Random Sampling in Graph Optimization Problems. The jury found (1998)
his contribution, on the interface between computer science and optimization, deep and elegant. To make David’s work even better known among the membership, I invited him to write a feature article...
Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems (1998)
Sanjeev Arora, David Karger, Marek Karpinski
We present a unified framework for designing polynomial time approximation schemes (PTASs) for "dense" instances of many NP-hard optimization problems, including maximum cut, graph...
A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP (1998)
Sanjeev Arora, Michelangelo Grigni, Princeton U, David Karger, Philip Klein, Brown U, ...
Given a planar graph on n nodes with costs (weights) on its edges, define the distance between nodes i and j as the length of the shortest path between i and j. Consider this as an instance of metric...
A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP (1998)
Sanjeev Arora, Michelangelo Grigni, Princeton U, David Karger, Philip Klein, Brown U, ...
Given a planar graph on n nodes with costs (weights) on its edges, define the distance between nodes i and j as the length of the shortest path between i and j. Consider this as an instance of metric...
David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, Rina Panigrahy
We describe a family of caching protocols for distrib-uted networks that can be used to decrease or eliminate the occurrence of hot spots in the network. Our protocols are particularly designed for...
A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP (1997)
Graph Tsp, Michelangelo Grigni, Sanjeev Arora, Princeton U, David Karger, Philip Klein, ...
Given a planar graph on n nodes with costs (weights) on its edges, define the distance between nodes i and j as the length of the shortest path between i and j. Consider this as an instance of metric...
Finding Maximum Flows in Undirected Graphs Seems Easier than Bipartite Matching (1997)
David Karger, Matthew S. Levine
Consider an n-vertex, m-edge, undirected graph with maximum flow value v. We give a method to find augmenting paths in such a graph in amortized sub-linear (O(n p v)) time per path. This lets us...
David Karger, Cliff Stein, Joel Wein
Introduction Scheduling theory is concerned with the optimal allocation of scarce resources to activities over time. The practice of this field dates to the first time two humans contended for a...
Distributed Job Scheduling in Rings Perry Fizzano (1997)
Perry Fizzano, David Karger, Clifford Stein, Joel Wein
We give a distributed approximation algorithm for job scheduling in a ring architecture. In contrast to many other parallel scheduling models, the model we consider captures the influence of the...
Scheduling theory is concerned with the optimal allocation of scarce resources to activities over time. The practice of this field dates to the first time two humans contended for a shared resource...
David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, Rina Panigrahy Abstract
We describe a family of caching protocols for distrib-uted networks that can be used to decrease or eliminate the occurrence of hot spots in the network. Our protocols are particularly designed for...
A New Approach to the Minimum Cut Problem (1996)
This paper presents a new approach to finding minimum cuts in undirected graphs. The fundamental principle is simple: the edges in a graph's minimum cut form an extremely small fraction of the...
An Õ(n^3/14)-Coloring Algorithm for 3-Colorable Graphs (1996)
We show how the results of Karger, Motwani, and Sudan [6] and Blum [3] can be combined in a natural manner to yield a polynomial-time algorithm for ~ O(n 3=14 )-coloring any n-node 3-colorable graph....
Minimum Cuts in Near-Linear Time (1996)
We significantly improve known time bounds for solving the minimum cut problem on undirected graphs. We use a "semi-duality" between minimum cuts and maximum spanning tree packings combined...
A New Approach to the Minimum Cut Problem (1996)
This paper presents a new approach to finding minimum cuts in undirected graphs. The fundamental principle is simple: the edges in a graph's minimum cut form an extremely small fraction of the...
Minimum cost multicommodity flow is an instance of a simpler problem (multicommodity flow) to which a cost constraint has been added. In this paper we present a general scheme for solving a large...
Polynomial time approximation schemes for dense instances of NP-hard problems (1995)
Sanjeev Arora, David Karger, Marek Karpinski
We present a unified framework for designing polynomial time approximation schemes (PTASs) for "dense " instances of many NP-hard optimization problems, including maximum cut, graph...
Polynomial time approximation schemes for dense instances of NP-hard problems (1995)
Sanjeev Arora, David Karger, Marek Karpinski
We present a unified framework for designing polynomial time approximation schemes (PTASs) for "dense" instances of many NP-hard optimization problems, including maximum cut, graph...
Minimum cost multicommodity flow is an instance of a simpler problem (multicommodity flow) to which a cost constraint has been added. In this paper we present a general scheme for solving a large...
Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems (1995)
Sanjeev Arora, David Karger, Marek Karpinski
We present a unified framework for designing polynomial time approximation schemes (PTASs) for "dense" instances of many NP-hard optimization problems, including maximum cut, graph...
Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems (1995)
Sanjeev Arora, David Karger, Marek Karpinski
We present a unified framework for designing polynomial time approximation schemes (PTASs) for "dense" instances of many NP-hard optimization problems, including maximum cut, graph...
Polynomial time approximation schemes for dense instances of NP-hard problems (1995)
Sanjeev Arora, David Karger, Marek Karpinski
We present a unified framework for designing polynomial time approximation schemes (PTASs) for “dense ” instances of many NP-hard optimization problems, including maximum cut, graph bisection,...
Approximate graph coloring by semidefinite programming (1994)
z We consider the problem of coloring k-colorable graphs with the fewest possible colors. We present a randomized polynomial time algorithm which colors a 3-colorable graph on n vertices with...
Approximate Graph Coloring by Semidefinite Programming (1994)
David Karger, Rajeev Motwani, Madhu Sudan
We consider the problem of coloring k-colorable graphs with the fewest possible colors. We present a randomized polynomial time algorithm that colors a 3-colorable graph on n vertices with...
Job Scheduling in Rings (1994)
Perry Fizzano, David Karger, Clifford Stein, Joel Wein
We give distributed approximation algorithms for job scheduling in a ring architecture. In contrast to almost all other parallel scheduling models, the model we consider captures the influence of the...
Approximate Graph Coloring by Semidefinite Programming (1994)
David Karger, Rajeev Motwani, Madhu Sudan
We consider the problem of coloring k-colorable graphs with the fewest possible colors. We present a randomized polynomial time algorithm which colors a 3-colorable graph on n vertices with...
Approximate Graph Coloring by Semidefinite Programming (1994)
David Karger, Rajeev Motwani, Madhu Sudan
We consider the problem of coloring k-colorable graphs with the fewest possible colors. We present a randomized polynomial time algorithm which colors a 3-colorable graph on n vertices with...
On Approximating the Longest Path in a Graph (1993)
We consider the problem of approximating the longest path in undirected graphs. In an attempt to pin down the best achievable performance ratio of an approximation algorithm for this problem, we...
On Approximating the Longest Path in a Graph (1993)
We consider the problem of approximating the longest path in undirected graphs. In an attempt to pin down the best achievable performance ratio of an approximation algorithm for this problem, we...
We show that the minimum cut problem for weighted undirected graphs can be solved in NC using three separate and independently interesting results. The first is an (m 2 =n)-processor NC algorithm for...
Infranet: Circumventing Web Censorship and Surveillance
Nick Feamster Magdalena, Magdalena Balazinska, Greg Harfst, Hari Balakrishnan, David Karger
An increasing number of countries and companies routinely block or monitor access to parts of the Internet. To counteract these measures, we propose Infranet, a system that enables clients to...