Property testers form an important class of sublinear-time algorithms. In the standard property testing model, an algorithm accesses the input function $f :\mathcal{D} \mapsto {\cal R}$ via an oracle. With very few exceptions, all property testers studied in this model rely on the oracle to provide function values at all queried domain points. However, in many realistic situations, the oracle may be unable to reveal the function values at some domain points due to privacy concerns, or when some of the values get erased by mistake or by an adversary. The testers do not learn anything useful about the function by querying those erased points. Moreover, the knowledge of a tester may enable an adversary to erase some of the values so as to increase the query complexity of the tester arbitrarily or, in some cases, make the tester entirely useless. In this work, we initiate a study of property testers that are resilient to the presence of adversarially erased function values. An $\alpha$-erasure-resilient $\varepsilon$-tester is given parameters $\alpha \in [0,1),\varepsilon\in (0,1)$, along with oracle access to a function $f$ such that at most an $\alpha$ fraction of function values have been erased. The tester does not know whether a value is erased until it queries the corresponding domain point. The tester has to accept with high probability if there is a way to assign values to the erased points such that the resulting function satisfies the desired property $\mathcal{P}$. It has to reject with high probability if, for every assignment of values to the erased points, the resulting function has to be changed in at least an $\varepsilon$ fraction of the nonerased domain points to satisfy $\mathcal{P}$. Erasure-resilient testing generalizes the standard property testing model of Rubinfeld and Sudan [ SIAM J. Comput., 25 (1996), pp. 252--271] and Goldreich, Goldwasser, and Ron [ J. ACM, 45 (1998), pp. 653--750]. Compared to the tolerant testing model of Parnas, Ron, and Rubinfeld [ J. Comput. System Sci., 6 (2006), pp. 1012--1042], our model places less stringent requirements on the tester. We design erasure-resilient property testers for a large class of properties. For some properties, it is possible to obtain erasure-resilient testers by simply using standard testers as a black box. However, for some more challenging properties, all existing algorithms are more likely to query certain points in the domain. If these points are erased, the algorithms break. We give efficient erasure-resilient testers for several important classes of such properties of functions including monotonicity, the Lipschitz property, and convexity. Finally, we show a separation between the standard and erasure-resilient testing. Specifically, we describe a property that can be $\varepsilon$-tested with $O(1/\varepsilon)$ queries in the standard model, whereas testing it in the erasure-resilient model requires a number of queries polynomial in the input size.

The primary problem in property testing is to decide whether a given function satisfies a certain property or is far from any function satisfying it. This crucially requires a notion of distance between functions. The most prevalent notion is the Hamming distance over theuniformdistribution on the domain. This restriction to uniformity is rather limiting, and it is important to investigate distances induced by more general distributions. In this article, we provide simple and optimal testers forbounded derivative propertiesoverarbitrary product distributions. Bounded derivative properties include fundamental properties, such as monotonicity and Lipschitz continuity. Our results subsume almost all known results (upper and lower bounds) on monotonicity and Lipschitz testing over arbitrary ranges. We prove an intimate connection between bounded derivative property testing and binary search trees (BSTs). We exhibit a tester whose query complexity is the sum of expected depths of optimal BSTs for each marginal. Furthermore, we show that this sum-of-depths is also a lower bound. A technical contribution of our work is anoptimal dimension reduction theoremfor all bounded derivative properties that relates the distance of a function from the property to the distance of restrictions of the function to random lines. Such a theorem has been elusive even for monotonicity, and our theorem is an exponential improvement to the previous best-known result.

The primary problem in property testing is to decide whether a given function satisfies a certain property, or is far from any function satisfying it. This crucially requires a notion of distance between functions. The most prevalent notion is the Hamming distance over the uniform distribution on the domain. This restriction to uniformity is rather limiting, and it is important to investigate distances induced by more general distributions. In this paper, we give simple and optimal testers for bounded derivative properties over arbitrary product distributions. Bounded derivative properties include fundamental properties such as monotonicity and Lipschitz continuity. Our results subsume almost all known results (upper and lower bounds) on monotonicity and Lipschitz testing. We prove an intimate connection between bounded derivative property testing and binary search trees (BSTs). We exhibit a tester whose query complexity is the sum of expected depths of optimal BSTs for each marginal. Furthermore, we show this sum-of-depths is also a lower bound. A technical contribution of our work is an optimal dimension reduction theorem for all bounded derivative properties, which relates the distance of a function from the property to the distance of restrictions of the function to random lines. Such a theorem has been elusive even for monotonicity, and our theorem is an exponential improvement to the previous best known result.

In this paper, we present a novel ranking technique that we developed in the context of an application that arose in a Service Delivery setting. We consider the problem of ranking agents of a service organization. The service agents typically need to interact with other service agents to accomplish the end goal of resolving customer requests. Their ranking needs to take into account two aspects: firstly, their importance in the network structure that arises as a result of their interactions, and secondly, the value generated by the interactions involving them. We highlight several other applications which have the common theme of ranking the participants of a value creation process based on the network structure of their interactions and the value generated by their interactions. We formally present the problem and describe the modeling technique which enables us to encode the value of interaction in the graph. Our ranking algorithm is based on extension of eigen value methods. We present experimental results on real-life, public domain datasets from the Internet Movie DataBase. This makes our experiments replicable and verifiable.

UNLABELLED: Suffix tree is one of the most fundamental data structures in string algorithms and biological sequence analysis. Unfortunately, when it comes to implementing those algorithms and applying them to real genomic sequences, often the main memory size becomes the bottleneck. This is easily explained by the fact that while a DNA sequence of length n from alphabet sigma = {A, C, G, T} can be stored in n log absolute value(sigma) = 2n bits, its suffix tree occupies O(n log n) bits. In practice, the size difference easily reaches factor 50. We provide an implementation of the compressed suffix tree very recently proposed by Sadakane (Theory of Computing Systems, in press). The compressed suffix tree occupies space proportional to the text size, i.e. O(n log) absolute value(sigma)) bits, and supports all typical suffix tree operations with at most log n factor slowdown. Our experiments show that, e.g. on a 10 MB DNA sequence, the compressed suffix tree takes 10% of the space of normal suffix tree. Typical operations are slowed down by factor 60. AVAILABILITY: The C++ implementation under GNU license is available at http://www.cs.helsinki.fi/group/suds/cst/. An example program implementing a typical pattern discovery task is included. Experimental results in this note correspond to version 0.95.