OpenRaiser/Intern-Atlas huggingface dataset:
Technological Strategy of Using Global Positioning System: An Analysis
Venue: arXiv cs.NI 2010
Year: 2010

The Global Positioning System (GPS) is a U.S. space-based radionavigation system that provides reliable positioning, navigation, and timing services to civilian users on a continuous worldwide basis -- freely available to all. GPS provides specially coded satellite signals that can be processed in a GPS receiver, enabling the receiver to compute position, velocity and time. Basically GPS works by using four GPS satellite signals to compute positions in three dimensions (and the time offset) in the receiver clock. GPS provides accurate location and time information for an unlimited number of people in all weather, day and night, anywhere in the world. Anyone who needs to keep track of where he or she is, to find his or her way to a specified location, or know what direction and how fast he or she is going can utilize the benefits of the global positioning system. Everyday activities such as banking, mobile phone operations, and even the control of power grids, are facilitated by the accurate timing provided by GPS.
Spreadsheet Auditing Software
Venue: arXiv cs.SE 2010
Year: 2010

It is now widely accepted that errors in spreadsheets are both common and potentially dangerous. Further research has taken place to investigate how frequently these errors occur, what impact they have, how the risk of spreadsheet errors can be reduced by following spreadsheet design guidelines and methodologies, and how effective auditing of a spreadsheet is in the detection of these errors. However, little research exists to establish the usefulness of software tools in the auditing of spreadsheets. This paper documents and tests office software tools designed to assist in the audit of spreadsheets. The test was designed to identify the success of software tools in detecting different types of errors, to identify how the software tools assist the auditor and to determine the usefulness of the tools.
Identification of Logical Errors through Monte-Carlo Simulation
Venue: arXiv cs.SE 2010
Year: 2010

The primary focus of Monte Carlo simulation is to identify and quantify risk related to uncertainty and variability in spreadsheet model inputs. The stress of Monte Carlo simulation often reveals logical errors in the underlying spreadsheet model that might be overlooked during day-to-day use or traditional "what-if" testing. This secondary benefit of simulation requires a trained eye to recognize warning signs of poor model construction.
Stream Productivity by Outermost Termination
Venue: arXiv cs.LO 2010
Year: 2010

Streams are infinite sequences over a given data type. A stream specification is a set of equations intended to define a stream. A core property is productivity: unfolding the equations produces the intended stream in the limit. In this paper we show that productivity is equivalent to termination with respect to the balanced outermost strategy of a TRS obtained by adding an additional rule. For specifications not involving branching symbols balancedness is obtained for free, by which tools for proving outermost termination can be used to prove productivity fully automatically.
Algebraic Network Coding Approach to Deterministic Wireless Relay Networks
Venue: arXiv cs.IT 2010
Year: 2010

The deterministic wireless relay network model, introduced by Avestimehr et al., has been proposed for approximating Gaussian relay networks. This model, known as the ADT network model, takes into account the broadcast nature of wireless medium and interference. Avestimehr et al. showed that the Min-cut Max-flow theorem holds in the ADT network. In this paper, we show that the ADT network model can be described within the algebraic network coding framework introduced by Koetter and Medard. We prove that the ADT network problem can be captured by a single matrix, called the "system matrix". We show that the min-cut of an ADT network is the rank of the system matrix; thus, eliminating the need to optimize over exponential number of cuts between two nodes to compute the min-cut of an ADT network. We extend the capacity characterization for ADT networks to a more general set of connections. Our algebraic approach not only provides the Min-cut Max-flow theorem for a single unicast/multicast connection, but also extends to non-multicast connections such as multiple multicast, disjoint multicast, and two-level multicast. We also provide sufficiency conditions for achievability in ADT networks for any general connection set. In addition, we show that the random linear network coding, a randomized distributed algorithm for network code construction, achieves capacity for the connections listed above. Finally, we extend the ADT networks to those with random erasures and cycles (thus, allowing bi-directional links). Note that ADT network was proposed for approximating the wireless networks; however, ADT network is acyclic. Furthermore, ADT network does not model the stochastic nature of the wireless links. With our algebraic framework, we incorporate both cycles as well as random failures into ADT network model.
Extending Context-Sensitivity in Term Rewriting
Venue: arXiv cs.LO 2010
Year: 2010

We propose a generalized version of context-sensitivity in term rewriting based on the notion of "forbidden patterns". The basic idea is that a rewrite step should be forbidden if the redex to be contracted has a certain shape and appears in a certain context. This shape and context is expressed through forbidden patterns. In particular we analyze the relationships among this novel approach and the commonly used notion of context-sensitivity in term rewriting, as well as the feasibility of rewriting with forbidden patterns from a computational point of view. The latter feasibility is characterized by demanding that restricting a rewrite relation yields an improved termination behaviour while still being powerful enough to compute meaningful results. Sufficient criteria for both kinds of properties in certain classes of rewrite systems with forbidden patterns are presented.
Maintaining Virtual Areas on FPGAs using Strip Packing with Delays
Venue: arXiv cs.AR 2010
Year: 2010

Every year, the computing resources available on dynamically partially reconfigurable devices increase enormously. In the near future, we expect many applications to run on a single reconfigurable device. In this paper, we present a concept for multitasking on dynamically partially reconfigurable systems called virtual area management. We explain its advantages, show its challenges, and discuss possible solutions. Furthermore, we investigate one problem in more detail: Packing modules with time-varying resource requests. This problem from the reconfigurable computing field results in a completely new optimization problem not tackled before. ILP-based and heuristic approaches are compared in an experimental study and the drawbacks and benefits discussed.
On the BICM Capacity
Venue: arXiv cs.IT 2010
Year: 2010

Optimal binary labelings, input distributions, and input alphabets are analyzed for the so-called bit-interleaved coded modulation (BICM) capacity, paying special attention to the low signal-to-noise ratio (SNR) regime. For 8-ary pulse amplitude modulation (PAM) and for 0.75 bit/symbol, the folded binary code results in a higher capacity than the binary reflected gray code (BRGC) and the natural binary code (NBC). The 1 dB gap between the additive white Gaussian noise (AWGN) capacity and the BICM capacity with the BRGC can be almost completely removed if the input symbol distribution is properly selected. First-order asymptotics of the BICM capacity for arbitrary input alphabets and distributions, dimensions, mean, variance, and binary labeling are developed. These asymptotics are used to define first-order optimal (FOO) constellations for BICM, i.e. constellations that make BICM achieve the Shannon limit $-1.59 \tr{dB}$. It is shown that the $\Eb/N_0$ required for reliable transmission at asymptotically low rates in BICM can be as high as infinity, that for uniform input distributions and 8-PAM there are only 72 classes of binary labelings with a different first-order asymptotic behavior, and that this number is reduced to only 26 for 8-ary phase shift keying (PSK). A general answer to the question of FOO constellations for BICM is also given: using the Hadamard transform, it is found that for uniform input distributions, a constellation for BICM is FOO if and only if it is a linear projection of a hypercube. A constellation based on PAM or quadrature amplitude modulation input alphabets is FOO if and only if they are labeled by the NBC; if the constellation is based on PSK input alphabets instead, it can never be FOO if the input alphabet has more than four points, regardless of the labeling.
Balancing Egoism and Altruism on the Interference Channel: The MIMO case
Venue: arXiv cs.IT 2010
Year: 2010

This paper considers the so-called MIMO interference channel. This situation has relevance in applications such as multi-cell coordination in cellular networks as well as spectrum sharing in cognitive radio networks among others. We address the design of precoding (i.e. beamforming) vectors at each sender with the aim of striking a compromise between beamforming gain at the intended receiver (Egoism) and the mitigation of interference created towards other receivers (Altruism). Combining egoistic and altruistic beamforming has been shown previously to be instrumental to optimizing the rates in a MISO interference channel (i.e. where receivers have no interference canceling capability) . Here we explore these game-theoretic concepts in the more general context of MIMO channels and using the framework of Bayesian games, allowing us to derive (semi-)distributed precoding techniques. We draw parallels with existing work on the MIMO interference channel, including rate-optimizing and interference-alignement precoding techniques, showing how such techniques may be improved and re-interpretated through a common prism based on balancing egoistic and altruistic beamforming.
Deriving Ontologies from XML Schema
Venue: arXiv cs.PL 2010
Year: 2010

In this paper, we present a method and a tool for deriving a skeleton of an ontology from XML schema files. We first recall what an is ontology and its relationships with XML schemas. Next, we focus on ontology building methodology and associated tool requirements. Then, we introduce Janus, a tool for building an ontology from various XML schemas in a given domain. We summarize the main features of Janus and illustrate its functionalities through a simple example. Finally, we compare our approach to other existing ontology building tools.
Equilibria of Plurality Voting with Abstentions
Venue: arXiv cs.GT 2010
Year: 2010

In the traditional voting manipulation literature, it is assumed that a group of manipulators jointly misrepresent their preferences to get a certain candidate elected, while the remaining voters are truthful. In this paper, we depart from this assumption, and consider the setting where all voters are strategic. In this case, the election can be viewed as a game, and the election outcomes correspond to Nash equilibria of this game. We use this framework to analyze two variants of Plurality voting, namely, simultaneous voting, where all voters submit their ballots at the same time, and sequential voting, where the voters express their preferences one by one. For simultaneous voting, we characterize the preference profiles that admit a pure Nash equilibrium, but show that it is computationally hard to check if a given profile fits our criterion. For sequential voting, we provide a complete analysis of the setting with two candidates, and show that for three or more candidates the equilibria of sequential voting may behave in a counterintuitive manner.
Sparse Recovery using Smoothed $\ell^0$ (SL0): Convergence Analysis
Venue: arXiv cs.IT 2010
Year: 2010

Finding the sparse solution of an underdetermined system of linear equations has many applications, especially, it is used in Compressed Sensing (CS), Sparse Component Analysis (SCA), and sparse decomposition of signals on overcomplete dictionaries. We have recently proposed a fast algorithm, called Smoothed $\ell^0$ (SL0), for this task. Contrary to many other sparse recovery algorithms, SL0 is not based on minimizing the $\ell^1$ norm, but it tries to directly minimize the $\ell^0$ norm of the solution. The basic idea of SL0 is optimizing a sequence of certain (continuous) cost functions approximating the $\ell^0$ norm of a vector. However, in previous papers, we did not provide a complete convergence proof for SL0. In this paper, we study the convergence properties of SL0, and show that under a certain sparsity constraint in terms of Asymmetric Restricted Isometry Property (ARIP), and with a certain choice of parameters, the convergence of SL0 to the sparsest solution is guaranteed. Moreover, we study the complexity of SL0, and we show that whenever the dimension of the dictionary grows, the complexity of SL0 increases with the same order as Matching Pursuit (MP), which is one of the fastest existing sparse recovery methods, while contrary to MP, its convergence to the sparsest solution is guaranteed under certain conditions which are satisfied through the choice of parameters.
Online Stochastic Packing Applied to Display Ad Allocation
Venue: arXiv cs.DS 2010
Year: 2010

Inspired by online ad allocation, we study online stochastic packing linear programs from theoretical and practical standpoints. We first present a near-optimal online algorithm for a general class of packing linear programs which model various online resource allocation problems including online variants of routing, ad allocations, generalized assignment, and combinatorial auctions. As our main theoretical result, we prove that a simple primal-dual training-based algorithm achieves a (1 - o(1))-approximation guarantee in the random order stochastic model. This is a significant improvement over logarithmic or constant-factor approximations for the adversarial variants of the same problems (e.g. factor 1 - 1/e for online ad allocation, and \log m for online routing). We then focus on the online display ad allocation problem and study the efficiency and fairness of various training-based and online allocation algorithms on data sets collected from real-life display ad allocation system. Our experimental evaluation confirms the effectiveness of training-based primal-dual algorithms on real data sets, and also indicate an intrinsic trade-off between fairness and efficiency.
Towards Network Games with Social Preferences
Venue: arXiv cs.DC 2010
Year: 2010

Many distributed systems can be modeled as network games: a collection of selfish players that communicate in order to maximize their individual utilities. The performance of such games can be evaluated through the costs of the system equilibria: the system states in which no player can increase her utility by unilaterally changing her behavior. However, assuming that all players are selfish and in particular that all players have the same utility function may not always be appropriate. Hence, several extensions to incorporate also altruistic and malicious behavior in addition to selfishness have been proposed over the last years. In this paper, we seek to go one step further and study arbitrary relationships between participants. In particular, we introduce the notion of the social range matrix and explore the effects of the social range matrix on the equilibria in a network game. In order to derive concrete results, we propose a simplistic network creation game that captures the effect of social relationships among players.
An efficient CDMA decoder for correlated information sources
Venue: arXiv cs.IT 2010
Year: 2010

We consider the detection of correlated information sources in the ubiquitous Code-Division Multiple-Access (CDMA) scheme. We propose a message-passing based scheme for detecting correlated sources directly, with no need for source coding. The detection is done simultaneously over a block of transmitted binary symbols (word). Simulation results are provided demonstrating a substantial improvement in bit-error-rate in comparison with the unmodified detector and the alternative of source compression. The robustness of the error-performance improvement is shown under practical model settings, including wrong estimation of the generating Markov transition matrix and finite-length spreading codes.
Computing Networks: A General Framework to Contrast Neural and Swarm Cognitions
Venue: arXiv cs.NE 2010
Year: 2010

This paper presents the Computing Networks (CNs) framework. CNs are used to generalize neural and swarm architectures. Artificial neural networks, ant colony optimization, particle swarm optimization, and realistic biological models are used as examples of instantiations of CNs. The description of these architectures as CNs allows their comparison. Their differences and similarities allow the identification of properties that enable neural and swarm architectures to perform complex computations and exhibit complex cognitive abilities. In this context, the most relevant characteristics of CNs are the existence multiple dynamical and functional scales. The relationship between multiple dynamical and functional scales with adaptation, cognition (of brains and swarms) and computation is discussed.
Solving Tensor Structured Problems with Computational Tensor Algebra
Venue: arXiv cs.NA 2010
Year: 2010

Since its introduction by Gauss, Matrix Algebra has facilitated understanding of scientific problems, hiding distracting details and finding more elegant and efficient ways of computational solving. Today's largest problems, which often originate from multidimensional data, might profit from even higher levels of abstraction. We developed a framework for solving tensor structured problems with tensor algebra that unifies concepts from tensor analysis, multilinear algebra and multidimensional signal processing. In contrast to the conventional matrix approach, it allows the formulation of multidimensional problems, in a multidimensional way, preserving structure and data coherence; and the implementation of automated optimizations of solving algorithms, based on the commutativity of all tensor operations. Its ability to handle large scientific tasks is showcased by a real-world, 4D medical imaging problem, with more than 30 million unknown parameters solved on a current, inexpensive hardware. This significantly surpassed the best published matrix-based approach.
Usages et conception des TIC : Proposition d'un modèle d'aide à la représentation de problème de conception
Venue: arXiv cs.SE 2010
Year: 2010

This paper considers economic intelligence contribution to exploit individual and collective images of change, in ICT design decision-making. Technical devices meeting with real use situations often gives the opportunity to emerge mental images, that a innovation process, through its unprecedented nature, can not anticipate. Although methodologies exists for quality and design project management, the survey we conduct among small ICT publishers, show how they are not very suitable for small firms. This elements taken into account, we try to build a proposition of exploration ? analyze ? sum up process, adapted to this type of actors decisional process.
Moment-Based Analysis of Synchronization in Small-World Networks of Oscillators
Venue: arXiv cs.MA 2010
Year: 2010

In this paper, we investigate synchronization in a small-world network of coupled nonlinear oscillators. This network is constructed by introducing random shortcuts in a nearest-neighbors ring. The local stability of the synchronous state is closely related with the support of the eigenvalue distribution of the Laplacian matrix of the network. We introduce, for the first time, analytical expressions for the first three moments of the eigenvalue distribution of the Laplacian matrix as a function of the probability of shortcuts and the connectivity of the underlying nearest-neighbor coupled ring. We apply these expressions to estimate the spectral support of the Laplacian matrix in order to predict synchronization in small-world networks. We verify the efficiency of our predictions with numerical simulations.
Some considerations on how the human brain must be arranged in order to make its replication in a thinking machine possible
Venue: arXiv cs.AI 2010
Year: 2010

For the most of my life, I have earned my living as a computer vision professional busy with image processing tasks and problems. In the computer vision community there is a widespread belief that artificial vision systems faithfully replicate human vision abilities or at least very closely mimic them. It was a great surprise to me when one day I have realized that computer and human vision have next to nothing in common. The former is occupied with extensive data processing, carrying out massive pixel-based calculations, while the latter is busy with meaningful information processing, concerned with smart objects-based manipulations. And the gap between the two is insurmountable. To resolve this confusion, I had had to return and revaluate first the vision phenomenon itself, define more carefully what visual information is and how to treat it properly. In this work I have not been, as it is usually accepted, biologically inspired . On the contrary, I have drawn my inspirations from a pure mathematical theory, the Kolmogorov s complexity theory. The results of my work have been already published elsewhere. So the objective of this paper is to try and apply the insights gained in course of this my enterprise to a more general case of information processing in human brain and the challenging issue of human intelligence.
On the Generality of $1+\mathbf{i}$ as a Non-Norm Element
Venue: arXiv cs.IT 2010
Year: 2010

Full-rate space-time block codes with nonvanishing determinants have been extensively designed with cyclic division algebras. For these designs, smaller pairwise error probabilities of maximum likelihood detections require larger normalized diversity products, which can be obtained by choosing integer non-norm elements with smaller absolute values. All known methods have constructed $1+\bi$ and $2+\bi$ to be integer non-norm elements with the smallest absolute values over QAM for the number of transmit antennas $n$: $\{n:5\leq n\leq 40,8\nmid n\}$ and $\{n:5\leq n\leq 40,8\mid n\}$, respectively. Via explicit constructions, this paper proves that $1+\bi$ is an integer non-norm element with the smallest absolute value over QAM for every $n\geq 5$.
Modeling of 2D and 3D Assemblies Taking Into Account Form Errors of Plane Surfaces
Venue: arXiv cs.OH 2010
Year: 2010

The tolerancing process links the virtual and the real worlds. From the former, tolerances define a variational geometrical language (geometric parameters). From the latter, there are values limiting those parameters. The beginning of a tolerancing process is in this duality. As high precision assemblies cannot be analyzed with the assumption that form errors are negligible, we propose to apply this process to assemblies with form errors through a new way of allowing to parameterize forms and solve their assemblies. The assembly process is calculated through a method of allowing to solve the 3D assemblies of pairs of surfaces having form errors using a static equilibrium. We have built a geometrical model based on the modal shapes of the ideal surface. We compute for the completely deterministic contact points between this pair of shapes according to a given assembly process. The solution gives an accurate evaluation of the assembly performance. Then we compare the results with or without taking into account the form errors. When we analyze a batch of assemblies, the problem is to compute for the nonconformity rate of a pilot production according to the functional requirements. We input probable errors of surfaces (position, orientation, and form) in our calculus and we evaluate the quality of the results compared with the functional requirements. The pilot production then can or cannot be validated.