Companies are often motivated to evaluate their environmental sustainability, and to make public pronouncements about their performance with respect to quantitative sustainability metrics. Public trust in these declarations is enhanced if the claims are certified by a recognized authority. Because accurate evaluations of environmental impacts require detailed information about industrial processes throughout a supply chain, protecting the privacy of input data in sustainability assessment is of paramount importance. We introduce a new paradigm, called privacy-preserving certification, that enables the computation of sustainability indicators in a privacy-preserving manner, allowing firms to be classified based on their individual performance without revealing sensitive information to the certifier, other parties, or the public. In this work, we describe different variants of the certification problem, highlight the necessary security requirements, and propose a provably-secure novel framework that performs the certification operations under the management of an authorized, yet untrusted, party without compromising confidential information.

Life Cycle Assessment(LCA) is crucial for evaluating the ecological sustainability of a product or service, and the accurate evaluation of sustainability requires detailed and transparent information about industrial activities. However, such information is usually considered confidential and withheld from the public. In this paper, we present a rigorous study of privacy in the context of LCA. The main goal is to explore the privacy challenges in sustainability assessment considering the protection of trade secrets while increasing transparency of industrial activities. To overcome privacy concerns, we apply differential privacy to LCA computations considering the idiosyncratic features of LCA data. Our assessments on a specific real-life example show that it is possible to achieve privacy-preserving LCA computations without losing the utility of data completely.

We introduce a matrix decomposition method and prove that multiplication in GF$(2^k)$with a Type 1 optimal normal basis for can be performed using$k^2-1$XOR gates irrespective of the choice of the irreducible polynomial generating the field. The previous results achieved this bound only with special irreducible polynomials. Furthermore, the decomposition method performs the multiplication operation using$1.5k(k-1)$XOR gates for Type 2a and 2b optimal normal bases, which matches previous bounds.

A stateless multicounter machine has m-counters operating on a one-way input delimited by left and right end markers. A move of the machine depends only on the symbol under the input head and the sign pattern of the counters. An input string is accep

The increasing popularity of social networks has initiated a fertile research area in information extraction and data mining. Anonymization of these social graphs is important to facilitate publishing these data sets for analysis by external entities. Prior work has concentrated mostly on node identity anonymization and structural anonymization. But with the growing interest in analyzing social networks as a weighted network, edge weight anonymization is also gaining importance. We present Anónimos, a Linear Programming-based technique for anonymization of edge weights that preserves linear properties of graphs. Such properties form the foundation of many important graph-theoretic algorithms such as shortest paths problem, k-nearest neighbors, minimum cost spanning tree, and maximizing information spread. As a proof of concept, we apply Anónimos to the shortest paths problem and its extensions, prove the correctness, analyze complexity, and experimentally evaluate it using real social network data sets. Our experiments demonstrate that Anónimos anonymizes the weights, improves k-anonymity of the weights, and also scrambles the relative ordering of the edges sorted by weights, thereby providing robust and effective anonymization of the sensitive edge-weights. We also demonstrate the composability of different models generated using Anónimos, a property that allows a single anonymized graph to preserve multiple linear properties.

We consider stateless counter machines which mix the features of one-head counter machines and a special type of two-head Watson-Crick automata (WK-automata). Our Watson-Crick counter machines are biologically motivated. They have two heads that read the input starting from the two extremes. The reading process is finished when there are no more symbols between the heads, i.e., every letter of the input is processed by either head. Depending on whether the heads are required to advance at each move, we distinguish between realtime and non-realtime machines. If every counter makes at most k alternations between nondecreasing and decreasing modes in every computation, then the machine is k-reversal. It is reversal bounded if it is k-reversal for some k. In this paper we concentrate on the properties of both deterministic and nondeterministic stateless WK-automata with reversal bounded counters.

The increasing popularity of social networks has initiated a fertile research area in information extraction and data mining. Although such analysis can facilitate better understanding of sociological, behavioral, and other interesting phenomena, there is a growing concern about personal privacy being breached, thereby requiring effective anonymization techniques. In this paper, we consider edge weight anonymization in social graphs. Our approach builds a linear programming (LP) model which preserves properties of the graph that are expressible as linear functions of the edge weights. Such properties form the foundations of many important graph-theoretic algorithms such as shortest paths, k-nearest neighbors, minimum spanning tree, etc. Off-the-shelf LP solvers can then be used to find solutions to the resulting model where the computed solution constitutes the weights in the anonymized graph. As a proof of concept, we choose the shortest paths problem, and experimentally evaluate the proposed techniques using real social network data sets.

Let $e_k(x)$ denote the k-th partial sum of the Maclaurin series for the exponential function. Define the $(n+1)\times(n+1)$ Hankel determinant by setting $\widetilde{H}_n(x)=\det[e_{i+j}(x)]_{0\leq i,j\leq n}$. We give a closed form evaluation of this determinant in terms of the Bessel polynomials using the method of recently introduced $\gamma$-operators.

Deployed anonymous networks such as Tor focus on delivering messages through end-to-end paths with high anonymity. Selection of routers in the anonymous path construction is either performed randomly, or relies on self-described resource availability at routers, making systems vulnerable to low-resource attacks. In this paper, we investigate an alternative router and path selection mechanism for constructing efficient end-to-end paths with low loss of path anonymity. We propose a novel construct called a "route mesh," and a dynamic programming algorithm that determines optimal-latency paths from many random samples using only a small number of end-to-end measurements. We prove analytically that our path search algorithm finds the optimal path, and requires exponentially lower number of measurements compared to a standard measurement approach. In addition, our analysis shows that route meshes incur only a small loss in anonymity for its users.

This paper addresses the problem of efficient maintenance of a materialized skyline view in response to skyline removals. While there has been significant progress on skyline query computation, an equally important but largely unanswered issue is on the incremental maintenance for skyline deletions. Previous work suggested the use of the so called exclusive dominance region (EDR) to achieve optimal I/O performance for deletion maintenance. However, the shape of an EDR becomes extremely complex in higher dimensions, and algorithms for its computation have not been developed. We derive a systematic way to decompose a d-dimensional EDR into a collection of hyper-rectangles. We show that the number of such hyper-rectangles is O(md), where m is the current skyline result size. We then propose a novel algorithm DeltaSky which determines whether an intermediate R-tree MBR intersects with the EDR without explicitly calculating the EDR itself. This reduces the worse case complexity of the EDR intersection check from O(md) to O(md). Thus DeltaSky helps the branch and bound skyline algorithm achieve I/O optimality for deletion maintenance by finding only the newly appeared skyline points after the deletion. We discuss implementation issues and show that DeltaSky can be efficiently implemented using one extra B-Tree. Moreover, we propose two optimization techniques which further reduce the average cost in practice. Extensive experiments demonstrate that DeltaSky achieves orders of magnitude performance gain over alternative solutions.

Given two sequences X and Y, the classical dynamic programming solution to the local alignment problem searches for two subsequences I ⊆ X and J ⊆ Y with maximum similarity score under a given scoring scheme. In several applications, variants of this problem arise with different objectives and with length constraints on the subsequences I and J. This constraint can be explicit, such as requiring | I | + | J | ≥ t, or | J | ≤ T, or may be implicit such as in cyclic sequence comparison, or as in the maximization of length-normalized scores, and driven by practical considerations. We present a survey of approximation algorithms for various alignment problems with constraints, and several new approximation algorithms. These approximations are in two distinct senses: In one the constraints are satisfied but the score computed is within a prescribed tolerance of the optimum instead of the exact optimum. In another, the alignment returned is assured to have at least the optimum score with respect to the given constraints, but the length constraints are satisfied to within a prescribed tolerance from the required values. The algorithms proposed involve applications of techniques from fractional programming and dynamic programming.

As databases increasingly integrate different types of information such as multimedia, spatial, time-series, and scientific data, it becomes necessary to support efficient retrieval of multidimensional data. Both the dimensionality and the amount of data that needs to be processed are increasing rapidly. Reducing the dimension of the feature vectors to enhance the performance of the underlying technique is a popular solution to the infamous curse of dimensionality. We expect the techniques to have good quality of distance measures when the similarity distance between two feature vectors is approximated by some notion of distance between two lower-dimensional transformed vectors. Thus, it is desirable to develop techniques resulting in accurate approximations to the original similarity distance. We investigate dimensionality reduction techniques that directly target minimizing the errors made in the approximations. In particular, we develop dynamic techniques for efficient and accurate approximation of similarity evaluations between high-dimensional vectors based on inner-product approximations. Inner-product, by itself, is used as a distance measure in a wide area of applications such as document databases. A first order approximation to the inner-product is obtained from the Cauchy-Schwarz inequality. We extend this idea to higher order power symmetric functions of the multidimensional points. We show how to compute fixed coefficients that work as universal weights based on the moments of the probability density function of the data set. We also develop a dynamic model to compute the universal coefficients for data sets whose distribution is not known. Our experiments on synthetic and real data sets show that the similarity between two objects in high-dimensional space can be accurately approximated by a significantly lower-dimensional representation.

The Smith-Waterman algorithm for local sequence alignment is one of the most important techniques in computational molecular biology. This ingenious dynamic programming approach was designed to reveal the highly conserved fragments by discarding poorly conserved initial and terminal segments. However, the existing notion of local similarity has a serious flaw: it does not discard poorly conserved intermediate segments. The Smith-Waterman algorithm finds the local alignment with maximal score but it is unable to find local alignment with maximum degree of similarity (e.g., maximal percent of matches). Moreover, there is still no efficient algorithm that answers the following natural question: do two sequences share a (sufficiently long) fragment with more than 70% of similarity? As a result, the local alignment sometimes produces a mosaic of well-conserved fragments artificially connected by poorly-conserved or even unrelated fragments. This may lead to problems in comparison of long genomic sequences and comparative gene prediction as recently pointed out by Zhang et al., 1999 [33]. In this paper we propose a new sequence comparison algorithm (normalized local alignment) that reports the regions with maximum degree of similarity. The algorithm is based on fractional programming and its running time is Ο(n2 log n). In practice, normalized local alignment is only 3-5 times slower than the standard Smith-Waterman algorithm.

The Smith-Waterman algorithm for local sequence alignment is one of the most important techniques in computational molecular biology. This ingenious dynamic programming approach was designed to reveal the highly conserved fragments by discarding poorly conserved initial and terminal segments. However, the existing notion of local similarity has a serious flaw: it does not discard poorly conserved intermediate segments. The Smith-Waterman algorithm finds the local alignment with maximal score but it is unable to find local alignment with maximum degree of similarity (e.g. maximal percent of matches). Moreover, there is still no efficient algorithm that answers the following natural question: do two sequences share a (sufficiently long) fragment with more than 70% of similarity? As a result, the local alignment sometimes produces a mosaic of well-conserved fragments artificially connected by poorly-conserved or even unrelated fragments. This may lead to problems in comparison of long genomic sequences and comparative gene prediction as recently pointed out by Zhang et al. (Bioinformatics, 15, 1012-1019, 1999). In this paper we propose a new sequence comparison algorithm (normalized local alignment ) that reports the regions with maximum degree of similarity. The algorithm is based on fractional programming and its running time is O(n2log n). In practice, normalized local alignment is only 3-5 times slower than the standard Smith-Waterman algorithm.

We d e v elop dynamic dimensionality reduction based on the appro ximationof the standard inner-product.The innerproduct, by itself, is used as a distance measure in a wide area of applications such as document databases, e.g.latent semantic indexing (LSI).A rst order approximation to the inner-product is usually obtained from the Cauchy-Schw arz inequality.The method proposed in this paper re nes such a n appro ximation b y using higher order pow er symmetric functions of the components of the v ectors, whic h a r e p o w ers of the p-norms of the vectors for p = 1 ; 2; : : : ; m .We s h o w h o w to compute xed coecients that work as universal weights based on the moments of the probability density function assumed for the distribution of the components of the input vectors in the data set.Our experiments on syn thetic and document d a t a s h o w that with this technique, the similarity between tw o objects in high dimensional space for certain applications can be accurately approximated by a signi cantly low er dimensional representation.

Fully populated torus-connected networks, where every node has a processor attached, do not scale well since load on edges increases superlinearly with network size under heavy communication, resulting in a degradation in network throughput. In a partially populated network, processors occupy a subset of available nodes and a routing algorithm is specified among the processors placed. Analogous to multistage networks, it is desirable to have the total number of messages being routed through a particular edge in toroidal networks increase at most linearly with the size of the placement. To this end, we consider placements of processors which are described by a given placement algorithm parameterized by k and d: We show formally, that to achieve linear communication load in a d-dimensional k-torus, the number of processors in the placement must be equal to ck/sup d-1/ for some constant c. Our approach also gives a tighter lower bound than existing bounds for the maximum load of a placement for arbitrary number of dimensions for placements with sufficient symmetries. Based on these results, we give optimal placements and corresponding routing algorithms achieving linear communication load in tori with arbitrary number of dimensions.

Novel techniques based on the Discrete Fourier Transform are proposed to estimate the size of relations resulting from join operations. For the special case of self join the proposed algorithm gives the exact join size using logarithmic space. A generalization to compute the join of arbitrary relations is then used to develop two tree-based techniques that provide a spectrum of algorithms which interpolate storage requirements versus accuracy of the estimation obtained. Finally, we present experimental results to exhibit the effectiveness of our approach. 1

A generalization of the majority quorum for the solution of the distributed (k+1)-exclusion problem is proposed. This scheme produces a family of quorums of varying sizes and availabilities indexed by integral divisors r of k. The cases r=1 and r=k correspond to known majority based quorum generation algorithms MAJ and DIV, whereas intermediate values of r interpolate between these two extremes. A cost and availability analysis of the proposed methods is also presented. An interesting implication of this analysis is that in a reasonably reliable environment with a large number of sites, even protocols with low communication costs attain high availability.