Approximating the Weight of the Euclidean Minimum Spanning Tree in (2003)
Artur Czumaj, Funda Ergun, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, ...
We consider the problem of computing the weight of a Euclidean minimum spanning tree for a set of n points in R . We focus on the setting where the input point set is supported by certain basic (and...
Sublinear-Time Approximation of Euclidean Minimum Spanning Tree (2002)
Artur Czumaj, Funda Ergun, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, ...
We consider the problem of computing the weight of a Euclidean minimum spanning tree for a set of n points in R^d. We focus on the situation when the input point set is supported by certain basic...
Sublinear-Time Approximation of Euclidean Minimum Spanning Tree (2002)
Artur Czumaj, Funda Ergun, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, ...
We consider the problem of estimating the weight of a Euclidean minimum spanning tree for a set of n points in R . We focus on the situation when the input point set is supported by certain basic...
A Dynamic Lookup Scheme for Bursty Access Patterns (2001)
Funda Ergun, Suvo Mittra, Jonathan Sharp, Rakesh K. Sinha
The problem of fast address lookup is crucial to routing and thus has received considerable attention. Most of the work in this field has focused on improving the speed of individual accesses --...
Biased Skip Lists for Highly Skewed Access Patterns (2001)
Funda Ergun, Jonathan Sharp, Rakesh K. Sinha
Dynamic tables that support search, insert and delete operations are fundamental and well studied in computer science. There are many well known data structures that solve this problem, including...
We investigate the question of when a prover can aid a verifier to reliably compute a function faster than if the verifier were to compute the function on its own. Our focus is on the case when it is...
Funda Ergun, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan
On Labor Day weekend, the highway patrol sets up spot-checks at random points on the freeways with the intention of deterring a large fraction of motorists from driving incorrectly. We explore a very...
Learning Distributions from Random Walks (2000)
Funda Ergun, S Ravi Kumar, Ronitt Rubinfeld
We introduce a new model of distributions generated by random walks on graphs. This model suggests a variety of learning problems, using the definitions and models of distribution learning defined in...
We investigate the problem of when a prover can aid a verifier to reliably compute a function faster than if the verifier were to compute the function on its own. We focus on the case when it is...
Funda Ergun, Sampath Kannan, S Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan
On Labor Day weekend, the highway patrol sets up spot-checks at random points on the freeways with the intention of deterring a large fraction of motorists from driving incorrectly. We explore a very...
Funda Ergun, Sampath Kannan, S Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan
On Labor Day weekend, the highway patrol sets up spot-checks at random points on the freeways with the intention of deterring a large fraction of motorists from driving incorrectly. We explore a very...
Learning Distributions from Random Walks (1999)
Funda Ergun, S Ravi Kumar, Ronitt Rubinfeld
We introduce a new model of distributions generated by random walks on graphs. This model suggests a variety of learning problems, using the definitions and models of distribution learning defined in...
Approximate Checking of Polynomials and Functional Equations (1999)
Funda Ergun, S Ravi, Kumar Ronitt Rubinfeld
In this paper, we show how to check programs that compute polynomials and functions defined by addition theorems --- in the realistic setting where the output of the program is approximate instead of...
Funda Ergun, Sampath Kannan, S Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan
On Labor Day Weekend, the highway patrol sets up spotchecks at random points on the freeways with the intention of deterring a large fraction of motorists from driving incorrectly. We explore a very...
We investigate the problem of when a prover can aid a verifier to reliably compute a function faster than if the verifier were to compute the function on its own. We focus on the case when it is...
Funda Ergun, Sampath Kannan, S Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan
On Labor Day Weekend, the highway patrol sets up spotchecks at random points on the freeways with the intention of deterring a large fraction of motorists from driving incorrectly. We explore a very...
Approximate Checking of Polynomials and Functional Equations (1998)
Funda Ergun, S Ravi, Kumar Ronitt Rubinfeld
In this paper, we show how to check programs that compute polynomials and functions defined by addition theorems --- in the realistic setting where the output of the program is approximate instead of...
Approximate Checking of Polynomials and Functional Equations (1998)
Funda Ergun, S Ravi, Kumar Ronitt Rubinfeld
In this paper, we show how to check programs that compute polynomials and functions defined by addition theorems --- in the realistic setting where the output of the program is approximate instead of...
Funda Ergun, Sampath Kannan, S Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan
On Labor Day Weekend, the highway patrol sets up spotchecks at random points on the freeways with the intention of deterring a large fraction of motorists from driving incorrectly. We explore a very...
Funda Ergun, Sampath Kannan, S Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan
On Labor Day Weekend, the highway patrol sets up spotchecks at random points on the freeways with the intention of deterring a large fraction of motorists from driving incorrectly. We explore a very...
Approximate Checking of Polynomials and Functional Equations (1998)
Funda Ergun, S Ravi, Kumar Ronitt Rubinfeld
In this paper, we show how to check programs that compute polynomials and functions defined by addition theorems --- in the realistic setting where the output of the program is approximate instead of...
Learning Distributions from Random Walks (1997)
Funda Ergun, S Ravi Kumar, Ronitt Rubinfeld
We introduce a new model of distributions generated by random walks on graphs. This model suggests a variety of learning problems, using the definitions and models of distribution learning defined in...
Testing Multivariate Linear Functions: Overcoming the Generator Bottleneck (1994)
The problem of testing program correctness has received considerable attention in computer science. One approach to this problem is the notion of self-testing programs [BLR90]. Selftesting usually...
Testing Multivariate Linear Functions:Overcoming the GeneratorBottleneck (1994)
The problem of testing program correctness has received considerable attention in computer science. One approach to this problem is the notion of self-testing programs \cite{BlumLubyRubinfeld}....
QoS Routing with Performance-Dependent Costs (1970)
Funda Ergun, Rakesh Sinha, Lisa Zhang
We study a network model in which each network link is associated with a set of delays and costs. These costs are a function of the delays and reflect the prices paid in return for delay guarantees....