OpenRaiser/Intern-Atlas huggingface dataset:
Spectrum Allocation in Two-Tier Networks
Venue: arXiv cs.NI 2008
Year: 2008

Two-tier networks, comprising a conventional cellular network overlaid with shorter range hotspots (e.g. femtocells, distributed antennas, or wired relays), offer an economically viable way to improve cellular system capacity. The capacity-limiting factor in such networks is interference. The cross-tier interference between macrocells and femtocells can suffocate the capacity due to the near-far problem, so in practice hotspots should use a different frequency channel than the potentially nearby high-power macrocell users. Centralized or coordinated frequency planning, which is difficult and inefficient even in conventional cellular networks, is all but impossible in a two-tier network. This paper proposes and analyzes an optimum decentralized spectrum allocation policy for two-tier networks that employ frequency division multiple access (including OFDMA). The proposed allocation is optimal in terms of Area Spectral Efficiency (ASE), and is subjected to a sensible Quality of Service (QoS) requirement, which guarantees that both macrocell and femtocell users attain at least a prescribed data rate. Results show the dependence of this allocation on the QoS requirement, hotspot density and the co-channel interference from the macrocell and surrounding femtocells. Design interpretations of this result are provided.
A Simple Dynamic Mind-map Framework To Discover Associative Relationships in Transactional Data Streams
Venue: arXiv cs.NE 2008
Year: 2008

In this paper, we informally introduce dynamic mind-maps that represent a new approach on the basis of a dynamic construction of connectionist structures during the processing of a data stream. This allows the representation and processing of recursively defined structures and avoids the problem of a more traditional, fixed-size architecture with the processing of input structures of unknown size. For a data stream analysis with association discovery, the incremental analysis of data leads to results on demand. Here, we describe a framework that uses symbolic cells to calculate associations based on transactional data streams as it exists in e.g. bibliographic databases. We follow a natural paradigm of applying simple operations on cells yielding on a mind-map structure that adapts over time.
Linear Time Algorithm for Weak Parity Games
Venue: arXiv cs.LO 2008
Year: 2008

We consider games played on graphs with the winning conditions for the players specified as weak-parity conditions. In weak-parity conditions the winner of a play is decided by looking into the set of states appearing in the play, rather than the set of states appearing infinitely often in the play. A naive analysis of the classical algorithm for weak-parity games yields a quadratic time algorithm. We present a linear time algorithm for solving weak-parity games.
On the Spectrum of Large Random Hermitian Finite-Band Matrices
Venue: arXiv cs.IT 2008
Year: 2008

The open problem of calculating the limiting spectrum (or its Shannon transform) of increasingly large random Hermitian finite-band matrices is described. In general, these matrices include a finite number of non-zero diagonals around their main diagonal regardless of their size. Two different communication setups which may be modeled using such matrices are presented: a simple cellular uplink channel, and a time varying inter-symbol interference channel. Selected recent information-theoretic works dealing directly with such channels are reviewed. Finally, several characteristics of the still unknown limiting spectrum of such matrices are listed, and some reflections are touched upon.
NAPX: A Polynomial Time Approximation Scheme for the Noah's Ark Problem
Venue: arXiv cs.DS 2008
Year: 2008

The Noah's Ark Problem (NAP) is an NP-Hard optimization problem with relevance to ecological conservation management. It asks to maximize the phylogenetic diversity (PD) of a set of taxa given a fixed budget, where each taxon is associated with a cost of conservation and a probability of extinction. NAP has received renewed interest with the rise in availability of genetic sequence data, allowing PD to be used as a practical measure of biodiversity. However, only simplified instances of the problem, where one or more parameters are fixed as constants, have as of yet been addressed in the literature. We present NAPX, the first algorithm for the general version of NAP that returns a $1 - ε$ approximation of the optimal solution. It runs in $O(\frac{n B^2 h^2 \log^2n}{\log^2(1 - ε)})$ time where $n$ is the number of species, and $B$ is the total budget and $h$ is the height of the input tree. We also provide improved bounds for its expected running time.
A Spreadsheet Auditing Tool Evaluated in an Industrial Context
Venue: arXiv cs.HC 2008
Year: 2008

Amongst the large number of write-and-throw-away spreadsheets developed for one-time use there is a rather neglected proportion of spreadsheets that are huge, periodically used, and submitted to regular update-cycles like any conventionally evolving valuable legacy application software. However, due to the very nature of spreadsheets, their evolution is particularly tricky and therefore error-prone. In our strive to develop tools and methodologies to improve spreadsheet quality, we analysed consolidation spreadsheets of an internationally operating company for the errors they contain. The paper presents the results of the field audit, involving 78 spreadsheets with 60,446 non-empty cells. As a by-product, the study performed was also to validate our analysis tools in an industrial context. The evaluated auditing tool offers the auditor a new view on the formula structure of the spreadsheet by grouping similar formulas into equivalence classes. Our auditing approach defines three similarity criteria between formulae, namely copy, logical and structural equivalence. To improve the visualization of large spreadsheets, equivalences and data dependencies are displayed in separated windows that are interlinked with the spreadsheet. The auditing approach helps to find irregularities in the geometrical pattern of similar formulas.
(Mechanical) Reasoning on Infinite Extensive Games
Venue: arXiv cs.GT 2008
Year: 2008

In order to better understand reasoning involved in analyzing infinite games in extensive form, we performed experiments in the proof assistant Coq that are reported here.
Least change in the Determinant or Permanent of a matrix under perturbation of a single element: continuous and discrete cases
Venue: arXiv cs.DM 2008
Year: 2008

We formulate the problem of finding the probability that the determinant of a matrix undergoes the least change upon perturbation of one of its elements, provided that most or all of the elements of the matrix are chosen at random and that the randomly chosen elements have a fixed probability of being non-zero. Also, we show that the procedure for finding the probability that the determinant undergoes the least change depends on whether the random variables for the matrix elements are continuous or discrete.
Linear code-based vector quantization for independent random variables
Venue: arXiv cs.IT 2008
Year: 2008

In this paper we analyze the rate-distortion function R(D) achievable using linear codes over GF(q), where q is a prime number.
Malicious Bayesian Congestion Games
Venue: arXiv cs.GT 2008
Year: 2008

In this paper, we introduce malicious Bayesian congestion games as an extension to congestion games where players might act in a malicious way. In such a game each player has two types. Either the player is a rational player seeking to minimize her own delay, or - with a certain probability - the player is malicious in which case her only goal is to disturb the other players as much as possible. We show that such games do in general not possess a Bayesian Nash equilibrium in pure strategies (i.e. a pure Bayesian Nash equilibrium). Moreover, given a game, we show that it is NP-complete to decide whether it admits a pure Bayesian Nash equilibrium. This result even holds when resource latency functions are linear, each player is malicious with the same probability, and all strategy sets consist of singleton sets. For a slightly more restricted class of malicious Bayesian congestion games, we provide easy checkable properties that are necessary and sufficient for the existence of a pure Bayesian Nash equilibrium. In the second part of the paper we study the impact of the malicious types on the overall performance of the system (i.e. the social cost). To measure this impact, we use the Price of Malice. We provide (tight) bounds on the Price of Malice for an interesting class of malicious Bayesian congestion games. Moreover, we show that for certain congestion games the advent of malicious types can also be beneficial to the system in the sense that the social cost of the worst case equilibrium decreases. We provide a tight bound on the maximum factor by which this happens.
Green Codes: Energy-Efficient Short-Range Communication
Venue: arXiv cs.IT 2008
Year: 2008

A green code attempts to minimize the total energy per-bit required to communicate across a noisy channel. The classical information-theoretic approach neglects the energy expended in processing the data at the encoder and the decoder and only minimizes the energy required for transmissions. Since there is no cost associated with using more degrees of freedom, the traditionally optimal strategy is to communicate at rate zero. In this work, we use our recently proposed model for the power consumed by iterative message passing. Using generalized sphere-packing bounds on the decoding power, we find lower bounds on the total energy consumed in the transmissions and the decoding, allowing for freedom in the choice of the rate. We show that contrary to the classical intuition, the rate for green codes is bounded away from zero for any given error probability. In fact, as the desired bit-error probability goes to zero, the optimizing rate for our bounds converges to 1.
On the Capacity of the Diamond Half-Duplex Relay Channel
Venue: arXiv cs.IT 2008
Year: 2008

We consider a diamond-shaped dual-hop communication system consisting a source, two parallel half-duplex relays and a destination. In a single antenna configuration, it has been previously shown that a two-phase node-scheduling algorithm, along with the decode and forward strategy can achieve the capacity of the diamond channel for a certain symmetric channel gains [1]. In this paper, we obtain a more general condition for the optimality of the scheme in terms of power resources and channel gains. In particular, it is proved that if the product of the capacity of the simultaneously active links are equal in both transmission phases, the scheme achieves the capacity of the channel.
Finger Indexed Sets: New Approaches
Venue: arXiv cs.DS 2008
Year: 2008

In the particular case we have insertions/deletions at the tail of a given set S of $n$ one-dimensional elements, we present a simpler and more concrete algorithm than that presented in [Anderson, 2007] achieving the same (but also amortized) upper bound of $O(\sqrt{logd/loglogd})$ for finger searching queries, where $d$ is the number of sorted keys between the finger element and the target element we are looking for. Furthermore, in general case we have insertions/deletions anywhere we present a new randomized algorithm achieving the same expected time bounds. Even the new solutions achieve the optimal bounds in amortized or expected case, the advantage of simplicity is of great importance due to practical merits we gain.
Assessing Random Dynamical Network Architectures for Nanoelectronics
Venue: arXiv cs.AR 2008
Year: 2008

Independent of the technology, it is generally expected that future nanoscale devices will be built from vast numbers of densely arranged devices that exhibit high failure rates. Other than that, there is little consensus on what type of technology and computing architecture holds most promises to go far beyond today's top-down engineered silicon devices. Cellular automata (CA) have been proposed in the past as a possible class of architectures to the von Neumann computing architecture, which is not generally well suited for future parallel and fine-grained nanoscale electronics. While the top-down engineered semi-conducting technology favors regular and locally interconnected structures, future bottom-up self-assembled devices tend to have irregular structures because of the current lack precise control over these processes. In this paper, we will assess random dynamical networks, namely Random Boolean Networks (RBNs) and Random Threshold Networks (RTNs), as alternative computing architectures and models for future information processing devices. We will illustrate that--from a theoretical perspective--they offer superior properties over classical CA-based architectures, such as inherent robustness as the system scales up, more efficient information processing capabilities, and manufacturing benefits for bottom-up designed devices, which motivates this investigation. We will present recent results on the dynamic behavior and robustness of such random dynamical networks while also including manufacturing issues in the assessment.
Innovation in Scholarly Communication: Vision and Projects from High-Energy Physics
Venue: arXiv cs.DL 2008
Year: 2008

Having always been at the forefront of information management and open access, High-Energy Physics (HEP) proves to be an ideal test-bed for innovations in scholarly communication including new information and communication technologies. Three selected topics of scholarly communication in High-Energy Physics are presented here: A new open access business model, SCOAP3, a world-wide sponsoring consortium for peer-reviewed HEP literature; the design, development and deployment of an e-infrastructure for information management; and the emerging debate on long-term preservation, re-use and (open) access to HEP data.
Codeword-Independent Performance of Nonbinary Linear Codes Under Linear-Programming and Sum-Product Decoding
Venue: arXiv cs.IT 2008
Year: 2008

A coded modulation system is considered in which nonbinary coded symbols are mapped directly to nonbinary modulation signals. It is proved that if the modulator-channel combination satisfies a particular symmetry condition, the codeword error rate performance is independent of the transmitted codeword. It is shown that this result holds for both linear-programming decoders and sum-product decoders. In particular, this provides a natural modulation mapping for nonbinary codes mapped to PSK constellations for transmission over memoryless channels such as AWGN channels or flat fading channels with AWGN.
Performability Aspects of the Atlas Vo; Using Lmbench Suite
Venue: arXiv cs.PF 2008
Year: 2008

The ATLAS Virtual Organization is grid's largest Virtual Organization which is currently in full production stage. Hereby a case is being made that a user working within that VO is going to face a wide spectrum of different systems, whose heterogeneity is enough to count as "orders of magnitude" according to a number of metrics; including integer/float operations, memory throughput (STREAM) and communication latencies. Furthermore, the spread of performance does not appear to follow any known distribution pattern, which is demonstrated in graphs produced during May 2007 measurements. It is implied that the current practice where either "all-WNs-are-equal" or, the alternative of SPEC-based rating used by LCG/EGEE is an oversimplification which is inappropriate and expensive from an operational point of view, therefore new techniques are needed for optimal grid resources allocation.
Full Diversity Blind Signal Designs for Unique Identification of Frequency Selective Channels
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, we develop two kinds of novel closed-form decompositions on phase shift keying (PSK) constellations by exploiting linear congruence equation theory: the one for factorizing a $pq$-PSK constellation into a product of a $p$-PSK constellation and a $q$-PSK constellation, and the other for decomposing a specific complex number into a difference of a $p$-PSK constellation and a $q$-PSK constellation. With this, we propose a simple signal design technique to blindly and uniquely identify frequency selective channels with zero-padded block transmission under noise-free environments by only using the first two block received signal vectors. Furthermore, a closed-form solution to determine the transmitted signals and the channel coefficients is obtained. In the Gaussian noise and Rayleigh fading environment, we prove that the newly proposed signaling scheme enables non-coherent full diversity for the Generalized Likelihood Ratio Test (GLRT) receiver.
Cognitive Architecture for Direction of Attention Founded on Subliminal Memory Searches, Pseudorandom and Nonstop
Venue: arXiv cs.AI 2008
Year: 2008

By way of explaining how a brain works logically, human associative memory is modeled with logical and memory neurons, corresponding to standard digital circuits. The resulting cognitive architecture incorporates basic psychological elements such as short term and long term memory. Novel to the architecture are memory searches using cues chosen pseudorandomly from short term memory. Recalls alternated with sensory images, many tens per second, are analyzed subliminally as an ongoing process, to determine a direction of attention in short term memory.
Computational Representation of Linguistic Structures using Domain-Specific Languages
Venue: arXiv cs.CL 2008
Year: 2008

We describe a modular system for generating sentences from formal definitions of underlying linguistic structures using domain-specific languages. The system uses Java in general, Prolog for lexical entries and custom domain-specific languages based on Functional Grammar and Functional Discourse Grammar notation, implemented using the ANTLR parser generator. We show how linguistic and technological parts can be brought together in a natural language processing system and how domain-specific languages can be used as a tool for consistent formal notation in linguistic description.
Exploring a type-theoretic approach to accessibility constraint modelling
Venue: arXiv cs.CL 2008
Year: 2008

The type-theoretic modelling of DRT that [degroote06] proposed features continuations for the management of the context in which a clause has to be interpreted. This approach, while keeping the standard definitions of quantifier scope, translates the rules of the accessibility constraints of discourse referents inside the semantic recipes. In this paper, we deal with additional rules for these accessibility constraints. In particular in the case of discourse referents introduced by proper nouns, that negation does not block, and in the case of rhetorical relations that structure discourses. We show how this continuation-based approach applies to those accessibility constraints and how we can consider the parallel management of various principles.
A MacWilliams Identity for Convolutional Codes: The General Case
Venue: arXiv cs.IT 2008
Year: 2008

A MacWilliams Identity for convolutional codes will be established. It makes use of the weight adjacency matrices of the code and its dual, based on state space realizations (the controller canonical form) of the codes in question. The MacWilliams Identity applies to various notions of duality appearing in the literature on convolutional coding theory.
Joint Cooperation and Multi-Hopping Increase the Capacity of Wireless Networks
Venue: arXiv cs.NI 2008
Year: 2008

The problem of communication among nodes in an \emph{extended network} is considered, where radio power decay and interference are limiting factors. It has been shown previously that, with simple multi-hopping, the achievable total communication rate in such a network is at most $Θ(\sqrt{N})$. In this work, we study the benefit of node cooperation in conjunction with multi-hopping on the network capacity. We propose a multi-phase communication scheme, combining distributed MIMO transmission with multi-hop forwarding among clusters of nodes. We derive the network throughput of this communication scheme and determine the optimal cluster size. This provides a constructive lower bound on the network capacity. We first show that in \textit{regular networks} a rate of $ω(N^{2/3})$ can be achieved with transmission power scaling of $Θ(N^{\fracα{6}-{1/3}})$, where $α>2$ is the signal path-loss exponent. We further extend this result to \textit{random networks}, where we show a rate of $ω(N^{2/3}(\log{N})^{(2-α)/6})$ can be achieved with transmission power scaling of $Θ(N^{α/6-1/3}(\log{N})^{-(α-2)^2/6})$ in a random network with unit node density. In particular, as $α$ approaches 2, only constant transmission power is required. Finally, we study a random network with density $λ=Ω(\log{N})$ and show that a rate of $ω((λN)^{2/3})$ is achieved and the required power scales as $Θ(N^{α/6-1/3}/λ^{α/3-2/3})$.
Event Synchronization by Lightweight Message Passing
Venue: arXiv cs.PL 2008
Year: 2008

Concurrent ML's events and event combinators facilitate modular concurrent programming with first-class synchronization abstractions. A standard implementation of these abstractions relies on fairly complex manipulations of first-class continuations in the underlying language. In this paper, we present a lightweight implementation of these abstractions in Concurrent Haskell, a language that already provides first-order message passing. At the heart of our implementation is a new distributed synchronization protocol. In contrast with several previous translations of event abstractions in concurrent languages, we remain faithful to the standard semantics for events and event combinators; for example, we retain the symmetry of $\mathtt{choose}$ for expressing selective communication.
Peculiarities of the Correlation between Local and Global News Popularity of Electronic Mass Media
Venue: arXiv cs.IT 2008
Year: 2008

One of the approaches to the solution of the navigation problem in current information flows is ranking the documents according to their popularity level. The definition of local and global news popularity which is based on the number of similar-in-content documents, published within local and global time interval, was suggested. Mutual behavior of the documents of local and global popularity levels was studied. The algorithm of detecting the documents which received great popularity before new topics appeared was suggested.
Goal-oriented Dialog as a Collaborative Subordinated Activity involving Collective Acceptance
Venue: arXiv cs.AI 2008
Year: 2008

Modeling dialog as a collaborative activity consists notably in specifying the content of the Conversational Common Ground and the kind of social mental state involved. In previous work (Saget, 2006), we claim that Collective Acceptance is the proper social attitude for modeling Conversational Common Ground in the particular case of goal-oriented dialog. In this paper, a formalization of Collective Acceptance is shown, besides elements in order to integrate this attitude in a rational model of dialog are provided; and finally, a model of referential acts as being part of a collaborative activity is presented. The particular case of reference has been chosen in order to exemplify our claims.