41292415
Randomness, Stochasticity and Approximations
Polynomial time unsafe approximations for intractable sets were introduced by Meyer and Paterson [9] and Yesha [19], respectively. The question of which sets have optimal unsafe approximations has been investigated extensively; see, e.g., [1], [5], [15], and [17]. Recently, Wang [15], [17] showed that polynomial time random sets are neither optimally unsafe approximable nor Δ -levelable. In this paper we show that: (1) There exists a polynomial time stochastic set in the exponential time complexity class which has an optimal unsafe approximation. (2) There exists a polynomial time stochastic set in the exponential time complexity class which is Δ -levelable. The above two results answer a question asked by Ambos-Spies and Lutz [2]: What kind of natural complexity property can be characterized by p -randomness but not by p -stochasticity? Our above results also extend Ville's [13] historical result. The proof of our first result shows that, for Ville's stochastic sequence, we can find an optimal prediction function f such that we will never lose our own money betting according to f (except the money we have earned), that is to say, if at the beginning we have only $1 and we always bet $1 that the next selected bit is 1 , then we always have enough money to bet on the next bit. Our second result shows that there is a stochastic sequence for which there is a betting strategy f such that we will never lose our own money betting according to f (except the money we have earned), but there is no such optimal betting strategy. That is to say, for any such betting strategy, we can find another betting strategy which could be used to make money more quickly.
1602403
Using Mobile Agent Results to Create Hard-to-Detect Computer Viruses
The theory of computer viruses has been studied by several authors, though there is no systematic theoretical study up to now. The long time open question in this area is as follows: Is it possible to design a signature-free (including dynamic signatures which we will define late) virus? In this paper, we give an affirmative answer to this question from a theoretical viewpoint. We will introduce a new stronger concept: dynamic signatures of viruses, and present a method to design viruses which are static signature-free and whose dynamic signatures are hard to determine unless some cryptographic assumption fails. We should remark that our results are only for theoretical interest and may be resource intensive in practice.
16463784
Privacy Preserving Data Generation for Database Application Performance Testing
Synthetic data plays an important role in software testing. In this paper, we initiate the study of synthetic data generation models for the purpose of application software performance testing. In particular, we will discuss models for protecting privacy in synthetic data generations. Within this model, we investigate the feasibility and techniques for privacy preserving synthetic database generation that can be used for database application performance testing. The methodologies that we will present will be useful for general privacy preserving software performance testing.
5782664
A Separation of Two Randomness Concepts
In this paper we give an affirmative answer to a conjecture by Lutz (1992). That is, we will show that there is a Schnorr random sequence which is not rec-random.
16439255
Privacy Aware Market Basket Data Set Generation: A Feasible Approach for Inverse Frequent Set Mining
Association rule mining has received a lot of attention in the data mining community and several algorithms were proposed to improve the performance of association rule or frequent itemset mining. The IBM Almaden synthetic data generator has been commonly used for performance evaluation. One recent work shows that the data generated is not good enough for benchmarking as it has very different characteristics from real-world data sets. Hence there is a great need to use real-world data sets as benchmarks. However, organizations hesitate to provide their data due to privacy concerns. Recent work on privacy preserving association rule mining addresses this issue by modifying real data sets to hide sensitive or private rules. However, modifying individual values in real data may impact on other, non-sensitive rules. In this paper, we propose a feasible solution to the NPcomplete problem of inverse frequent set mining. Since solving this problem by linear programming techniques is very computationally prohibitive, we apply graph-theoretical results to divide the original itemsets into components that preserve maximum likelihood estimation. We then use iterative proportional fitting method to each component. The technique is experimentally evaluated with two real data sets and one synthetic data set. The results show that our approach is effective and efficient for reconstructing market basket data set from a given set of frequent itemsets while preserving sensitive information.
8968053
Resource-Bounded Balanced Genericity, Stochasticity and Weak Randomness
We introduce balanced t(n)-genericity which is a refinement of the genericity concept of Ambos-Spies, Fleischhack and Huwig [2] and which in addition controls the frequency with which a condition is met. We show that this concept coincides with the resource-bounded version of Church's stochasticity [6]. By uniformly describing these concepts and weaker notions of stochasticity introduced by Wilber [19] and Ko [11] in terms of prediction functions, we clarify the relations among these resource-bounded stochasticity concepts. Moreover, we give descriptions of these concepts in the framework of Lutz's resource-bounded measure theory [13] based on martingales: We show that t(n)-stochasticity coincides with a weak notion of t(n)-randomness based on so-called simple martingales but that it is strictly weaker than t(n)-randomness in the sense of Lutz.
6837149
Hausdorff distance under translation for points and balls
We study the shape matching problem under the Hausdorff distance and its variants. Specifically, we consider two sets A,B of balls in Rd, d=2,3, and wish to find a translation t that minimizes the Hausdorff distance between A+t, the set of all balls in A shifted by t, and B. We consider several variants of this problem. First, we extend the notion of Hausdorff distance from sets of points to sets of balls, so that each ball has to be matched with the nearest ball in the other set. We also consider the problem in the standard setting, by computing the Hausdorff distance between the unions of the two sets (as point sets). Second, we consider either all possible translates t (as is the standard approach), or consider only translations that keep the balls of A+t disjoint from those of B. We propose several exact and approximation algorithms for these problems. Since the Hausdorff distance is sensitive to outliers, we also propose efficient approximation algorithms for computing the minimum root mean-square (rms) and the minimum summed Hausdorff distance, under translation, between two point sets in Rd. In order to obtain a fast algorithm for the summed Hausdorff distance, we propose a deterministic efficient dynamic data structure for maintaining an e-approximation of the 1-median of a set of points, under insertion and deletion.
13960849
NTS6: IPv6 based Network Topology Service System of CERNET2
In this paper, we propose NTS6, an IPv6 based network topology service system, which provides a query and response service of network topology information between any pair of hosts accessing IPv6 Internet via CERNET2. The NTS6 system periodically collects the latest OSPF, BGP and SNMP information of CERNET2. Based on these information, NTS6 provides network topology information such as net distance, available bandwidth and path packet loss in response to users' query. The real-world experiment on CERNET2 confirms the accuracy of our system. Also, NTS6 now performs well on large deployed maze P2P file-sharing system. We believe NTS6 will be a powerful middleware for other applications.
15443235
Computing the Writhing Number of a Polygonal Knot
AbstractThe writhing number measures the global geometry of
 a closed space curve or knot.
 We show that this measure is related to the average winding number
 of its Gauss map.
 Using this relationship, we give an algorithm for computing
 the writhing number for a polygonal knot with n edges
 in time roughly proportional to n1.6.
 We also implement a different, simple algorithm and provide
 experimental evidence for its practical efficiency.


34251654
Near-Linear Time Approximation Algorithms for Curve Simplification
We consider the problem of approximating a polygonal curve P under a given error criterion by another polygonal curve P? whose vertices are a subset of the vertices of P. The goal is to minimize the number of vertices of P? while ensuring that the error between P? and P is below a certain threshold. We consider two fundamentally different error measures -- Hausdorff and Frechet error measures. For both error criteria, we present near-linear time approximation algorithms that, given a parameter ? > 0, compute a simplified polygonal curve P? whose error is less than ? and size at most the size of an optimal simplified polygonal curve with error ?/2. We consider monotone curves in the case of Hausdorff error measure and arbitrary curves for the Frechet error measure. We present experimental results demonstrating that our algorithms are simple and fast, and produce close to optimal simplifications in practice.
10803461
Iterative normalization of cDNA microarray data
Describes an approach to normalizing microarray expression data. The novel feature is to unify the tasks of estimating normalization coefficients and identifying the control gene set. Unification is realized by constructing a window function over the scatter plot defining the subset of constantly expressed genes and by affecting optimization using an iterative procedure. The structure of window function gates contributions to the control gene set used to estimate normalization coefficients. This window measures the consistency of the matched neighborhoods in the scatter plot and provides a means of rejecting control gene outliers. The recovery of normalizational regression and control gene selection are interleaved and are realized by applying coupled operations to the mean square error function. In this way, the two processes bootstrap one another. We evaluate the technique on real microarray data from breast cancer cell lines and complement the experiment with a data cluster visualization study.