11378639
Efficient Zero-Knowledge Proofs for Some Practical Graph Problems
From a cryptographic aspect zero-knowledge protocols for graph isomorphisms, graph non-isomorphisms, and graph-coloring are artificial problems, that received lots of attention. Due to recent work in network security in a broadcast setting, it seems important to design efficient zero-knowledge protocols for the following graph problems: independent set problem, neighbor independent set problem, and disjoint broadcast lines problem. In this paper, we will introduce a new concept of k-independent set problem which is a generalization of independent set and neighbor independent set problems, and we will present efficient zero-knowledge protocols for these problems. In the end of the paper we will give some cryptographic applications of k-independent set. Especially, we will point out the applications to the concept of "threshold" and appropriate access structures. Note that k-independent set also has applications outside cryptography, such as biology, methodology of scientific research, ethics, etc., which are beyond the scope of this paper.
5215725
Linear Complexity versus Pseudorandomness: On Beth and Dai's Result
Beth and Dai studied in their Eurocrypt paper [1] the relationship between linear complexity (that is, the length of the shortest Linear Feedback Shift Register that generates the given strings) of strings and the Kolmogorov complexity of strings. Though their results are correct, some of their proofs are incorrect. In this note, we demonstrate with a counterexample the reason why their proofs are incorrect and we prove a stronger result. We conclude our note with some comments on the use of the LIL test (the law of the iterated logarithm) for pseudorandom bits generated by pseudorandom generators.
8204880
Privacy aware data generation for testing database applications
Testing of database applications is of great importance. A significant issue in database application testing consists in the availability of representative data. In this paper, we investigate the problem of generating a synthetic database based on a-priori knowledge about a production database. Our approach is to fit general location model using various characteristics (e.g., constraints, statistics, rules) extracted from the production database and then generate the synthetic data using model learnt. The generated data is valid and similar to real data in terms of statistical distribution, hence it can be used for functional and performance testing. As characteristics extracted may contain information which may be used by attacker to derive some confidential information about individuals, we present our disclosure analysis method which applies cell suppression technique for identity disclosure analysis and perturbation for value disclosure.
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.
8247434
NP-Hard Sets are Superterse Unless NP is Small
Abstract We show that the class P- mc ( n ) of polynomial time n -membership comparable sets (defined by Ogihara, 1995) has p -measure 0. Using this result, we will show that the class of sets which are ⩽ tt P -reducible to some P-selective set has p -measure 0. Furthermore, we will show that if NP does not have p -measure 0 then no ⩽ tt p -hard set for NP is P-approximable.
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.
10936975
Quantifying Evolving Processes in Multimodal 3D Medical Images
Quantitative measurements of changes in evolving brain pathology, such as multiple sclerosis lesions and brain tumors, are important for clinicians to perform pertinent diagnoses and to help in patient follow-up. Lesions or tumors can vary over time in size, shape, location and composition because of natural pathological processes or the effect of a drug treatment or therapy. In the past, people have used as a quantitative measurement the change in total or regional lesion/tumor volume. In this paper we propose a new model to quantify changes in evolving processes in multimodal 3D medical images. We believe this model reflects changes in pathology more accurately because it simultaneously takes into account information in multiple imaging modalities and the location of lesion/tumor voxels. We demonstrate the effectiveness of this model with experiments on synthetic lesion data.
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.
16100691
Design multicast protocols for non-cooperative networks
Conventionally, most network protocols assume that the network entities that participate in the network activities will always behave as instructed. However, in practice, most network entities will try to maximize their own benefits instead of altruistically contribute to the network by following the prescribed protocols, which is known as selfish. Thus, new protocols should be designed for the non-cooperative network, which is composed of selfish entities. In this paper, we specifically show how to design strategyproof multicast protocols for non-cooperative networks such that these selfish entities will follow the protocols out of their own interests. By assuming that a group of receivers is willing to pay to receive the multicast service, we specifically give a general framework to decide whether it is possible, and how if possible to transform an existing multicast protocol to a strategyproof multicast protocol. We then show how the payments to those relay entities are shared fairly among all receivers so that it encourages collaboration among receivers. As a running example, we show how to design the strategyproof multicast protocol for the currently used core-based multicast structure. We also conduct extensive simulations to study the relations between payment and cost of the multicast structure.
11122272
Modeling with Structures in Statistical Machine Translation
Most statistical machine translation systems employ a word-based alignment model. In this paper we demonstrate that word-based alignment is a major cause of translation errors. We propose a new alignment model based on shallow phrase structures, and the structures can be automatically acquired from parallel corpus. This new model achieved over 10% error reduction for our spoken language translation task.
2617111
Efficient Algorithms for Traffic Grooming in SONET/WDM Networks
In SONET/WDM optical networks, a wavelength channel is shared by multiple low-rate traffic demands. The multiplexing is known as traffic grooming and carried out by SONET add-drop multiplexers (SADM). A key optimization problem in traffic grooming is to minimize the number of SADMs. This optimization problem is challenging and NP-hard even for unidirectional SONET/WDM rings (UPSR) with symmetric unitary traffic demands. In this paper, we give a linear time heuristic algorithm for this NP-hard problem. Empirical results show that the algorithm outperforms previous algorithms. The algorithm uses the minimum number of wavelengths, which are also precious resources in optical networks. An important subclass of the symmetric unitary traffic pattern is the regular traffic pattern, where each network node appears in exactly r symmetric demands. The regular traffic pattern is a generalization of the well known all-to-all traffic pattern, in which r = n - 1 for a network of n nodes. We prove that the optimization problem remains NP-hard for the regular traffic pattern on the UPSR. We also propose an algorithm for this problem with a better upper bound on the number of used SADMs than previous algorithms. This algorithm always uses the minimum number of wavelengths as well