OpenRaiser/Intern-Atlas huggingface dataset:
On the capacity of mobile ad hoc networks with delay constraints
Venue: arXiv cs.IT 2005
Year: 2005

Previous work on ad hoc network capacity has focused primarily on source-destination throughput requirements for different models and transmission scenarios, with an emphasis on delay tolerant applications. In such problems, network capacity enhancement is achieved as a tradeoff with transmission delay. In this paper, the capacity of ad hoc networks supporting delay sensitive traffic is studied. First, a general framework is proposed for characterizing the interactions between the physical and the network layer in an ad hoc network. Then, CDMA ad hoc networks, in which advanced signal processing techniques such as multiuser detection are relied upon to enhance the user capacity, are analyzed. The network capacity is characterized using a combination of geometric arguments and large scale analysis, for several network scenarios employing matched filters, decorrelators and minimum-mean-square-error receivers. Insight into the network performance for finite systems is also provided by means of simulations. Both analysis and simulations show a significant network capacity gain for ad hoc networks employing multiuser detectors, compared with those using matched filter receivers, as well as very good performance even under tight delay and transmission power requirements.
Delta-confluent Drawings
Venue: arXiv cs.CG 2005
Year: 2005

We generalize the tree-confluent graphs to a broader class of graphs called Delta-confluent graphs. This class of graphs and distance-hereditary graphs, a well-known class of graphs, coincide. Some results about the visualization of Delta-confluent graphs are also given.
COMODI: On the Graphical User Interface
Venue: arXiv cs.HC 2005
Year: 2005

We propose a series of features for the graphical user interface (GUI) of the COmputational MOdule Integrator (COMODI) \cite{Synasc05a}\cite{COMODI}. In view of the special requirements that a COMODI type of framework for scientific computing imposes and inspiring from existing solutions that provide advanced graphical visual programming environments, we identify those elements and associated behaviors that will have to find their way into the first release of COMODI.
The "...system of constraints"
Venue: arXiv cs.IT 2005
Year: 2005

This paper proposes that the mathematical relationship between an entropy distribution and its limit offers some new insight into system performance. This relationship is used to quantify variation among the entities of a system, where variation is defined as tolerance, option, specification or implementation variation among the entities of a system. Variation has a significnt and increasing impact on communications system performance. This paper introduces means to identify, quantify and reduce such performance variations.
Feynman graphs and related Hopf algebras
Venue: arXiv cs.SC 2005
Year: 2005

In a recent series of communications we have shown that the reordering problem of bosons leads to certain combinatorial structures. These structures may be associated with a certain graphical description. In this paper, we show that there is a Hopf Algebra structure associated with this problem which is, in a certain sense, unique.
Why We Can Not Surpass Capacity: The Matching Condition
Venue: arXiv cs.IT 2005
Year: 2005

We show that iterative coding systems can not surpass capacity using only quantities which naturally appear in density evolution. Although the result in itself is trivial, the method which we apply shows that in order to achieve capacity the various components in an iterative coding system have to be perfectly matched. This generalizes the perfect matching condition which was previously known for the case of transmission over the binary erasure channel to the general class of binary-input memoryless output-symmetric channels. Potential applications of this perfect matching condition are the construction of capacity-achieving degree distributions and the determination of the number required iterations as a function of the multiplicative gap to capacity.
Bounds on the Pseudo-Weight of Minimal Pseudo-Codewords of Projective Geometry Codes
Venue: arXiv cs.IT 2005
Year: 2005

In this paper we focus our attention on a family of finite geometry codes, called type-I projective geometry low-density parity-check (PG-LDPC) codes, that are constructed based on the projective planes PG{2,q). In particular, we study their minimal codewords and pseudo-codewords, as it is known that these vectors characterize completely the code performance under maximum-likelihood decoding and linear programming decoding, respectively. The main results of this paper consist of upper and lower bounds on the pseudo-weight of the minimal pseudo-codewords of type-I PG-LDPC codes.
Integration of the DOLCE top-level ontology into the OntoSpec methodology
Venue: arXiv cs.AI 2005
Year: 2005

This report describes a new version of the OntoSpec methodology for ontology building. Defined by the LaRIA Knowledge Engineering Team (University of Picardie Jules Verne, Amiens, France), OntoSpec aims at helping builders to model ontological knowledge (upstream of formal representation). The methodology relies on a set of rigorously-defined modelling primitives and principles. Its application leads to the elaboration of a semi-informal ontology, which is independent of knowledge representation languages. We recently enriched the OntoSpec methodology by endowing it with a new resource, the DOLCE top-level ontology defined at the LOA (IST-CNR, Trento, Italy). The goal of this integration is to provide modellers with additional help in structuring application ontologies, while maintaining independence vis-à-vis formal representation languages. In this report, we first provide an overview of the OntoSpec methodology's general principles and then describe the DOLCE re-engineering process. A complete version of DOLCE-OS (i.e. a specification of DOLCE in the semi-informal OntoSpec language) is presented in an appendix.
The Nature of Novelty Detection
Venue: arXiv cs.IR 2005
Year: 2005

Sentence level novelty detection aims at reducing redundant sentences from a sentence list. In the task, sentences appearing later in the list with no new meanings are eliminated. Aiming at a better accuracy for detecting redundancy, this paper reveals the nature of the novelty detection task currently overlooked by the Novelty community $-$ Novelty as a combination of the partial overlap (PO, two sentences sharing common facts) and complete overlap (CO, the first sentence covers all the facts of the second sentence) relations. By formalizing novelty detection as a combination of the two relations between sentences, new viewpoints toward techniques dealing with Novelty are proposed. Among the methods discussed, the similarity, overlap, pool and language modeling approaches are commonly used. Furthermore, a novel approach, selected pool method is provided, which is immediate following the nature of the task. Experimental results obtained on all the three currently available novelty datasets showed that selected pool is significantly better or no worse than the current methods. Knowledge about the nature of the task also affects the evaluation methodologies. We propose new evaluation measures for Novelty according to the nature of the task, as well as possible directions for future study.
First-Order Modeling and Stability Analysis of Illusory Contours
Venue: arXiv cs.CV 2005
Year: 2005

In visual cognition, illusions help elucidate certain intriguing latent perceptual functions of the human vision system, and their proper mathematical modeling and computational simulation are therefore deeply beneficial to both biological and computer vision. Inspired by existent prior works, the current paper proposes a first-order energy-based model for analyzing and simulating illusory contours. The lower complexity of the proposed model facilitates rigorous mathematical analysis on the detailed geometric structures of illusory contours. After being asymptotically approximated by classical active contours, the proposed model is then robustly computed using the celebrated level-set method of Osher and Sethian (J. Comput. Phys., 79:12-49, 1988) with a natural supervising scheme. Potential cognitive implications of the mathematical results are addressed, and generic computational examples are demonstrated and discussed.
Ultra Wideband Impulse Radio Systems with Multiple Pulse Types
Venue: arXiv cs.IT 2005
Year: 2005

In an ultra wideband (UWB) impulse radio (IR) system, a number of pulses, each transmitted in an interval called a "frame", is employed to represent one information symbol. Conventionally, a single type of UWB pulse is used in all frames of all users. In this paper, IR systems with multiple types of UWB pulses are considered, where different types of pulses can be used in different frames by different users. Both stored-reference (SR) and transmitted-reference (TR) systems are considered. First, the spectral properties of a multi-pulse IR system with polarity randomization is investigated. It is shown that the average power spectral density is the average of the spectral contents of different pulse shapes. Then, approximate closed-form expressions for the bit error probability of a multi-pulse SR-IR system are derived for RAKE receivers in asynchronous multiuser environments. The effects of both inter-frame interference (IFI) and multiple-access interference (MAI) are analyzed. The theoretical and simulation results indicate that SR-IR systems that are more robust against IFI and MAI than a "conventional" SR-IR system can be designed with multiple types of ultra-wideband pulses. Finally, extensions to multi-pulse TR-IR systems are briefly described.
Practical Datatype Specializations with Phantom Types and Recursion Schemes
Venue: arXiv cs.PL 2005
Year: 2005

Datatype specialization is a form of subtyping that captures program invariants on data structures that are expressed using the convenient and intuitive datatype notation. Of particular interest are structural invariants such as well-formedness. We investigate the use of phantom types for describing datatype specializations. We show that it is possible to express statically-checked specializations within the type system of Standard ML. We also show that this can be done in a way that does not lose useful programming facilities such as pattern matching in case expressions.
Architectural Considerations for a Self-Configuring Routing Scheme for Spontaneous Networks
Venue: arXiv cs.NI 2005
Year: 2005

Decoupling the permanent identifier of a node from the node's topology-dependent address is a promising approach toward completely scalable self-organizing networks. A group of proposals that have adopted such an approach use the same structure to: address nodes, perform routing, and implement location service. In this way, the consistency of the routing protocol relies on the coherent sharing of the addressing space among all nodes in the network. Such proposals use a logical tree-like structure where routes in this space correspond to routes in the physical level. The advantage of tree-like spaces is that it allows for simple address assignment and management. Nevertheless, it has low route selection flexibility, which results in low routing performance and poor resilience to failures. In this paper, we propose to increase the number of paths using incomplete hypercubes. The design of more complex structures, like multi-dimensional Cartesian spaces, improves the resilience and routing performance due to the flexibility in route selection. We present a framework for using hypercubes to implement indirect routing. This framework allows to give a solution adapted to the dynamics of the network, providing a proactive and reactive routing protocols, our major contributions. We show that, contrary to traditional approaches, our proposal supports more dynamic networks and is more robust to node failures.
Short Quantum Games
Venue: arXiv cs.CC 2005
Year: 2005

In this thesis we introduce quantum refereed games, which are quantum interactive proof systems with two competing provers. We focus on a restriction of this model that we call "short quantum games" and we prove an upper bound and a lower bound on the expressive power of these games. For the lower bound, we prove that every language having an ordinary quantum interactive proof system also has a short quantum game. An important part of this proof is the establishment of a quantum measurement that reliably distinguishes between quantum states chosen from disjoint convex sets. For the upper bound, we show that certain types of quantum refereed games, including short quantum games, are decidable in deterministic exponential time by supplying a separation oracle for use with the ellipsoid method for convex feasibility.
Heat kernel expansion for a family of stochastic volatility models : delta-geometry
Venue: arXiv cs.CE 2005
Year: 2005

In this paper, we study a family of stochastic volatility processes; this family features a mean reversion term for the volatility and a double CEV-like exponent that generalizes SABR and Heston's models. We derive approximated closed form formulas for the digital prices, the local and implied volatilities. Our formulas are efficient for small maturities. Our method is based on differential geometry, especially small time diffusions on riemanian spaces. This geometrical point of view can be extended to other processes, and is very accurate to produce variate smiles for small maturities and small moneyness.
Generalized Hermitian Codes over GF(2^r)
Venue: arXiv cs.DM 2005
Year: 2005

In this paper we studied generalization of Hermitian function field proposed by A.Garcia and H.Stichtenoth. We calculated a Weierstrass semigroup of the point at infinity for the case q=2, r>=3. It turned out that unlike Hermitian case, we have already three generators for the semigroup. We then applied this result to codes, constructed on generalized Hermitian function fields. Further, we applied results of C.Kirfel and R.Pellikaan to estimating a Feng-Rao designed distance for GH-codes, which improved on Goppa designed distance. Next, we studied the question of codes dual to GH-codes. We identified that the duals are also GH-codes and gave an explicit formula. We concluded with some computational results. In particular, a new record-giving [32,16,>=12]-code over GF(8) was presented.
A Model Based Approach to Reachability Routing
Venue: arXiv cs.NI 2005
Year: 2005

Current directions in network routing research have not kept pace with the latest developments in network architectures, such as peer-to-peer networks, sensor networks, ad-hoc wireless networks, and overlay networks. A common characteristic among all of these new technologies is the presence of highly dynamic network topologies. Currently deployed single-path routing protocols cannot adequately cope with this dynamism, and existing multi-path algorithms make trade-offs which lead to less than optimal performance on these networks. This drives the need for routing protocols designed with the unique characteristics of these networks in mind. In this paper we propose the notion of reachability routing as a solution to the challenges posed by routing on such dynamic networks. In particular, our formulation of reachability routing provides cost-sensitive multi-path forwarding along with loop avoidance within the confines of the Internet Protocol (IP) architecture. This is achieved through the application of reinforcement learning within a probabilistic routing framework. Following an explanation of our design decisions and a description of the algorithm, we provide an evaluation of the performance of the algorithm on a variety of network topologies. The results show consistently superior performance compared to other reinforcement learning based routing algorithms.
Quantized Indexing: Beyond Arithmetic Coding
Venue: arXiv cs.IT 2005
Year: 2005

Quantized Indexing is a fast and space-efficient form of enumerative (combinatorial) coding, the strongest among asymptotically optimal universal entropy coding algorithms. The present advance in enumerative coding is similar to that made by arithmetic coding with respect to its unlimited precision predecessor, Elias coding. The arithmetic precision, execution time, table sizes and coding delay are all reduced by a factor O(n) at a redundancy below 2*log(e)/2^g bits/symbol (for n input symbols and g-bit QI precision). Due to its tighter enumeration, QI output redundancy is below that of arithmetic coding (which can be derived as a lower accuracy approximation of QI). The relative compression gain vanishes in large n and in high entropy limits and increases for shorter outputs and for less predictable data. QI is significantly faster than the fastest arithmetic coders, from factor 6 in high entropy limit to over 100 in low entropy limit (`typically' 10-20 times faster). These speedups are result of using only 3 adds, 1 shift and 2 array lookups (all in 32 bit precision) per less probable symbol and no coding operations for the most probable symbol . Further, the exact enumeration algorithm is sharpened and its lattice walks formulation is generalized. A new numeric type with a broader applicability, sliding window integer, is introduced.
Performance Analysis of MIMO-MRC in Double-Correlated Rayleigh Environments
Venue: arXiv cs.IT 2005
Year: 2005

We consider multiple-input multiple-output (MIMO) transmit beamforming systems with maximum ratio combining (MRC) receivers. The operating environment is Rayleigh-fading with both transmit and receive spatial correlation. We present exact expressions for the probability density function (p.d.f.) of the output signal-to-noise ratio (SNR), as well as the system outage probability. The results are based on explicit closed-form expressions which we derive for the p.d.f. and c.d.f. of the maximum eigenvalue of double-correlated complex Wishart matrices. For systems with two antennas at either the transmitter or the receiver, we also derive exact closed-form expressions for the symbol error rate (SER). The new expressions are used to prove that MIMO-MRC achieves the maximum available spatial diversity order, and to demonstrate the effect of spatial correlation. The analysis is validated through comparison with Monte-Carlo simulations.
A polynomial-time heuristic for Circuit-SAT
Venue: arXiv cs.CC 2005
Year: 2005

In this paper is presented an heuristic that, in polynomial time and space in the input dimension, determines if a circuit describes a tautology or a contradiction. If the circuit is neither a tautology nor a contradiction, then the heuristic finds an assignment to the circuit inputs such that the circuit is satisfied.
Identifying Interaction Sites in "Recalcitrant" Proteins: Predicted Protein and Rna Binding Sites in Rev Proteins of Hiv-1 and Eiav Agree with Experimental Data
Venue: arXiv cs.LG 2005
Year: 2005

Protein-protein and protein nucleic acid interactions are vitally important for a wide range of biological processes, including regulation of gene expression, protein synthesis, and replication and assembly of many viruses. We have developed machine learning approaches for predicting which amino acids of a protein participate in its interactions with other proteins and/or nucleic acids, using only the protein sequence as input. In this paper, we describe an application of classifiers trained on datasets of well-characterized protein-protein and protein-RNA complexes for which experimental structures are available. We apply these classifiers to the problem of predicting protein and RNA binding sites in the sequence of a clinically important protein for which the structure is not known: the regulatory protein Rev, essential for the replication of HIV-1 and other lentiviruses. We compare our predictions with published biochemical, genetic and partial structural information for HIV-1 and EIAV Rev and with our own published experimental mapping of RNA binding sites in EIAV Rev. The predicted and experimentally determined binding sites are in very good agreement. The ability to predict reliably the residues of a protein that directly contribute to specific binding events - without the requirement for structural information regarding either the protein or complexes in which it participates - can potentially generate new disease intervention strategies.
Uniqueness of Nonextensive entropy under Renyi's Recipe
Venue: arXiv cs.IT 2005
Year: 2005

By replacing linear averaging in Shannon entropy with Kolmogorov-Nagumo average (KN-averages) or quasilinear mean and further imposing the additivity constraint, Rényi proposed the first formal generalization of Shannon entropy. Using this recipe of Rényi, one can prepare only two information measures: Shannon and Rényi entropy. Indeed, using this formalism Rényi characterized these additive entropies in terms of axioms of quasilinear mean. As additivity is a characteristic property of Shannon entropy, pseudo-additivity of the form $x \oplus_{q} y = x + y + (1-q)x y$ is a characteristic property of nonextensive (or Tsallis) entropy. One can apply Rényi's recipe in the nonextensive case by replacing the linear averaging in Tsallis entropy with KN-averages and thereby imposing the constraint of pseudo-additivity. In this paper we show that nonextensive entropy is unique under the Rényi's recipe, and there by give a characterization.
A dissemination strategy for immunizing scale-free networks
Venue: arXiv cs.NI 2005
Year: 2005

We consider the problem of distributing a vaccine for immunizing a scale-free network against a given virus or worm. We introduce a new method, based on vaccine dissemination, that seems to reflect more accurately what is expected to occur in real-world networks. Also, since the dissemination is performed using only local information, the method can be easily employed in practice. Using a random-graph framework, we analyze our method both mathematically and by means of simulations. We demonstrate its efficacy regarding the trade-off between the expected number of nodes that receive the vaccine and the network's resulting vulnerability to develop an epidemic as the virus or worm attempts to infect one of its nodes. For some scenarios, the new method is seen to render the network practically invulnerable to attacks while requiring only a small fraction of the nodes to receive the vaccine.
Approximating Clustering of Fingerprint Vectors with Missing Values
Venue: arXiv cs.DS 2005
Year: 2005

The problem of clustering fingerprint vectors is an interesting problem in Computational Biology that has been proposed in (Figureroa et al. 2004). In this paper we show some improvements in closing the gaps between the known lower bounds and upper bounds on the approximability of some variants of the biological problem. Namely we are able to prove that the problem is APX-hard even when each fingerprint contains only two unknown position. Moreover we have studied some variants of the orginal problem, and we give two 2-approximation algorithm for the IECMV and OECMV problems when the number of unknown entries for each vector is at most a constant.