OpenRaiser/Intern-Atlas huggingface dataset:
Exponential Sums, Cyclic Codes and Sequences: the Odd Characteristic Kasami Case
Venue: arXiv cs.IT 2009
Year: 2009

Let $q=p^n$ with $n=2m$ and $p$ be an odd prime. Let $0\leq k\leq n-1$ and $k\neq m$. In this paper we determine the value distribution of following exponential(character) sums \[\sum\limits_{x\in \bF_q}ζ_p^{\Tra_1^m (αx^{p^{m}+1})+\Tra_1^n(βx^{p^k+1})}\quad(α\in \bF_{p^m},β\in \bF_{q})\] and \[\sum\limits_{x\in \bF_q}ζ_p^{\Tra_1^m (αx^{p^{m}+1})+\Tra_1^n(βx^{p^k+1}+\ga x)}\quad(α\in \bF_{p^m},β,\ga\in \bF_{q})\] where $\Tra_1^n: \bF_q\ra \bF_p$ and $\Tra_1^m: \bF_{p^m}\ra\bF_p$ are the canonical trace mappings and $ζ_p=e^{\frac{2πi}{p}}$ is a primitive $p$-th root of unity. As applications: (1). We determine the weight distribution of the cyclic codes $\cC_1$ and $\cC_2$ over $\bF_{p^t}$ with parity-check polynomials $h_2(x)h_3(x)$ and $h_1(x)h_2(x)h_3(x)$ respectively where $t$ is a divisor of $d=\gcd(m,k)$, and $h_1(x)$, $h_2(x)$ and $h_3(x)$ are the minimal polynomials of $π^{-1}$, $π^{-(p^k+1)}$ and $π^{-(p^m+1)}$ over $\bF_{p^t}$ respectively for a primitive element $π$ of $\bF_q$. (2). We determine the correlation distribution among a family of m-sequences. This paper extends the results in \cite{Zen Li}.
A Multipath Energy-Aware On demand Source Routing Protocol for Mobile Ad-Hoc Networks
Venue: arXiv cs.NI 2009
Year: 2009

Energy consumption is the most challenging issue in routing protocol design for mobile ad-hoc networks (MANETs), since mobile nodes are battery powered. Furthermore, replacing or recharging batteries is often impossible in critical environments such as in military or rescue missions. In a MANET, the energy depletion of a node does not affect the node itself only, but the overall network lifetime. In this paper, we present multipath and energy-aware on demand source routing (MEA-DSR) protocol, which exploits route diversity and information about batteries-energy levels for balancing energy consumption between mobile nodes. Simulation results, have shown that MEA-DSR protocol is more energy efficient than DSR in almost mobility scenarios.
Dipole Vectors in Images Processing
Venue: arXiv cs.CV 2009
Year: 2009

Instead of evaluating the gradient field of the brightness map of an image, we propose the use of dipole vectors. This approach is obtained by adapting to the image gray-tone distribution the definition of the dipole moment of charge distributions. We will show how to evaluate the dipoles and obtain a vector field, which can be a good alternative to the gradient field in pattern recognition.
Minimal Economic Distributed Computing
Venue: arXiv cs.DC 2009
Year: 2009

In an ideal distributed computing infrastructure, users would be able to use diverse distributed computing resources in a simple coherent way, with guaranteed security and efficient use of shared resources in accordance with the wishes of the owners of the resources. Our strategy for approaching this ideal is to first find the simplest structure within which these goals can plausibly be achieved. This structure, we find, is given by a particular recursive distributive lattice freely constructed from a presumed partially ordered set of all data in the infrastructure. Minor syntactic adjustments to the resulting algebra yields a simple language resembling a UNIX shell, a concept of execution and an interprocess protocol. Persons, organizations and servers within the system express their interests explicitly via a hierarchical currency. The currency provides a common framework for treating authentication, access control and resource sharing as economic problems while also introducing a new dimension for improving the infrastructure over time by designing system components which compete with each other to earn the currency. We explain these results, discuss experience with an implementation called egg and point out areas where more research is needed.
Simulation and Performance Analysis of MP-OLSR for Mobile Ad hoc Networks
Venue: arXiv cs.NI 2009
Year: 2009

Mobile ad hoc networks (MANETs) consist of a collection of wireless mobile nodes which dynamically exchange data without reliance on a fixed base station or a wired backbone network, which makes routing a crucial issue for the design of a ad hoc networks. In this paper we discussed a hybrid multipath routing protocol named MP-OLSR. It is based on the link state algorithm and employs periodic exchange of messages to maintain topology information of the networks. In the mean time, it updates the routing table in an on-demand scheme and forwards the packets in multiple paths which have been determined at the source. If a link failure is detected, the algorithm recovers the route automatically. Concerning the instability of the wireless networks, the redundancy coding is used to improve the delivery ratio. The simulation in NS2 shows that the new protocol can effectively improve the performance of the networks.
Measuring Independence of Datasets
Venue: arXiv cs.DS 2009
Year: 2009

A data stream model represents setting where approximating pairwise, or $k$-wise, independence with sublinear memory is of considerable importance. In the streaming model the joint distribution is given by a stream of $k$-tuples, with the goal of testing correlations among the components measured over the entire stream. In the streaming model, Indyk and McGregor (SODA 08) recently gave exciting new results for measuring pairwise independence. The Indyk and McGregor methods provide $\log{n}$-approximation under statistical distance between the joint and product distributions in the streaming model. Indyk and McGregor leave, as their main open question, the problem of improving their $\log n$-approximation for the statistical distance metric. In this paper we solve the main open problem posed by of Indyk and McGregor for the statistical distance for pairwise independence and extend this result to any constant $k$. In particular, we present an algorithm that computes an $(ε, δ)$-approximation of the statistical distance between the joint and product distributions defined by a stream of $k$-tuples. Our algorithm requires $O(({1\over ε}\log({nm\over δ}))^{(30+k)^k})$ memory and a single pass over the data stream.
Non Linear System for a Veritable PID Substitute
Venue: arXiv cs.DM 2009
Year: 2009

The paper deals with a non-linear system largely used in biology, which, in certain conditions and for particular coefficient values, becomes linear, with a linear diagram over a large range of time. It can be used as a veritable regulator in systems' control
Villager's dilemma
Venue: arXiv cs.GT 2009
Year: 2009

With deeper study of the Game Theory, some conditions of Prisoner's Dilemma is no longer suitable of games in real life. So we try to develop a new model-Villager's Dilemma which has more realistic conditions to stimulate the process of game. It is emphasize that Prisoner's Dilemma is an exception which is lack of universality and the importance of rules in the game. And it puts forward that to let the rule maker take part in the game and specifies game players can stop the game as they like. This essay describes the basic model, the villager's dilemma (VD) and put some extended use of it, and points out the importance of rules and the effect it has on the result of the game. It briefly describes the disadvantage of Prisoner's Dilemma and advantage Villager's Dilemma has. It summarizes the premise and scope of application of Villager's Dilemma, and provides theory foundation for making rules for game and forecast of the future of the game.
A Graph Analysis of the Linked Data Cloud
Venue: arXiv cs.CY 2009
Year: 2009

The Linked Data community is focused on integrating Resource Description Framework (RDF) data sets into a single unified representation known as the Web of Data. The Web of Data can be traversed by both man and machine and shows promise as the \textit{de facto} standard for integrating data world wide much like the World Wide Web is the \textit{de facto} standard for integrating documents. On February 27$^\text{th}$ of 2009, an updated Linked Data cloud visualization was made publicly available. This visualization represents the various RDF data sets currently in the Linked Data cloud and their interlinking relationships. For the purposes of this article, this visual representation was manually transformed into a directed graph and analyzed.
Rotation Distance is Fixed-Parameter Tractable
Venue: arXiv cs.DS 2009
Year: 2009

Rotation distance between trees measures the number of simple operations it takes to transform one tree into another. There are no known polynomial-time algorithms for computing rotation distance. In the case of ordered rooted trees, we show that the rotation distance between two ordered trees is fixed-parameter tractable, in the parameter, k, the rotation distance. The proof relies on the kernalization of the initial trees to trees with size bounded by 7k.
A Linear-Time Approximation Algorithm for Rotation Distance
Venue: arXiv cs.DS 2009
Year: 2009

Rotation distance between rooted binary trees measures the number of simple operations it takes to transform one tree into another. There are no known polynomial-time algorithms for computing rotation distance. We give an efficient, linear-time approximation algorithm, which estimates the rotation distance, within a provable factor of 2, between ordered rooted binary trees. .
Impact of Cognitive Radio on Future Management of Spectrum
Venue: arXiv cs.AI 2009
Year: 2009

Cognitive radio is a breakthrough technology which is expected to have a profound impact on the way radio spectrum will be accessed, managed and shared in the future. In this paper I examine some of the implications of cognitive radio for future management of spectrum. Both a near-term view involving the opportunistic spectrum access model and a longer-term view involving a self-regulating dynamic spectrum access model within a society of cognitive radios are discussed.
An introduction to DSmT
Venue: arXiv cs.AI 2009
Year: 2009

The management and combination of uncertain, imprecise, fuzzy and even paradoxical or high conflicting sources of information has always been, and still remains today, of primal importance for the development of reliable modern information systems involving artificial reasoning. In this introduction, we present a survey of our recent theory of plausible and paradoxical reasoning, known as Dezert-Smarandache Theory (DSmT), developed for dealing with imprecise, uncertain and conflicting sources of information. We focus our presentation on the foundations of DSmT and on its most important rules of combination, rather than on browsing specific applications of DSmT available in literature. Several simple examples are given throughout this presentation to show the efficiency and the generality of this new approach.
General Game Management Agent
Venue: arXiv cs.GT 2009
Year: 2009

The task of managing general game playing in a multi-agent system is the problem addressed in this paper. It is considered to be done by an agent. There are many reasons for constructing such an agent, called general game management agent. This agent manages strategic interactions between other agents - players, natural or also artificial. The agent records the interaction for further benchmarking and analysis. He can also be used for a kind of restricted communications. His behavior is defined by a game description written in a logic-based language. The language, we present for this application, is more expressive than the language GDL, which is already used for such purposes. Our language can represent imperfect information and time dependent elements of a game. Time dependent elements like delays and timeouts are of crucial importance for interactions between players with bounded processing power like humans. We provide examples to show the feasibility of our approach. A way for game theoretical solving of an interaction description in our language is considered as future work.
On Stability Region and Delay Performance of Linear-Memory Randomized Scheduling for Time-Varying Networks
Venue: arXiv cs.NI 2009
Year: 2009

Throughput optimal scheduling policies in general require the solution of a complex and often NP-hard optimization problem. Related literature has shown that in the context of time-varying channels, randomized scheduling policies can be employed to reduce the complexity of the optimization problem but at the expense of a memory requirement that is exponential in the number of data flows. In this paper, we consider a Linear-Memory Randomized Scheduling Policy (LM-RSP) that is based on a pick-and-compare principle in a time-varying network with $N$ one-hop data flows. For general ergodic channel processes, we study the performance of LM-RSP in terms of its stability region and average delay. Specifically, we show that LM-RSP can stabilize a fraction of the capacity region. Our analysis characterizes this fraction as well as the average delay as a function of channel variations and the efficiency of LM-RSP in choosing an appropriate schedule vector. Applying these results to a class of Markovian channels, we provide explicit results on the stability region and delay performance of LM-RSP.
Algorithm for Finding $k$-Vertex Out-trees and its Application to $k$-Internal Out-branching Problem
Venue: arXiv cs.DS 2009
Year: 2009

An out-tree $T$ is an oriented tree with only one vertex of in-degree zero. A vertex $x$ of $T$ is internal if its out-degree is positive. We design randomized and deterministic algorithms for deciding whether an input digraph contains a given out-tree with $k$ vertices. The algorithms are of runtime $O^*(5.704^k)$ and $O^*(5.704^{k(1+o(1))})$, respectively. We apply the deterministic algorithm to obtain a deterministic algorithm of runtime $O^*(c^k)$, where $c$ is a constant, for deciding whether an input digraph contains a spanning out-tree with at least $k$ internal vertices. This answers in affirmative a question of Gutin, Razgon and Kim (Proc. AAIM'08).
Hospital Acquired Infections: Advantages of a Computerized Surveillance
Venue: arXiv cs.DM 2009
Year: 2009

To asses the advantages of a computerized surveillance system to detect Healthcare-Associated Infections (HAI). All HAI reported to the Timis County branch of the Romanian National Health Insurance and the Public Health Authority during the year 2007 were collected and assessed for validity
Group code structures on affine-invariant codes
Venue: arXiv cs.IT 2009
Year: 2009

A group code structure of a linear code is a description of the code as one-sided or two-sided ideal of a group algebra of a finite group. In these realizations, the group algebra is identified with the ambient space, and the group elements with the coordinates of the ambient space. It is well known that every affine-invariant code of length $p^m$, with $p$ prime, can be realized as an ideal of the group algebra $\F\I$, where $\I$ is the underlying additive group of the field with $p^m$ elements. In this paper we describe all the group code structures of an affine-invariant code of length $p^m$ in terms of a family of maps from $\I$ to the group of automorphisms of $\I$.
Home Heating Systems Design using PHP and MySQL Databases
Venue: arXiv cs.DB 2009
Year: 2009

This paper presents the use of a computer application based on a MySQL database, managed by PHP programs, allowing the selection of a heating device using coefficient-based calculus.
Symmetry Breaking Using Value Precedence
Venue: arXiv cs.AI 2009
Year: 2009

We present a comprehensive study of the use of value precedence constraints to break value symmetry. We first give a simple encoding of value precedence into ternary constraints that is both efficient and effective at breaking symmetry. We then extend value precedence to deal with a number of generalizations like wreath value and partial interchangeability. We also show that value precedence is closely related to lexicographical ordering. Finally, we consider the interaction between value precedence and symmetry breaking constraints for variable symmetries.
Tetravex is NP-complete
Venue: arXiv cs.CC 2009
Year: 2009

Tetravex is a widely played one person computer game in which you are given $n^2$ unit tiles, each edge of which is labelled with a number. The objective is to place each tile within a $n$ by $n$ square such that all neighbouring edges are labelled with an identical number. Unfortunately, playing Tetravex is computationally hard. More precisely, we prove that deciding if there is a tiling of the Tetravex board is NP-complete. Deciding where to place the tiles is therefore NP-hard. This may help to explain why Tetravex is a good puzzle. This result compliments a number of similar results for one person games involving tiling. For example, NP-completeness results have been shown for: the offline version of Tetris, KPlumber (which involves rotating tiles containing drawings of pipes to make a connected network), and shortest sliding puzzle problems. It raises a number of open questions. For example, is the infinite version Turing-complete? How do we generate Tetravex problems which are truly puzzling as random NP-complete problems are often surprising easy to solve? Can we observe phase transition behaviour? What about the complexity of the problem when it is guaranteed to have an unique solution? How do we generate puzzles with unique solutions?
Stochastic Constraint Programming
Venue: arXiv cs.AI 2009
Year: 2009

To model combinatorial decision problems involving uncertainty and probability, we introduce stochastic constraint programming. Stochastic constraint programs contain both decision variables (which we can set) and stochastic variables (which follow a probability distribution). They combine together the best features of traditional constraint satisfaction, stochastic integer programming, and stochastic satisfiability. We give a semantics for stochastic constraint programs, and propose a number of complete algorithms and approximation procedures. Finally, we discuss a number of extensions of stochastic constraint programming to relax various assumptions like the independence between stochastic variables, and compare with other approaches for decision making under uncertainty.
A Linear Programming Driven Genetic Algorithm for Meta-Scheduling on Utility Grids
Venue: arXiv cs.DC 2009
Year: 2009

The user-level brokers in grids consider individual application QoS requirements and minimize their cost without considering demands from other users. This results in contention for resources and sub-optimal schedules. Meta-scheduling in grids aims to address this scheduling problem, which is NP hard due to its combinatorial nature. Thus, many heuristic-based solutions using Genetic Algorithm (GA) have been proposed, apart from traditional algorithms such as Greedy and FCFS. We propose a Linear Programming/Integer Programming model (LP/IP) for scheduling these applications to multiple resources. We also propose a novel algorithm LPGA (Linear programming driven Genetic Algorithm) which combines the capabilities of LP and GA. The aim of this algorithm is to obtain the best metaschedule for utility grids which minimize combined cost of all users in a coordinated manner. Simulation results show that our proposed integrated algorithm offers the best schedule having the minimum processing cost with negligible time overhead.
MIMO Based Multimedia Communication System
Venue: arXiv cs.NI 2009
Year: 2009

High data rate is required for multimedia communication. But the communication at high data rate is always challenging. In this work we have successfully performed data chatting, Voice chatting and high quality video transmission between two distant units using MIMO adapter, Direct sequence spread spectrum system and MATLAB/SIMULINK platform.
Heuristic Reasoning on Graph and Game Complexity of Sudoku
Venue: arXiv cs.AI 2009
Year: 2009

The Sudoku puzzle has achieved worldwide popularity recently, and attracted great attention of the computational intelligence community. Sudoku is always considered as Satisfiability Problem or Constraint Satisfaction Problem. In this paper, we propose to focus on the essential graph structure underlying the Sudoku puzzle. First, we formalize Sudoku as a graph. Then a solving algorithm based on heuristic reasoning on the graph is proposed. The related r-Reduction theorem, inference theorem and their properties are proved, providing the formal basis for developments of Sudoku solving systems. In order to evaluate the difficulty levels of puzzles, a quantitative measurement of the complexity level of Sudoku puzzles based on the graph structure and information theory is proposed. Experimental results show that all the puzzles can be solved fast using the proposed heuristic reasoning, and that the proposed game complexity metrics can discriminate difficulty levels of puzzles perfectly.
Reconstructing Curves from Points and Tangents
Venue: arXiv cs.CG 2009
Year: 2009

Reconstructing a finite set of curves from an unordered set of sample points is a well studied topic. There has been less effort that considers how much better the reconstruction can be if tangential information is given as well. We show that if curves are separated from each other by a distance D, then the sampling rate need only be O(sqrt(D)) for error-free reconstruction. For the case of point data alone, O(D) sampling is required.
Statistical Eigenmode Transmission over Jointly-Correlated MIMO Channels
Venue: arXiv cs.IT 2009
Year: 2009

We investigate MIMO eigenmode transmission using statistical channel state information at the transmitter. We consider a general jointly-correlated MIMO channel model, which does not require separable spatial correlations at the transmitter and receiver. For this model, we first derive a closed-form tight upper bound for the ergodic capacity, which reveals a simple and interesting relationship in terms of the matrix permanent of the eigenmode channel coupling matrix and embraces many existing results in the literature as special cases. Based on this closed-form and tractable upper bound expression, we then employ convex optimization techniques to develop low-complexity power allocation solutions involving only the channel statistics. Necessary and sufficient optimality conditions are derived, from which we develop an iterative water-filling algorithm with guaranteed convergence. Simulations demonstrate the tightness of the capacity upper bound and the near-optimal performance of the proposed low-complexity transmitter optimization approach.
Network error correction for unit-delay, memory-free networks using convolutional codes
Venue: arXiv cs.IT 2009
Year: 2009

A single source network is said to be memory-free if all of the internal nodes (those except the source and the sinks) do not employ memory but merely send linear combinations of the symbols received at their incoming edges on their outgoing edges. In this work, we introduce network-error correction for single source, acyclic, unit-delay, memory-free networks with coherent network coding for multicast. A convolutional code is designed at the source based on the network code in order to correct network-errors that correspond to any of a given set of error patterns, as long as consecutive errors are separated by a certain interval which depends on the convolutional code selected. Bounds on this interval and the field size required for constructing the convolutional code with the required free distance are also obtained. We illustrate the performance of convolutional network error correcting codes (CNECCs) designed for the unit-delay networks using simulations of CNECCs on an example network under a probabilistic error model.