A Note on the Limits of Collusion-Resistant (2008)
Funda Ergun, Joe Kilian, Ravi Kumar
Abstract. In one proposed use of digital watermarks, the owner of a document D sells slightly different documents, D1; D2; : : : to each buyer; if a buyer posts his/her document Di to the web, the...
A Note on the Limits of Collusion-Resistant (2008)
Funda Ergun, Joe Kilian, Ravi Kumar
Abstract. In one proposed use of digital watermarks, the owner of a document D sells slightly different documents, D1; D2; : : : to each buyer; if a buyer posts his/her document Di to the web, the...
Periodicity Testing with Sublinear Samples and Space (2008)
Funda Ergun, S. Muthukrishnan, S. Cenk Sahinalp
Abstract In this work, we are interested in finding representative trends in long large data streamsin the presence of computational constraints; to this end we present algorithms for discovering...
Checking Properties of Polynomials (Extended Abstract) (2007)
Bruno Codenotti, Funda Ergun, Peter Gemmell, S Ravi Kumar
) Bruno Codenotti, 1 Funda Ergun, 2 Peter Gemmell, 3 and S Ravi Kumar 2 1 IMC-CNR, Via S. Maria 46, 56126-Pisa, Italy. (codenotti@imc.pi.cnr.it) 2 Cornell University, Ithaca, NY 14853. (fergun,...
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 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, 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...
1 A Dynamic Lookup Scheme for Bursty Access Patterns (2007)
Funda Ergun, Suvo Mittra, Jonathan Sharp, Rakesh K. Sinha
Abstract---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...
Sahinalp. Oblivious string embeddings and edit distance approximations (2005)
Abstract We introduce an oblivious embedding that maps stringsof length n under edit distance to strings of length atmost n/r under edit distance for any value of parameter r. For any given r, our...
Oblivious String Embeddings and Edit Distance Approximations (2005)
Tugkan Batu Funda, Funda Ergun, Cenk Sahinalp
We introduce an oblivious embedding that maps any string of length n to a string of length at most n/r for any user specified value of r. For any given r, our embedding provides a distortion of O(r...
Oblivious String Embeddings and Edit Distance Approximations (2005)
Tugkan Batu Funda, Funda Ergun, Cenk Sahinalp
We introduce an oblivious embedding that maps any string of length n to a string of length at most n/r for any user specified value of r. For any given r, our embedding provides a distortion of O(r...
A sublinear algorithm for weakly approximating edit distance (2003)
Batu, Tugkan, Ergun, Funda, Kilian, Joe, Magen, Avner, Raskhodnikova, Sofya, Rubinfeld, Robin, ...
Comparing sequences with segment rearrangements (2003)
Funda Ergun, S. Muthukrishnan, S. Cenk Sahinalp
Abstract. Computational genomics involves comparing sequences based on "similarity " for detecting evolutionary and functional relation-ships. Until very recently, available...
Comparing sequences with segment rearrangements (2003)
Funda Ergun, S. Muthukrishnan, S. Cenk Sahinalp
Center for Comp. Genomics, CWRU.
Sublinear-Time Approximation of Euclidean Minimum Spanning Tree (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^d. We focus on the situation when the input point set is supported by certain basic...
Biased skip lists for highly skewed access patterns (2001)
Funda Ergun, S. Cenk S, Jonathan Sharp, Rakesh K. Sinha
Abstract. 1 Dynamic tables that support search, insert and delete operations arefundamental and well studied in computer science. There are many well known data structures that solve this problem,...
Biased skip lists for highly skewed access patterns (2001)
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...
A Dynamic Lookup Scheme for Bursty Access Patterns (2001)
Funda Ergun Suvo, Funda Ergun, Suvo Mittra, Süleyman Cenk S¸ahinalp
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 --...
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...
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 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}....
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}....