Limited Randomness LT Codes (2008)
Chris Harrelson, Lawrence Ip, Wei Wang
LT codes are asymptotically optimal rateless erasure codes with highly efficient encoding and decoding algorithms. In the original analysis of these codes, it was assumed that for each encoding...
Limited Randomness LT Codes (2008)
Chris Harrelson, Lawrence Ip, Wei Wang
LT codes are asymptotically optimal rateless erasure codes with highly ecient encoding and decoding algorithms. In the original analysis of these codes, it was assumed that for each encoding symbol,...
Approximate classication via earthmover metrics (2007)
Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, Eva Tardos
Given a metric space (X; d), a natural distance measure on probability distributions over X is the earthmover metric. We use randomized rounding of earthmover metrics to devise new approximation...
Limited Randomness LT Codes (2007)
Chris Harrelson, Lawrence Ip, Wei Wang
LT codes are asymptotically optimal rateless erasure codes with highly e#cient encoding and decoding algorithms. In the original analysis of these codes, it was assumed that for each encoding symbol,...
Quantum Clock Synchronization With One Qubit (2007)
Chris Harrelson Uc, Chris Harrelson, Iordanis Kerenidis
The clock synchronization problem is to determine the time dierence T between two spatially separated parties. We improve on I. Chuang's quantum clock synchronization algorithm and show that it...
An analysis of distributed, Unix-based routers (Project report for CS 252, spring 2001) (2007)
In this report, we examine the challenges facing the construction of an Internet router based on commodity hardware and operating systems. Further, we present an architecture which attempts to...
Sampling from two-way contingency tables (2007)
This report describes the current state of research into the problem of sampling uniformly at random from contingency tables. It is meant to be combined with its oral presentation counterpart, which...
Computing the shortest path: A* search meets graph theory (2005)
Andrew V. Goldberg, Chris Harrelson
We study the problem of finding a shortest path between two vertices in a directed graph. This is an important problem with many applications, including that of computing driving directions. We allow...
Lower Bounds for Maximum Parsimony with Gene Order Data (2005)
Abraham Bachrach, Kevin Chen, Chris Harrelson, Radu Mihaescu, Satish Rao, Apurva Shah
Abstract. In this paper, we study lower bound techniques for branchand-bound algorithms for maximum parsimony, with a focus on gene order data. We give a simple O(n 3) time dynamic programming...
Approximate classification via earthmover metrics (2004)
Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, Éva Tardos
Given a metric space (X, d), a natural distance measure on probability distributions over X is the earthmover metric. We use randomized rounding of earthmover metrics to devise new approximation...
Approximate classification via earthmover metrics (2004)
Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, Eva Tardos
Given a metric space (X, d), a natural distance measure on probability distributions over X is the earthmover metric. We use randomized rounding of earthmover metrics to devise new approximation...
Lecture notes on computational complexity (2004)
Steve Chien, Jittat Fakcharoenphol, Chris Harrelson, Iordanis Kerenidis, Lawrence Ip, Ranjit Jhala, ...
These are scribed notes from a graduate courses on Computational Complexity o#ered at the University of California at Berkeley in the Fall of 2002, based on notes scribed by students in Spring 2001...
Computing the Shortest Path: A* Search Meets Graph Theory (2004)
Andrew V. Goldberg, Chris Harrelson
this paper we study one of the most common variants of the problem, where the goal is to nd a point-to-point shortest path in a directed graph. We refer to this problem as the P2P problem. We assume...
Approximate classification via earthmover metrics (2004)
Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, Éva Tardos
Given a metric space (X, d), a natural distance measure on probability distributions over X is the earthmover metric. We use randomized rounding of earthmover metrics to devise new approximation...
An improved approximation algorithm for the 0-extension problem (2003)
Jittat Fakcharoenphol, Chris Harrelson, Satish Rao, Kunal Talwar
Abstract Given a graph G = (V, E), a set of terminals T ` V, anda metric D on T, the 0-extension problem is to assignvertices in V to terminals, so that the sum, over all edges e, of the distance...
A polynomial-time tree decomposition to minimize congestion (2003)
ABSTRACT R"acke recently gave a remarkable proof showing that any undirected multicommodity flow problem can be routed in an oblivious fashion with congestion that is within a factor of...
A Polynomial-time Tree Decomposition to Minimize Congestion (2003)
Chris Harrelson, Kirsten Hildrum, Satish Rao
Racke recently gave a remarkable proof showing that any undirected multicommodity ow problem can be routed in an oblivious fashion with congestion that is within a factor of O(log n) of the best...
A Polynomial-time Tree Decomposition to Minimize Congestion (2003)
Chris Harrelson, Kirsten Hildrum, Satish Rao
Racke recently gave a remarkable proof showing that any undirected multicommodity ow problem can be routed in an oblivious fashion with congestion that is within a factor of O(log^3 n) of the best...
The k-Traveling Repairman Problem (2003)
Jittat Fakcharoenphol, Chris Harrelson, Satish Rao
We consider the k-traveling repairman problem, a generalization of the metric traveling repairman problem, also known as the minimum latency problem, to multiple repairmen. We give an...
The k-Traveling Repairman Problem (2003)
Jittat Fakcharoenphol, Chris Harrelson, Satish Rao
We consider the k-traveling repairman problem, a generalization of the metric traveling repairman problem, also known as the minimum latency problem, to multiple repairmen. We give an...
An improved approximation algorithm for the 0-extension problem (2003)
Jittat Fakcharoenphol, Chris Harrelson, Satish Rao, Kunal Talwar
Abstract Given a graph G = (V, E), a set of terminals T ` V, anda metric D on T, the 0-extension problem is to assignvertices in V to terminals, so that the sum, over all edges e, of the distance...
An Improved Approximation Algorithm for the 0-Extension Problem (2003)
Jittat Fakcharoenphol, Chris Harrelson, Satish Rao, Kunal Talwar
Given a graph G = (V, E), a set of terminals T V , and a metric D on T , the 0-extension problem is to assign vertices in V to terminals, so that the sum, over all edges e, of the distance (under D)...
A polynomial-time tree decomposition to minimize congestion (2003)
Chris Harrelson, Kirsten Hildrum, Satish Rao
Räcke recently gave a remarkable proof showing that any undirected multicommodity flow problem can be routed in an oblivious fashion with congestion that is within a factor of O(log 3 n) of the best...
Luca Trevisan, Andrej Bogdanov, Allison Coates, Steve Chien, Jittat Fakcharoenphol, Chris Harrelson, ...
These are scribed notes from a graduate courses on Computational Complexity offered at the University of California at Berkeley in the Fall of 2002, based on notes scribed by students in Spring 2001...
Luca Trevisan, Andrej Bogdanov, Allison Coates, Steve Chien, Jittat Fakcharoenphol, Chris Harrelson, ...
These are scribed notes from a graduate courses on Computational Complexity offered at the University of California at Berkeley in the Fall of 2002, based on notes scribed by students in Spring 2001...
Quantum Clock Synchronization with one qubit (2001)
Harrelson, Chris, Kerenidis, Iordanis
The clock synchronization problem is to determine the time difference T between two spatially separated parties. We improve on I. Chuang's quantum clock synchronization algorithm and show that it is...