Funda Ergün

SODA Conference 2008 Conference Paper

On distance to monotonicity and longest increasing subsequence of a data stream

• Funda Ergün
• Hossein Jowhari

SODA Conference 2006 Conference Paper

Oblivious string embeddings and edit distance approximations

• Tugkan Batu
• Funda Ergün
• Süleyman Cenk Sahinalp

I&C Journal 2004 Journal Article

Fast approximate probabilistically checkable proofs

• Funda Ergün
• Ravi Kumar
• Ronitt Rubinfeld

We investigate the question of when a verifier, with the aid of a proof, can reliably compute a function faster than it can without the proof. The proof system model that we use is based on a variant of the Probabilistically Checkable Proofs (PCP) model, in which a verifier can ascertain the correctness of the proof by looking at very few locations in the proof. However, known results in the PCP model require that the verifier spend time linear in the size of the input in order to determine where to query the proof. In this work, we focus on the case when it is enough for the verifier to know that the answer is close to correct, and develop an approximate PCP model. We construct approximate PCPs for several optimization problems, in which the total running time of the verifier is significantly less than the size of the input. For example, we give polylogarithmic time approximate PCPs for showing the existence of a large cut, or a large matching in a graph, and a small bin packing. In the process, we develop a set of tools for use in constructing these proof systems.

STOC Conference 2003 Conference Paper

A sublinear algorithm for weakly approximating edit distance

• Tugkan Batu
• Funda Ergün
• Joe Kilian
• Avner Magen
• Sofya Raskhodnikova
• Ronitt Rubinfeld
• Rahul Sami

We show how to determine whether the edit distance between two given strings is small in sublinear time. Specifically, we present a test which, given two n-character strings A and B, runs in time o(n) and with high probability returns " CLOSE " if their edit distance is O(n Α ), and " FAR " if their edit distance is Ω(n), where Α is a fixed parameter less than 1. Our algorithm for testing the edit distance works by recursively subdividing the strings A and B into smaller substrings and looking for pairs of substrings in A, B with small edit distance. To do this, we query both strings at random places using a special technique for economizing on the samples which does not pick the samples independently and provides better query and overall complexity. As a result, our test runs in time Õ(n max(Α/2, 2Α - 1\) ) for any fixed Α < 1. Our algorithm thus provides a trade-off between accuracy and efficiency that is particularly useful when the input data is very large.We also show a lower bound of Ω(n Α/2 ) on the query complexity of every algorithm that distinguishes pairs of strings with edit distance at most n Α from those with edit distance at least n/6.

SODA Conference 2003 Conference Paper

Sublinear-time approximation of Euclidean minimum spanning tree

• Artur Czumaj
• Funda Ergün
• Lance Fortnow
• Avner Magen
• Ilan Newman
• Ronitt Rubinfeld
• Christian Sohler

STOC Conference 2001 Conference Paper

Biased dictionaries with fast insert/deletes

• Funda Ergün
• Süleyman Cenk Sahinalp
• Jonathan Sharp
• Rakesh K. Sinha

A dictionary data structure supports efficient search, insert, and delete operations on n keys from a totally ordered universe. Red-black trees, 2-3 trees, AVL trees, skip lists and other classic data structures facilitate O (log n ) time search, insert and deletes, matching the information theoretic lower bound when access probabilities are uniform i.i.d. If access probabilities are non-uniform but still i.i.d., there are other weighted data structures such as D-trees, biased search trees, splay trees and treaps which can achieve optimality. In many applications, however, the source of nonuniformity in access probabilities is locality of reference : examples include memory, cache, disk and buffer management and emerging applications in internetwork traffic management. In such applications, the access probability of any given key is not i.i.d., but decreases with idle time since the last access to the key. It is possible to adjust the weighted dictionaries to achieve optimal search time even under time dependent distributions; however insert/delete times will be suboptimal at O (log n ). In this paper, we present a lazy updating scheme which can be applied to weighted dictionaries to improve their amortized insert/delete performance when access probabilities decrease with time; optimality of search time is preserved. More speci%cally, let r(k) be the number of distinct keys accessed since the last access to key k - that is r(k) is the move-to-front rank of k . Let rmax(k) be the maximum rank of k during its lifetime. Then our lazy update scheme enables the abovementioned data structures to perform search in O (log r(k) ) time and insert/delete in O (log rmax(k) ) time. We illustrate our lazy update scheme in the context of a new Biased Skip List data structure and show that our bounds are optimal.

STOC Conference 1999 Conference Paper

Fast Approximate PCPs

• Funda Ergün
• Ravi Kumar 0001
• Ronitt Rubinfeld

STOC Conference 1998 Conference Paper

Spot-Checkers

• Funda Ergün
• Sampath Kannan
• Ravi Kumar 0001
• Ronitt Rubinfeld
• Mahesh Viswanathan 0001

FOCS Conference 1996 Conference Paper

Approximate Checking of Polynomials and Functional Equations (extended abstract)

• Funda Ergün
• Ravi Kumar 0001
• Ronitt Rubinfeld

The authors 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 exact. They present results showing how to perform approximate checking, self-testing, and self-correcting of polynomials, settling in the affirmative a question raised by Gemmell et al. (1991), and Rubinfeld and Sudan (1992, 1996). They then show how to perform approximate checking, self-testing, and self-correcting for those functions that satisfy addition theorems, settling a question raised by Rubinfeld (1994]) In both cases, they show that the properties used to test programs for these functions are both robust (in the approximate sense) and stable. Finally, they explore the use of reductions between functional equations in the context of approximate self-testing. Their results have implications to the stability theory of functional equations.

STOC Conference 1995 Conference Paper

Testing multivariate linear functions: overcoming the generator bottleneck

• Funda Ergün