OpenRaiser/Intern-Atlas huggingface dataset:
Conference Key Agreement and Quantum Sharing of Classical Secrets with Noisy GHZ States
Venue: arXiv cs.IT 2005
Year: 2005

We propose a wide class of distillation schemes for multi-partite entangled states that are CSS-states. Our proposal provides not only superior efficiency, but also new insights on the connection between CSS-states and bipartite graph states. We then consider the applications of our distillation schemes for two cryptographic tasks--namely, (a) conference key agreement and (b) quantum sharing of classical secrets. In particular, we construct ``prepare-and-measure'' protocols. Also we study the yield of those protocols and the threshold value of the fidelity above which the protocols can function securely. Surprisingly, our protocols will function securely even when the initial state does not violate the standard Bell-inequalities for GHZ states. Experimental realization involving only bi-partite entanglement is also suggested.
Corpus-based Learning of Analogies and Semantic Relations
Venue: arXiv cs.LG 2005
Year: 2005

We present an algorithm for learning from unlabeled text, based on the Vector Space Model (VSM) of information retrieval, that can solve verbal analogy questions of the kind found in the SAT college entrance exam. A verbal analogy has the form A:B::C:D, meaning "A is to B as C is to D"; for example, mason:stone::carpenter:wood. SAT analogy questions provide a word pair, A:B, and the problem is to select the most analogous word pair, C:D, from a set of five choices. The VSM algorithm correctly answers 47% of a collection of 374 college-level analogy questions (random guessing would yield 20% correct; the average college-bound senior high school student answers about 57% correctly). We motivate this research by applying it to a difficult problem in natural language processing, determining semantic relations in noun-modifier pairs. The problem is to classify a noun-modifier pair, such as "laser printer", according to the semantic relation between the noun (printer) and the modifier (laser). We use a supervised nearest-neighbour algorithm that assigns a class to a given noun-modifier pair by finding the most analogous noun-modifier pair in the training data. With 30 classes of semantic relations, on a collection of 600 labeled noun-modifier pairs, the learning algorithm attains an F value of 26.5% (random guessing: 3.3%). With 5 classes of semantic relations, the F value is 43.2% (random: 20%). The performance is state-of-the-art for both verbal analogies and noun-modifier relations.
A Tracer Driver for Versatile Dynamic Analyses of Constraint Logic Programs
Venue: arXiv cs.SE 2005
Year: 2005

Programs with constraints are hard to debug. In this paper, we describe a general architecture to help develop new debugging tools for constraint programming. The possible tools are fed by a single general-purpose tracer. A tracer-driver is used to adapt the actual content of the trace, according to the needs of the tool. This enables the tools and the tracer to communicate in a client-server scheme. Each tool describes its needs of execution data thanks to event patterns. The tracer driver scrutinizes the execution according to these event patterns and sends only the data that are relevant to the connected tools. Experimental measures show that this approach leads to good performance in the context of constraint logic programming, where a large variety of tools exists and the trace is potentially huge.
A Generic Framework for the Analysis and Specialization of Logic Programs
Venue: arXiv cs.PL 2005
Year: 2005

The relationship between abstract interpretation and partial deduction has received considerable attention and (partial) integrations have been proposed starting from both the partial deduction and abstract interpretation perspectives. In this work we present what we argue is the first fully described generic algorithm for efficient and precise integration of abstract interpretation and partial deduction. Taking as starting point state-of-the-art algorithms for context-sensitive, polyvariant abstract interpretation and (abstract) partial deduction, we present an algorithm which combines the best of both worlds. Key ingredients include the accurate success propagation inherent to abstract interpretation and the powerful program transformations achievable by partial deduction. In our algorithm, the calls which appear in the analysis graph are not analyzed w.r.t. the original definition of the procedure but w.r.t. specialized definitions of these procedures. Such specialized definitions are obtained by applying both unfolding and abstract executability. Our framework is parametric w.r.t. different control strategies and abstract domains. Different combinations of such parameters correspond to existing algorithms for program analysis and specialization. Simultaneously, our approach opens the door to the efficient computation of strictly more precise results than those achievable by each of the individual techniques. The algorithm is now one of the key components of the CiaoPP analysis and specialization system.
Asymptotically fast polynomial matrix algorithms for multivariable systems
Venue: arXiv cs.SC 2005
Year: 2005

We present the asymptotically fastest known algorithms for some basic problems on univariate polynomial matrices: rank, nullspace, determinant, generic inverse, reduced form. We show that they essentially can be reduced to two computer algebra techniques, minimal basis computations and matrix fraction expansion/reconstruction, and to polynomial matrix multiplication. Such reductions eventually imply that all these problems can be solved in about the same amount of time as polynomial matrix multiplication.
Unified Theory of Source Coding: Part II -- Multiterminal Problems
Venue: arXiv cs.IT 2005
Year: 2005

In the first paper of this two part communication, we solved in a unified framework a variety of two terminal source coding problems with noncooperative encoders, thereby consolidating works of Shannon, Slepian-Wolf, Wyner, Ahlswede-Körner, Wyner-Ziv, Berger {\em et al.} and Berger-Yeung. To achieve such unification we made use of a fundamental principle that dissociates bulk of the analysis from the distortion criterion at hand (if any) and extends the typicality arguments of Shannon and Wyner-Ziv. In this second paper, we generalize the fundamental principle for any number of sources and on its basis exhaustively solve all multiterminal source coding problems with noncooperative encoders and one decoder. The distortion criteria, when applicable, are required to apply to single letters and be bounded. Our analysis includes cases where side information is, respectively, partially available, completely available and altogether unavailable at the decoder. As seen in our first paper, the achievable regions permit infinite order information-theoretic descriptions. We also show that the entropy-constrained multiterminal estimation problem can be solved as a special case of our theory.
Streaming and Sublinear Approximation of Entropy and Information Distances
Venue: arXiv cs.DS 2005
Year: 2005

In many problems in data mining and machine learning, data items that need to be clustered or classified are not points in a high-dimensional space, but are distributions (points on a high dimensional simplex). For distributions, natural measures of distance are not the $\ell_p$ norms and variants, but information-theoretic measures like the Kullback-Leibler distance, the Hellinger distance, and others. Efficient estimation of these distances is a key component in algorithms for manipulating distributions. Thus, sublinear resource constraints, either in time (property testing) or space (streaming) are crucial. We start by resolving two open questions regarding property testing of distributions. Firstly, we show a tight bound for estimating bounded, symmetric f-divergences between distributions in a general property testing (sublinear time) framework (the so-called combined oracle model). This yields optimal algorithms for estimating such well known distances as the Jensen-Shannon divergence and the Hellinger distance. Secondly, we close a $(\log n)/H$ gap between upper and lower bounds for estimating entropy $H$ in this model. In a stream setting (sublinear space), we give the first algorithm for estimating the entropy of a distribution. Our algorithm runs in polylogarithmic space and yields an asymptotic constant factor approximation scheme. We also provide other results along the space/time/approximation tradeoff curve.
On Algorithms and Complexity for Sets with Cardinality Constraints
Venue: arXiv cs.PL 2005
Year: 2005

Typestate systems ensure many desirable properties of imperative programs, including initialization of object fields and correct use of stateful library interfaces. Abstract sets with cardinality constraints naturally generalize typestate properties: relationships between the typestates of objects can be expressed as subset and disjointness relations on sets, and elements of sets can be represented as sets of cardinality one. Motivated by these applications, this paper presents new algorithms and new complexity results for constraints on sets and their cardinalities. We study several classes of constraints and demonstrate a trade-off between their expressive power and their complexity. Our first result concerns a quantifier-free fragment of Boolean Algebra with Presburger Arithmetic. We give a nondeterministic polynomial-time algorithm for reducing the satisfiability of sets with symbolic cardinalities to constraints on constant cardinalities, and give a polynomial-space algorithm for the resulting problem. In a quest for more efficient fragments, we identify several subclasses of sets with cardinality constraints whose satisfiability is NP-hard. Finally, we identify a class of constraints that has polynomial-time satisfiability and entailment problems and can serve as a foundation for efficient program analysis.
A Fresh Look at the Reliability of Long-term Digital Storage
Venue: arXiv cs.DL 2005
Year: 2005

Many emerging Web services, such as email, photo sharing, and web site archives, need to preserve large amounts of quickly-accessible data indefinitely into the future. In this paper, we make the case that these applications' demands on large scale storage systems over long time horizons require us to re-evaluate traditional storage system designs. We examine threats to long-lived data from an end-to-end perspective, taking into account not just hardware and software faults but also faults due to humans and organizations. We present a simple model of long-term storage failures that helps us reason about the various strategies for addressing these threats in a cost-effective manner. Using this model we show that the most important strategies for increasing the reliability of long-term storage are detecting latent faults quickly, automating fault repair to make it faster and cheaper, and increasing the independence of data replicas.
Planning with Preferences using Logic Programming
Venue: arXiv cs.AI 2005
Year: 2005

We present a declarative language, PP, for the high-level specification of preferences between possible solutions (or trajectories) of a planning problem. This novel language allows users to elegantly express non-trivial, multi-dimensional preferences and priorities over such preferences. The semantics of PP allows the identification of most preferred trajectories for a given goal. We also provide an answer set programming implementation of planning problems with PP preferences.
Component Based Programming in Scientific Computing: The Viable Approach
Venue: arXiv cs.CE 2005
Year: 2005

Computational scientists are facing a new era where the old ways of developing and reusing code have to be left behind and a few daring steps are to be made towards new horizons. The present work analyzes the needs that drive this change, the factors that contribute to the inertia of the community and slow the transition, the status and perspective of present attempts, the principle, practical and technical problems that are to be addressed in the short and long run.
Precoloring co-Meyniel graphs
Venue: arXiv cs.DM 2005
Year: 2005

The pre-coloring extension problem consists, given a graph $G$ and a subset of nodes to which some colors are already assigned, in finding a coloring of $G$ with the minimum number of colors which respects the pre-coloring assignment. This can be reduced to the usual coloring problem on a certain contracted graph. We prove that pre-coloring extension is polynomial for complements of Meyniel graphs. We answer a question of Hujter and Tuza by showing that ``PrExt perfect'' graphs are exactly the co-Meyniel graphs, which also generalizes results of Hujter and Tuza and of Hertz. Moreover we show that, given a co-Meyniel graph, the corresponding contracted graph belongs to a restricted class of perfect graphs (``co-Artemis'' graphs, which are ``co-perfectly contractile'' graphs), whose perfectness is easier to establish than the strong perfect graph theorem. However, the polynomiality of our algorithm still depends on the ellipsoid method for coloring perfect graphs.
Non-Data-Aided Parameter Estimation in an Additive White Gaussian Noise Channel
Venue: arXiv cs.IT 2005
Year: 2005

Non-data-aided (NDA) parameter estimation is considered for binary-phase-shift-keying transmission in an additive white Gaussian noise channel. Cramer-Rao lower bounds (CRLBs) for signal amplitude, noise variance, channel reliability constant and bit-error rate are derived and it is shown how these parameters relate to the signal-to-noise ratio (SNR). An alternative derivation of the iterative maximum likelihood (ML) SNR estimator is presented together with a novel, low complexity NDA SNR estimator. The performance of the proposed estimator is compared to previously suggested estimators and the CRLB. The results show that the proposed estimator performs close to the iterative ML estimator at significantly lower computational complexity.
On the variational distance of independently repeated experiments
Venue: arXiv cs.IT 2005
Year: 2005

Let P and Q be two probability distributions which differ only for values with non-zero probability. We show that the variational distance between the n-fold product distributions P^n and Q^n cannot grow faster than the square root of n.
Comparing hierarchies of total functionals
Venue: arXiv cs.LO 2005
Year: 2005

In this paper we consider two hierarchies of hereditarily total and continuous functionals over the reals based on one extensional and one intensional representation of real numbers, and we discuss under which asumptions these hierarchies coincide. This coincidense problem is equivalent to a statement about the topology of the Kleene-Kreisel continuous functionals. As a tool of independent interest, we show that the Kleene-Kreisel functionals may be embedded into both these hierarchies.
Effect of door delay on aircraft evacuation time
Venue: arXiv cs.MA 2005
Year: 2005

The recent commercial launch of twin-deck Very Large Transport Aircraft (VLTA) such as the Airbus A380 has raised questions concerning the speed at which they may be evacuated. The abnormal height of emergency exits on the upper deck has led to speculation that emotional factors such as fear may lead to door delay, and thus play a significant role in increasing overall evacuation time. Full-scale evacuation tests are financially expensive and potentially hazardous, and systematic studies of the evacuation of VLTA are rare. Here we present a computationally cheap agent-based framework for the general simulation of aircraft evacuation, and apply it to the particular case of the Airbus A380. In particular, we investigate the effect of door delay, and conclude that even a moderate average delay can lead to evacuation times that exceed the maximum for safety certification. The model suggests practical ways to minimise evacuation time, as well as providing a general framework for the simulation of evacuation.
Learning Optimal Augmented Bayes Networks
Venue: arXiv cs.LG 2005
Year: 2005

Naive Bayes is a simple Bayesian classifier with strong independence assumptions among the attributes. This classifier, desipte its strong independence assumptions, often performs well in practice. It is believed that relaxing the independence assumptions of a naive Bayes classifier may improve the classification accuracy of the resulting structure. While finding an optimal unconstrained Bayesian Network (for most any reasonable scoring measure) is an NP-hard problem, it is possible to learn in polynomial time optimal networks obeying various structural restrictions. Several authors have examined the possibilities of adding augmenting arcs between attributes of a Naive Bayes classifier. Friedman, Geiger and Goldszmidt define the TAN structure in which the augmenting arcs form a tree on the attributes, and present a polynomial time algorithm that learns an optimal TAN with respect to MDL score. Keogh and Pazzani define Augmented Bayes Networks in which the augmenting arcs form a forest on the attributes (a collection of trees, hence a relaxation of the stuctural restriction of TAN), and present heuristic search methods for learning good, though not optimal, augmenting arc sets. The authors, however, evaluate the learned structure only in terms of observed misclassification error and not against a scoring metric, such as MDL. In this paper, we present a simple, polynomial time greedy algorithm for learning an optimal Augmented Bayes Network with respect to MDL score.
Face Recognition Based on Polar Frequency Features
Venue: arXiv cs.CV 2005
Year: 2005

A novel biologically motivated face recognition algorithm based on polar frequency is presented. Polar frequency descriptors are extracted from face images by Fourier-Bessel transform (FBT). Next, the Euclidean distance between all images is computed and each image is now represented by its dissimilarity to the other images. A Pseudo-Fisher Linear Discriminant was built on this dissimilarity space. The performance of Discrete Fourier transform (DFT) descriptors, and a combination of both feature types was also evaluated. The algorithms were tested on a 40- and 1196-subjects face database (ORL and FERET, respectively). With 5 images per subject in the training and test datasets, error rate on the ORL database was 3.8, 1.25 and 0.2% for the FBT, DFT, and the combined classifier, respectively, as compared to 2.6% achieved by the best previous algorithm. The most informative polar frequency features were concentrated at low-to-medium angular frequencies coupled to low radial frequencies. On the FERET database, where an affine normalization pre-processing was applied, the FBT algorithm outperformed only the PCA in a rank recognition test. However, it achieved performance comparable to state-of-the-art methods when evaluated by verification tests. These results indicate the high informative value of the polar frequency content of face images in relation to recognition and verification tasks, and that the Cartesian frequency content can complement information about the subjects' identity, but possibly only when the images are not pre-normalized. Possible implications for human face recognition are discussed.
Statistical Mechanical Approach to Lossy Data Compression:Theory and Practice
Venue: arXiv cs.IT 2005
Year: 2005

The encoder and decoder for lossy data compression of binary memoryless sources are developed on the basis of a specific-type nonmonotonic perceptron. Statistical mechanical analysis indicates that the potential ability of the perceptron-based code saturates the theoretically achievable limit in most cases although exactly performing the compression is computationally difficult. To resolve this difficulty, we provide a computationally tractable approximation algorithm using belief propagation (BP), which is a current standard algorithm of probabilistic inference. Introducing several approximations and heuristics, the BP-based algorithm exhibits performance that is close to the achievable limit in a practical time scale in optimal cases.
Using the Modified Allan Variance for Accurate Estimation of the Hurst Parameter of Long-Range Dependent Traffic
Venue: arXiv cs.NI 2005
Year: 2005

Internet traffic exhibits self-similarity and long-range dependence (LRD) on various time scales. A well studied issue is the estimation of statistical parameters characterizing traffic self-similarity and LRD, such as the Hurst parameter H. In this paper, we propose to adapt the Modified Allan Variance (MAVAR), a time-domain quantity originally conceived to discriminate fractional noise in frequency stability measurement, to estimate the Hurst parameter of LRD traffic traces and, more generally, to identify fractional noise components in network traffic. This novel method is validated by comparison to one of the best techniques for analyzing self-similar and LRD traffic: the logscale diagram based on wavelet analysis. Both methods are applied to pseudo-random LRD data series, generated with assigned values of H. The superior spectral sensitivity of MAVAR achieves outstanding accuracy in estimating H, even better than the logscale method. The behaviour of MAVAR with most common deterministic signals that yield nonstationarity in data under analysis is also studied. Finally, both techniques are applied to a real IP traffic trace, providing a sound example of the usefulness of MAVAR also in traffic characterization, to complement other established techniques as the logscale method.
Accurate and robust image superresolution by neural processing of local image representations
Venue: arXiv cs.CV 2005
Year: 2005

Image superresolution involves the processing of an image sequence to generate a still image with higher resolution. Classical approaches, such as bayesian MAP methods, require iterative minimization procedures, with high computational costs. Recently, the authors proposed a method to tackle this problem, based on the use of a hybrid MLP-PNN architecture. In this paper, we present a novel superresolution method, based on an evolution of this concept, to incorporate the use of local image models. A neural processing stage receives as input the value of model coefficients on local windows. The data dimensionality is firstly reduced by application of PCA. An MLP, trained on synthetic sequences with various amounts of noise, estimates the high-resolution image data. The effect of varying the dimension of the network input space is examined, showing a complex, structured behavior. Quantitative results are presented showing the accuracy and robustness of the proposed method.
Safe Data Sharing and Data Dissemination on Smart Devices
Venue: arXiv cs.CR 2005
Year: 2005

The erosion of trust put in traditional database servers, the growing interest for different forms of data dissemination and the concern for protecting children from suspicious Internet content are different factors that lead to move the access control from servers to clients. Several encryption schemes can be used to serve this purpose but all suffer from a static way of sharing data. In a precedent paper, we devised smarter client-based access control managers exploiting hardware security elements on client devices. The goal pursued is being able to evaluate dynamic and personalized access control rules on a ciphered XML input document, with the benefit of dissociating access rights from encryption. In this demonstration, we validate our solution using a real smart card platform and explain how we deal with the constraints usually met on hardware security elements (small memory and low throughput). Finally, we illustrate the generality of the approach and the easiness of its deployment through two different applications: a collaborative application and a parental control application on video streams.