OpenRaiser/Intern-Atlas huggingface dataset:
Computing the Rank and a Small Nullspace Basis of a Polynomial Matrix
Venue: arXiv cs.SC 2005
Year: 2005

We reduce the problem of computing the rank and a nullspace basis of a univariate polynomial matrix to polynomial matrix multiplication. For an input n x n matrix of degree d over a field K we give a rank and nullspace algorithm using about the same number of operations as for multiplying two matrices of dimension n and degree d. If the latter multiplication is done in MM(n,d)=softO(n^omega d) operations, with omega the exponent of matrix multiplication over K, then the algorithm uses softO(MM(n,d)) operations in K. The softO notation indicates some missing logarithmic factors. The method is randomized with Las Vegas certification. We achieve our results in part through a combination of matrix Hensel high-order lifting and matrix minimal fraction reconstruction, and through the computation of minimal or small degree vectors in the nullspace seen as a K[x]-module
A Simple Proof of the F{á}ry-Wagner Theorem
Venue: arXiv cs.CG 2005
Year: 2005

We give a simple proof of the following fundamental result independently due to Fary (1948) and Wagner (1936): Every plane graph has a drawing in which every edge is straight.
Fading-Resilient Super-Orthogonal Space-Time Signal Sets: Can Good Constellations Survive in Fading?
Venue: arXiv cs.IT 2005
Year: 2005

In this correspondence, first-tier indirect (direct) discernible constellation expansions are defined for generalized orthogonal designs. The expanded signal constellation, leading to so-called super-orthogonal codes, allows the achievement of coding gains in addition to diversity gains enabled by orthogonal designs. Conditions that allow the shape of an expanded multidimensional constellation to be preserved at the channel output, on an instantaneous basis, are derived. It is further shown that, for such constellations, the channel alters neither the relative distances nor the angles between signal points in the expanded signal constellation.
Upgrading Pulse Detection with Time Shift Properties Using Wavelets and Support Vector Machines
Venue: arXiv cs.IR 2005
Year: 2005

Current approaches in pulse detection use domain transformations so as to concentrate frequency related information that can be distinguishable from noise. In real cases we do not know when the pulse will begin, so we need a time search process in which time windows are scheduled and analysed. Each window can contain the pulsed signal (either complete or incomplete) and / or noise. In this paper a simple search process will be introduced, allowing the algorithm to process more information, upgrading the capabilities in terms of probability of detection (Pd) and probability of false alarm (Pfa).
Improved Bounds on the Parity-Check Density and Achievable Rates of Binary Linear Block Codes with Applications to LDPC Codes
Venue: arXiv cs.IT 2005
Year: 2005

We derive bounds on the asymptotic density of parity-check matrices and the achievable rates of binary linear block codes transmitted over memoryless binary-input output-symmetric (MBIOS) channels. The lower bounds on the density of arbitrary parity-check matrices are expressed in terms of the gap between the rate of these codes for which reliable communication is achievable and the channel capacity, and the bounds are valid for every sequence of binary linear block codes. These bounds address the question, previously considered by Sason and Urbanke, of how sparse can parity-check matrices of binary linear block codes be as a function of the gap to capacity. Similarly to a previously reported bound by Sason and Urbanke, the new lower bounds on the parity-check density scale like the log of the inverse of the gap to capacity, but their tightness is improved (except for a binary symmetric/erasure channel, where they coincide with the previous bound). The new upper bounds on the achievable rates of binary linear block codes tighten previously reported bounds by Burshtein et al., and therefore enable to obtain tighter upper bounds on the thresholds of sequences of binary linear block codes under ML decoding. The bounds are applied to low-density parity-check (LDPC) codes, and the improvement in their tightness is exemplified numerically. The upper bounds on the achievable rates enable to assess the inherent loss in performance of various iterative decoding algorithms as compared to optimal ML decoding. The lower bounds on the asymptotic parity-check density are helpful in assessing the inherent tradeoff between the asymptotic performance of LDPC codes and their decoding complexity (per iteration) under message-passing decoding.
A Unified Subspace Outlier Ensemble Framework for Outlier Detection in High Dimensional Spaces
Venue: arXiv cs.DB 2005
Year: 2005

The task of outlier detection is to find small groups of data objects that are exceptional when compared with rest large amount of data. Detection of such outliers is important for many applications such as fraud detection and customer migration. Most such applications are high dimensional domains in which the data may contain hundreds of dimensions. However, the outlier detection problem itself is not well defined and none of the existing definitions are widely accepted, especially in high dimensional space. In this paper, our first contribution is to propose a unified framework for outlier detection in high dimensional spaces from an ensemble-learning viewpoint. In our new framework, the outlying-ness of each data object is measured by fusing outlier factors in different subspaces using a combination function. Accordingly, we show that all existing researches on outlier detection can be regarded as special cases in the unified framework with respect to the set of subspaces considered and the type of combination function used. In addition, to demonstrate the usefulness of the ensemble-learning based outlier detection framework, we developed a very simple and fast algorithm, namely SOE1 (Subspace Outlier Ensemble using 1-dimensional Subspaces) in which only subspaces with one dimension is used for mining outliers from large categorical datasets. The SOE1 algorithm needs only two scans over the dataset and hence is very appealing in real data mining applications. Experimental results on real datasets and large synthetic datasets show that: (1) SOE1 has comparable performance with respect to those state-of-art outlier detection algorithms on identifying true outliers and (2) SOE1 can be an order of magnitude faster than one of the fastest outlier detection algorithms known so far.
Application of Kolmogorov complexity and universal codes to identity testing and nonparametric testing of serial independence for time series
Venue: arXiv cs.CC 2005
Year: 2005

We show that Kolmogorov complexity and such its estimators as universal codes (or data compression methods) can be applied for hypotheses testing in a framework of classical mathematical statistics. The methods for identity testing and nonparametric testing of serial independence for time series are suggested.
An ontological approach to the construction of problem-solving models
Venue: arXiv cs.AI 2005
Year: 2005

Our ongoing work aims at defining an ontology-centered approach for building expertise models for the CommonKADS methodology. This approach (which we have named "OntoKADS") is founded on a core problem-solving ontology which distinguishes between two conceptualization levels: at an object level, a set of concepts enable us to define classes of problem-solving situations, and at a meta level, a set of meta-concepts represent modeling primitives. In this article, our presentation of OntoKADS will focus on the core ontology and, in particular, on roles - the primitive situated at the interface between domain knowledge and reasoning, and whose ontological status is still much debated. We first propose a coherent, global, ontological framework which enables us to account for this primitive. We then show how this novel characterization of the primitive allows definition of new rules for the construction of expertise models.
SafeMPI - Extending MPI for Byzantine Error Detection on Parallel Clusters
Venue: arXiv cs.DC 2005
Year: 2005

Modern high-performance computing relies heavily on the use of commodity processors arranged together in clusters. These clusters consist of individual nodes (typically off-the-shelf single or dual processor machines) connected together with a high speed interconnect. Using cluster computation has many benefits, but also carries the liability of being failure prone due to the sheer number of components involved. Many effective solutions have been proposed to aid failure recovery in clusters, their one significant downside being the failure models they support. Most of the work in the area has focused on detecting and correcting fail-stop errors. We propose a system that will also detect more general error models, such as Byzantine errors, thus allowing existing failure recovery methods to handle them correctly.
Programming Finite-Domain Constraint Propagators in Action Rules
Venue: arXiv cs.PL 2005
Year: 2005

In this paper, we propose a new language, called AR ({\it Action Rules}), and describe how various propagators for finite-domain constraints can be implemented in it. An action rule specifies a pattern for agents, an action that the agents can carry out, and an event pattern for events that can activate the agents. AR combines the goal-oriented execution model of logic programming with the event-driven execution model. This hybrid execution model facilitates programming constraint propagators. A propagator for a constraint is an agent that maintains the consistency of the constraint and is activated by the updates of the domain variables in the constraint. AR has a much stronger descriptive power than {\it indexicals}, the language widely used in the current finite-domain constraint systems, and is flexible for implementing not only interval-consistency but also arc-consistency algorithms. As examples, we present a weak arc-consistency propagator for the {\tt all\_distinct} constraint and a hybrid algorithm for n-ary linear equality constraints. B-Prolog has been extended to accommodate action rules. Benchmarking shows that B-Prolog as a CLP(FD) system significantly outperforms other CLP(FD) systems.
The Hyper-Cortex of Human Collective-Intelligence Systems
Venue: arXiv cs.CY 2005
Year: 2005

Individual-intelligence research, from a neurological perspective, discusses the hierarchical layers of the cortex as a structure that performs conceptual abstraction and specification. This theory has been used to explain how motor-cortex regions responsible for different behavioral modalities such as writing and speaking can be utilized to express the same general concept represented higher in the cortical hierarchy. For example, the concept of a dog, represented across a region of high-level cortical-neurons, can either be written or spoken about depending on the individual's context. The higher-layer cortical areas project down the hierarchy, sending abstract information to specific regions of the motor-cortex for contextual implementation. In this paper, this idea is expanded to incorporate collective-intelligence within a hyper-cortical construct. This hyper-cortex is a multi-layered network used to represent abstract collective concepts. These ideas play an important role in understanding how collective-intelligence systems can be engineered to handle problem abstraction and solution specification. Finally, a collection of common problems in the scientific community are solved using an artificial hyper-cortex generated from digital-library metadata.
A Constrained Object Model for Configuration Based Workflow Composition
Venue: arXiv cs.AI 2005
Year: 2005

Automatic or assisted workflow composition is a field of intense research for applications to the world wide web or to business process modeling. Workflow composition is traditionally addressed in various ways, generally via theorem proving techniques. Recent research observed that building a composite workflow bears strong relationships with finite model search, and that some workflow languages can be defined as constrained object metamodels . This lead to consider the viability of applying configuration techniques to this problem, which was proven feasible. Constrained based configuration expects a constrained object model as input. The purpose of this document is to formally specify the constrained object model involved in ongoing experiments and research using the Z specification language.
A Game Theoretic Economics Framework to understanding Information Security Oursourcing Market
Venue: arXiv cs.GT 2005
Year: 2005

On information security outsourcing market, an important reason that firms do not want to let outside firms(usually called MSSPs-Managed Security Service Providers) to take care of their security need is that they worry about service quality MSSPs provide because they cannot monitor effort of the MSSPs. Since MSSPs action is unobservable to buyers, MSSPs can lower cost by working less hard than required in the contract and get higher profit. In the asymmetric information literature, this possible secret shirking behavior is termed as moral hazard problem. This paper considers a game theoretic economic framework to show that under information asymmetry, an optimal contract can be designed so that MSSPs will stick to their promised effort level. We also show that the optimal contract should be performance-based, i.e., payment to MSSP should base on performance of MSSP's security service period by period. For comparison, we also showed that if the moral hazard problem does not exist, the optimal contract does not depend on MSSP's performance. A contract that specifies constant payment to MSSP will be optimal. Besides these, we show that for no matter under perfect information scenario or imperfect information scenario, the higher the transaction cost is, the lower payment to MSSPs will be.
Analyse et expansion des textes en question-réponse
Venue: arXiv cs.IR 2005
Year: 2005

This paper presents an original methodology to consider question answering. We noticed that query expansion is often incorrect because of a bad understanding of the question. But the automatic good understanding of an utterance is linked to the context length, and the question are often short. This methodology proposes to analyse the documents and to construct an informative structure from the results of the analysis and from a semantic text expansion. The linguistic analysis identifies words (tokenization and morphological analysis), links between words (syntactic analysis) and word sense (semantic disambiguation). The text expansion adds to each word the synonyms matching its sense and replaces the words in the utterances by derivatives, modifying the syntactic schema if necessary. In this way, whatever enrichment may be, the text keeps the same meaning, but each piece of information matches many realisations. The questioning method consists in constructing a local informative structure without enrichment, and matches it with the documentary structure. If a sentence in the informative structure matches the question structure, this sentence is the answer to the question.
Comparison of two different implementations of a finite-difference-method for first-order pde in mathematica and matlab
Venue: arXiv cs.CE 2005
Year: 2005

In this article two implementations of a symmetric finite difference algorithm for a first-order partial differential equation are discussed. The considered partial differential equation discribes the time evolution of the crack length distribution of microcracks in brittle materia.
Efficiency Loss in a Network Resource Allocation Game: The Case of Elastic Supply
Venue: arXiv cs.GT 2005
Year: 2005

We consider a resource allocation problem where individual users wish to send data across a network to maximize their utility, and a cost is incurred at each link that depends on the total rate sent through the link. It is known that as long as users do not anticipate the effect of their actions on prices, a simple proportional pricing mechanism can maximize the sum of users' utilities minus the cost (called aggregate surplus). Continuing previous efforts to quantify the effects of selfish behavior in network pricing mechanisms, we consider the possibility that users anticipate the effect of their actions on link prices. Under the assumption that the links' marginal cost functions are convex, we establish existence of a Nash equilibrium. We show that the aggregate surplus at a Nash equilibrium is no worse than a factor of 4*sqrt{2} - 5 times the optimal aggregate surplus; thus, the efficiency loss when users are selfish is no more than approximately 34%.
A generating function method for the average-case analysis of DPLL
Venue: arXiv cs.CC 2005
Year: 2005

A method to calculate the average size of Davis-Putnam-Loveland-Logemann (DPLL) search trees for random computational problems is introduced, and applied to the satisfiability of random CNF formulas (SAT) and the coloring of random graph (COL) problems. We establish recursion relations for the generating functions of the average numbers of (variable or color) assignments at a given height in the search tree, which allow us to derive the asymptotics of the expected DPLL tree size, 2^{N w + o(N)}, where N is the instance size. w is calculated as a function of the input distribution parameters (ratio of clauses per variable for SAT, average vertex degree for COL), and the branching heuristics.
Alternative security architecture for IP Telephony based on digital watermarking
Venue: arXiv cs.CR 2005
Year: 2005

Problems with securing IP Telephony systems, insufficient standardization and lack of security mechanisms emerged the need for new approaches and solutions. In this paper a new, alternative security architecture for voice-systems is presented. It is based on digital watermarking: a new, flexible and powerful technology that is increasingly gaining more and more attention. Besides known applications e.g. to solve copyright protection problems, we propose to use digital watermarking to secure not only transmitted audio but also signaling protocol that IP Telephony is based on.
DIMES: Let the Internet Measure Itself
Venue: arXiv cs.NI 2005
Year: 2005

Today's Internet maps, which are all collected from a small number of vantage points, are falling short of being accurate. We suggest here a paradigm shift for this task. DIMES is a distributed measurement infrastructure for the Internet that is based on the deployment of thousands of light weight measurement agents around the globe. We describe the rationale behind DIMES deployment, discuss its design trade-offs and algorithmic challenges, and analyze the structure of the Internet as it seen with DIMES.
On $m$-dimensional toric codes
Venue: arXiv cs.IT 2005
Year: 2005

Toric codes are a class of $m$-dimensional cyclic codes introduced recently by J. Hansen. They may be defined as evaluation codes obtained from monomials corresponding to integer lattice points in an integral convex polytope $P \subseteq \R^m$. As such, they are in a sense a natural extension of Reed-Solomon codes. Several authors have used intersection theory on toric surfaces to derive bounds on the minimum distance of some toric codes with $m = 2$. In this paper, we will provide a more elementary approach that applies equally well to many toric codes for all $m \ge 2$. Our methods are based on a sort of multivariate generalization of Vandermonde determinants that has also been used in the study of multivariate polynomial interpolation. We use these Vandermonde determinants to determine the minimum distance of toric codes from rectangular polytopes and simplices. We also prove a general result showing that if there is a unimodular integer affine transformation taking one polytope $P_1$ to a second polytope $P_2$, then the corresponding toric codes are monomially equivalent (hence have the same parameters). We use this to begin a classification of two-dimensional toric codes with small dimension.
Asymptotically Optimal Tree-based Group Key Management Schemes
Venue: arXiv cs.IT 2005
Year: 2005

In key management schemes that realize secure multicast communications encrypted by group keys on a public network, tree structures are often used to update the group keys efficiently. Selcuk and Sidhu have proposed an efficient scheme which updates dynamically the tree structures based on the withdrawal probabilities of members. In this paper, it is shown that Selcuk-Sidhu scheme is asymptotically optimal for the cost of withdrawal. Furthermore, a new key management scheme, which takes account of key update costs of joining in addition to withdrawal, is proposed. It is proved that the proposed scheme is also asymptotically optimal, and it is shown by simulation that it can attain good performance for nonasymptotic cases.
A Study for the Feature Core of Dynamic Reduct
Venue: arXiv cs.AI 2005
Year: 2005

To the reduct problems of decision system, the paper proposes the notion of dynamic core according to the dynamic reduct model. It describes various formal definitions of dynamic core, and discusses some properties about dynamic core. All of these show that dynamic core possesses the essential characters of the feature core.
First-order queries on structures of bounded degree are computable with constant delay
Venue: arXiv cs.LO 2005
Year: 2005

A bounded degree structure is either a relational structure all of whose relations are of bounded degree or a functional structure involving bijective functions only. In this paper, we revisit the complexity of the evaluation problem of not necessarily Boolean first-order queries over structures of bounded degree. Query evaluation is considered here as a dynamical process. We prove that any query on bounded degree structures is $\constantdelaylin$, i.e., can be computed by an algorithm that has two separate parts: it has a precomputation step of linear time in the size of the structure and then, it outputs all tuples one by one with a constant (i.e. depending on the size of the formula only) delay between each. Seen as a global process, this implies that queries on bounded structures can be evaluated in total time $O(f(|ϕ|).(|\calS|+|ϕ(\calS)|))$ and space $O(f(|ϕ|).|\calS|)$ where $\calS$ is the structure, $ϕ$ is the formula, $ϕ(\calS)$ is the result of the query and $f$ is some function. Among other things, our results generalize a result of \cite{Seese-96} on the data complexity of the model-checking problem for bounded degree structures. Besides, the originality of our approach compared to that \cite{Seese-96} and comparable results is that it does not rely on the Hanf's model-theoretic technic (see \cite{Hanf-65}) and is completely effective.
Two-dimensional cellular automata and the analysis of correlated time series
Venue: arXiv cs.AI 2005
Year: 2005

Correlated time series are time series that, by virtue of the underlying process to which they refer, are expected to influence each other strongly. We introduce a novel approach to handle such time series, one that models their interaction as a two-dimensional cellular automaton and therefore allows them to be treated as a single entity. We apply our approach to the problems of filling gaps and predicting values in rainfall time series. Computational results show that the new approach compares favorably to Kalman smoothing and filtering.