OpenRaiser/Intern-Atlas huggingface dataset:
A Union Bound Approximation for Rapid Performance Evaluation of Punctured Turbo Codes
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, we present a simple technique to approximate the performance union bound of a punctured turbo code. The bound approximation exploits only those terms of the transfer function that have a major impact on the overall performance. We revisit the structure of the constituent convolutional encoder and we develop a rapid method to calculate the most significant terms of the transfer function of a turbo encoder. We demonstrate that, for a large interleaver size, this approximation is very accurate. Furthermore, we apply our proposed method to a family of punctured turbo codes, which we call pseudo-randomly punctured codes. We conclude by emphasizing the benefits of our approach compared to those employed previously. We also highlight the advantages of pseudo-random puncturing over other puncturing schemes.
The Simplest Solution to an Underdetermined System of Linear Equations
Venue: arXiv cs.IT 2007
Year: 2007

Consider a d*n matrix A, with d<n. The problem of solving for x in y=Ax is underdetermined, and has infinitely many solutions (if there are any). Given y, the minimum Kolmogorov complexity solution (MKCS) of the input x is defined to be an input z (out of many) with minimum Kolmogorov-complexity that satisfies y=Az. One expects that if the actual input is simple enough, then MKCS will recover the input exactly. This paper presents a preliminary study of the existence and value of the complexity level up to which such a complexity-based recovery is possible. It is shown that for the set of all d*n binary matrices (with entries 0 or 1 and d<n), MKCS exactly recovers the input for an overwhelming fraction of the matrices provided the Kolmogorov complexity of the input is O(d). A weak converse that is loose by a log n factor is also established for this case. Finally, we investigate the difficulty of finding a matrix that has the property of recovering inputs with complexity of O(d) using MKCS.
Security Implications of Converged Networks and Protecting Them, without Compromising Efficiency
Venue: arXiv cs.NI 2007
Year: 2007

This dissertation has extensively looked into all aspects of VoIP commu-nications technology, and information presented in preceding chapters, which build up a solid framework to discuss the conceptual design model, and investigate features that could be incorporated for actual Pro-jects, with parameters that are tested on field values. The dissertation follows a five-course model, for answering different questions, both tech-nical and businesslike, around central issues, that have been crucial to explanation of the topic; starting with a general overview of VoIP tech-nology, analyzing current VoIP encryption methods, identifying security threats, designing a robust VoIP system based on particulars discussed in preceding chapters, and finally, a VoIP simulation.
Tree automata and separable sets of input variables
Venue: arXiv cs.CC 2007
Year: 2007

We consider the computational complexity of tree transducers, depending on their separable sets of input variables.
Exploiting social networks dynamics for P2P resource organisation
Venue: arXiv cs.DC 2007
Year: 2007

In this paper we present a formal description of PROSA, a P2P resource management system heavily inspired by social networks. Social networks have been deeply studied in the last two decades in order to understand how communities of people arise and grow. It is a widely known result that networks of social relationships usually evolves to small-worlds, i.e. networks where nodes are strongly connected to neighbours and separated from all other nodes by a small amount of hops. This work shows that algorithms implemented into PROSA allow to obtain an efficient small-world P2P network.
AICA: a New Pair Force Evaluation Method for Parallel Molecular Dynamics in Arbitrary Geometries
Venue: arXiv cs.CE 2007
Year: 2007

A new algorithm for calculating intermolecular pair forces in Molecular Dynamics (MD) simulations on a distributed parallel computer is presented. The Arbitrary Interacting Cells Algorithm (AICA) is designed to operate on geometrical domains defined by an unstructured, arbitrary polyhedral mesh, which has been spatially decomposed into irregular portions for parallelisation. It is intended for nano scale fluid mechanics simulation by MD in complex geometries, and to provide the MD component of a hybrid MD/continuum simulation. AICA has been implemented in the open-source computational toolbox OpenFOAM, and verified against a published MD code.
Fast Exact Method for Solving the Travelling Salesman Problem
Venue: arXiv cs.CC 2007
Year: 2007

This paper describes TSP exact solution of polynomial complexity. It is considered properties of proposed method. Effectiveness of proposed solution is illustrated by outcomes of computer modeling.
An Optimal Linear Time Algorithm for Quasi-Monotonic Segmentation
Venue: arXiv cs.DS 2007
Year: 2007

Monotonicity is a simple yet significant qualitative characteristic. We consider the problem of segmenting an array in up to K segments. We want segments to be as monotonic as possible and to alternate signs. We propose a quality metric for this problem, present an optimal linear time algorithm based on novel formalism, and compare experimentally its performance to a linear time top-down regression algorithm. We show that our algorithm is faster and more accurate. Applications include pattern recognition and qualitative modeling.
Designing a Resource Broker for Heterogeneous Grids
Venue: arXiv cs.DC 2007
Year: 2007

Grids provide uniform access to aggregations of heterogeneous resources and services such as computers, networks and storage owned by multiple organizations. However, such a dynamic environment poses many challenges for application composition and deployment. In this paper, we present the design of the Gridbus Grid resource broker that allows users to create applications and specify different objectives through different interfaces without having to deal with the complexity of Grid infrastructure. We present the unique requirements that motivated our design and discuss how these provide flexibility in extending the functionality of the broker to support different low-level middlewares and user interfaces. We evaluate the broker with different job profiles and Grid middleware and conclude with the lessons learnt from our development experience.
Joint Design and Separation Principle for Opportunistic Spectrum Access in the Presence of Sensing Errors
Venue: arXiv cs.NI 2007
Year: 2007

We address the design of opportunistic spectrum access (OSA) strategies that allow secondary users to independently search for and exploit instantaneous spectrum availability. Integrated in the joint design are three basic components: a spectrum sensor that identifies spectrum opportunities, a sensing strategy that determines which channels in the spectrum to sense, and an access strategy that decides whether to access based on imperfect sensing outcomes. We formulate the joint PHY-MAC design of OSA as a constrained partially observable Markov decision process (POMDP). Constrained POMDPs generally require randomized policies to achieve optimality, which are often intractable. By exploiting the rich structure of the underlying problem, we establish a separation principle for the joint design of OSA. This separation principle reveals the optimality of myopic policies for the design of the spectrum sensor and the access strategy, leading to closed-form optimal solutions. Furthermore, decoupling the design of the sensing strategy from that of the spectrum sensor and the access strategy, the separation principle reduces the constrained POMDP to an unconstrained one, which admits deterministic optimal policies. Numerical examples are provided to study the design tradeoffs, the interaction between the spectrum sensor and the sensing and access strategies, and the robustness of the ensuing design to model mismatch.
Monte-Carlo Simulations of the First Passage Time for Multivariate Jump-Diffusion Processes in Financial Applications
Venue: arXiv cs.CE 2007
Year: 2007

Many problems in finance require the information on the first passage time (FPT) of a stochastic process. Mathematically, such problems are often reduced to the evaluation of the probability density of the time for such a process to cross a certain level, a boundary, or to enter a certain region. While in other areas of applications the FPT problem can often be solved analytically, in finance we usually have to resort to the application of numerical procedures, in particular when we deal with jump-diffusion stochastic processes (JDP). In this paper, we propose a Monte-Carlo-based methodology for the solution of the first passage time problem in the context of multivariate (and correlated) jump-diffusion processes. The developed technique provide an efficient tool for a number of applications, including credit risk and option pricing. We demonstrate its applicability to the analysis of the default rates and default correlations of several different, but correlated firms via a set of empirical data.
Efficient estimation of default correlation for multivariate jump-diffusion processes
Venue: arXiv cs.CE 2007
Year: 2007

Evaluation of default correlation is an important task in credit risk analysis. In many practical situations, it concerns the joint defaults of several correlated firms, the task that is reducible to a first passage time (FPT) problem. This task represents a great challenge for jump-diffusion processes (JDP), where except for very basic cases, there are no analytical solutions for such problems. In this contribution, we generalize our previous fast Monte-Carlo method (non-correlated jump-diffusion cases) for multivariate (and correlated) jump-diffusion processes. This generalization allows us, among other things, to evaluate the default events of several correlated assets based on a set of empirical data. The developed technique is an efficient tool for a number of other applications, including credit risk and option pricing.
Finite Volume Analysis of Nonlinear Thermo-mechanical Dynamics of Shape Memory Alloys
Venue: arXiv cs.CE 2007
Year: 2007

In this paper, the finite volume method is developed to analyze coupled dynamic problems of nonlinear thermoelasticity. The major focus is given to the description of martensitic phase transformations essential in the modelling of shape memory alloys. Computational experiments are carried out to study the thermo-mechanical wave interactions in a shape memory alloy rod, and a patch. Both mechanically and thermally induced phase transformations, as well as hysteresis effects, in a one-dimensional structure are successfully simulated with the developed methodology. In the two-dimensional case, the main focus is given to square-to-rectangular transformations and examples of martensitic combinations under different mechanical loadings are provided.
Can we Compute the Similarity Between Surfaces?
Venue: arXiv cs.CG 2007
Year: 2007

A suitable measure for the similarity of shapes represented by parameterized curves or surfaces is the Fréchet distance. Whereas efficient algorithms are known for computing the Fréchet distance of polygonal curves, the same problem for triangulated surfaces is NP-hard. Furthermore, it remained open whether it is computable at all. Here, using a discrete approximation we show that it is {\em upper semi-computable}, i.e., there is a non-halting Turing machine which produces a monotone decreasing sequence of rationals converging to the result. It follows that the decision problem, whether the Fréchet distance of two given surfaces lies below some specified value, is recursively enumerable. Furthermore, we show that a relaxed version of the problem, the computation of the {\em weak Fréchet distance} can be solved in polynomial time. For this, we give a computable characterization of the weak Fréchet distance in a geometric data structure called the {\em free space diagram}.
Algorithmic Information Theory: a brief non-technical guide to the field
Venue: arXiv cs.IT 2007
Year: 2007

This article is a brief guide to the field of algorithmic information theory (AIT), its underlying philosophy, and the most important concepts. AIT arises by mixing information theory and computation theory to obtain an objective and absolute notion of information in an individual object, and in so doing gives rise to an objective and robust notion of randomness of individual objects. This is in contrast to classical information theory that is based on random variables and communication, and has no bearing on information and randomness of individual objects. After a brief overview, the major subfields, applications, history, and a map of the field are presented.
LIBOPT - An environment for testing solvers on heterogeneous collections of problems - Version 1.0
Venue: arXiv cs.MS 2007
Year: 2007

The Libopt environment is both a methodology and a set of tools that can be used for testing, comparing, and profiling solvers on problems belonging to various collections. These collections can be heterogeneous in the sense that their problems can have common features that differ from one collection to the other. Libopt brings a unified view on this composite world by offering, for example, the possibility to run any solver on any problem compatible with it, using the same Unix/Linux command. The environment also provides tools for comparing the results obtained by solvers on a specified set of problems. Most of the scripts going with the Libopt environment have been written in Perl.
Path Loss Models Based on Stochastic Rays
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, two-dimensional percolation lattices are applied to describe wireless propagation environment, and stochastic rays are employed to model the trajectories of radio waves. We first derive the probability that a stochastic ray undergoes certain number of collisions at a specific spatial location. Three classes of stochastic rays with different constraint conditions are considered: stochastic rays of random walks, and generic stochastic rays with two different anomalous levels. Subsequently, we obtain the closed-form formulation of mean received power of radio waves under non line-of-sight conditions for each class of stochastic ray. Specifically, the determination of model parameters and the effects of lattice structures on the path loss are investigated. The theoretical results are validated by comparison with experimental data.
Redesigning Decision Matrix Method with an indeterminacy-based inference process
Venue: arXiv cs.AI 2007
Year: 2007

For academics and practitioners concerned with computers, business and mathematics, one central issue is supporting decision makers. In this paper, we propose a generalization of Decision Matrix Method (DMM), using Neutrosophic logic. It emerges as an alternative to the existing logics and it represents a mathematical model of uncertainty and indeterminacy. This paper proposes the Neutrosophic Decision Matrix Method as a more realistic tool for decision making. In addition, a de-neutrosophication process is included.
A Few Graph-Based Relational Numerical Abstract Domains
Venue: arXiv cs.PL 2007
Year: 2007

This article presents the systematic design of a class of relational numerical abstract domains from non-relational ones. Constructed domains represent sets of invariants of the form (vj - vi in C), where vj and vi are two variables, and C lives in an abstraction of P(Z), P(Q), or P(R). We will call this family of domains weakly relational domains. The underlying concept allowing this construction is an extension of potential graphs and shortest-path closure algorithms in exotic-like algebras. Example constructions are given in order to retrieve well-known domains as well as new ones. Such domains can then be used in the Abstract Interpretation framework in order to design various static analyses. Amajor benfit of this construction is its modularity, allowing to quickly implement new abstract domains from existing ones.
Symbolic Methods to Enhance the Precision of Numerical Abstract Domains
Venue: arXiv cs.PL 2007
Year: 2007

We present lightweight and generic symbolic methods to improve the precison of numerical static analyses based on Abstract Interpretation. The main idea is to simplify numerical expressions before they are fed to abstract transfer functions. An important novelty is that these simplifications are performed on-the-fly, using information gathered dynamically by the analyzer. A first method, called "linearization," allows abstracting arbitrary expressions into affine forms with interval coefficients while simplifying them. A second method, called "symbolic constant propagation," enhances the simplification feature of the linearization by propagating assigned expressions in a symbolic way. Combined together, these methods increase the relationality level of numerical abstract domains and make them more robust against program transformations. We show how they can be integrated within the classical interval, octagon and polyhedron domains. These methods have been incorporated within the Astrée static analyzer that checks for the absence of run-time errors in embedded critical avionics software. We present an experimental proof of their usefulness.
The Octagon Abstract Domain
Venue: arXiv cs.PL 2007
Year: 2007

This article presents a new numerical abstract domain for static analysis by abstract interpretation. It extends a former numerical abstract domain based on Difference-Bound Matrices and allows us to represent invariants of the form (+/-x+/-y<=c), where x and y are program variables and c is a real constant. We focus on giving an efficient representation based on Difference-Bound Matrices - O(n2) memory cost, where n is the number of variables - and graph-based algorithms for all common abstract operators - O(n3) time cost. This includes a normal form algorithm to test equivalence of representation and a widening operator to compute least fixpoint approximations.
Social Information Processing in Social News Aggregation
Venue: arXiv cs.CY 2007
Year: 2007

The rise of the social media sites, such as blogs, wikis, Digg and Flickr among others, underscores the transformation of the Web to a participatory medium in which users are collaboratively creating, evaluating and distributing information. The innovations introduced by social media has lead to a new paradigm for interacting with information, what we call 'social information processing'. In this paper, we study how social news aggregator Digg exploits social information processing to solve the problems of document recommendation and rating. First, we show, by tracking stories over time, that social networks play an important role in document recommendation. The second contribution of this paper consists of two mathematical models. The first model describes how collaborative rating and promotion of stories emerges from the independent decisions made by many users. The second model describes how a user's influence, the number of promoted stories and the user's social network, changes in time. We find qualitative agreement between predictions of the model and user data gathered from Digg.
Geographic Routing Around Obstacles in Wireless Sensor Networks
Venue: arXiv cs.DC 2007
Year: 2007

Geographic routing is becoming the protocol of choice for many sensor network applications. The current state of the art is unsatisfactory: some algorithms are very efficient, however they require a preliminary planarization of the communication graph. Planarization induces overhead and is not realistic in many scenarios. On the otherhand, georouting algorithms which do not rely on planarization have fairly low success rates and either fail to route messages around all but the simplest obstacles or have a high topology control overhead (e.g. contour detection algorithms). To overcome these limitations, we propose GRIC, the first lightweight and efficient on demand (i.e. all-to-all) geographic routing algorithm which does not require planarization and has almost 100% delivery rates (when no obstacles are added). Furthermore, the excellent behavior of our algorithm is maintained even in the presence of large convex obstacles. The case of hard concave obstacles is also studied; such obstacles are hard instances for which performance diminishes.
A Note on Approximate Nearest Neighbor Methods
Venue: arXiv cs.IR 2007
Year: 2007

A number of authors have described randomized algorithms for solving the epsilon-approximate nearest neighbor problem. In this note I point out that the epsilon-approximate nearest neighbor property often fails to be a useful approximation property, since epsilon-approximate solutions fail to satisfy the necessary preconditions for using nearest neighbors for classification and related tasks.
Self-adaptive Gossip Policies for Distributed Population-based Algorithms
Venue: arXiv cs.DC 2007
Year: 2007

Gossipping has demonstrate to be an efficient mechanism for spreading information among P2P networks. Within the context of P2P computing, we propose the so-called Evolvable Agent Model for distributed population-based algorithms which uses gossipping as communication policy, and represents every individual as a self-scheduled single thread. The model avoids obsolete nodes in the population by defining a self-adaptive refresh rate which depends on the latency and bandwidth of the network. Such a mechanism balances the migration rate to the congestion of the links pursuing global population coherence. We perform an experimental evaluation of this model on a real parallel system and observe how solution quality and algorithm speed scale with the number of processors with this seamless approach.
Sequential decoding for lossless streaming source coding with side information
Venue: arXiv cs.IT 2007
Year: 2007

The problem of lossless fixed-rate streaming coding of discrete memoryless sources with side information at the decoder is studied. A random time-varying tree-code is used to sequentially bin strings and a Stack Algorithm with a variable bias uses the side information to give a delay-universal coding system for lossless source coding with side information. The scheme is shown to give exponentially decaying probability of error with delay, with exponent equal to Gallager's random coding exponent for sources with side information. The mean of the random variable of computation for the stack decoder is bounded, and conditions on the bias are given to guarantee a finite $ρ^{th}$ moment for $0 \leq ρ\leq 1$. Further, the problem is also studied in the case where there is a discrete memoryless channel between encoder and decoder. The same scheme is slightly modified to give a joint-source channel encoder and Stack Algorithm-based sequential decoder using side information. Again, by a suitable choice of bias, the probability of error decays exponentially with delay and the random variable of computation has a finite mean. Simulation results for several examples are given.
Differential Equations for Algebraic Functions
Venue: arXiv cs.SC 2007
Year: 2007

It is classical that univariate algebraic functions satisfy linear differential equations with polynomial coefficients. Linear recurrences follow for the coefficients of their power series expansions. We show that the linear differential equation of minimal order has coefficients whose degree is cubic in the degree of the function. We also show that there exists a linear differential equation of order linear in the degree whose coefficients are only of quadratic degree. Furthermore, we prove the existence of recurrences of order and degree close to optimal. We study the complexity of computing these differential equations and recurrences. We deduce a fast algorithm for the expansion of algebraic series.