OpenRaiser/Intern-Atlas huggingface dataset:
Sub-optimality of Treating Interference as Noise in the Cellular Uplink
Venue: arXiv cs.IT 2011
Year: 2011

Despite the simplicity of the scheme of treating interference as noise (TIN), it was shown to be sum-capacity optimal in the Gaussian 2-user interference channel in \cite{ShangKramerChen,MotahariKhandani,AnnapureddyVeeravalli}. In this paper, an interference network consisting of a point-to-point channel interfering with a multiple access channel (MAC) is considered, with focus on the weak interference scenario. Naive TIN in this network is performed by using Gaussian codes at the transmitters, joint decoding at the MAC receiver while treating interference as noise, and single user decoding at the point-to-point receiver while treating both interferers as noise. It is shown that this naive TIN scheme is never optimal in this scenario. In fact, a scheme that combines both time division multiple access and TIN outperforms the naive TIN scheme. An upper bound on the sum-capacity of the given network is also derived.
The merit factor of binary arrays derived from the quadratic character
Venue: arXiv cs.IT 2011
Year: 2011

We calculate the asymptotic merit factor, under all cyclic rotations of rows and columns, of two families of binary two-dimensional arrays derived from the quadratic character. The arrays in these families have size p x q, where p and q are not necessarily distinct odd primes, and can be considered as two-dimensional generalisations of a Legendre sequence. The asymptotic values of the merit factor of the two families are generally different, although the maximum asymptotic merit factor, taken over all cyclic rotations of rows and columns, equals 36/13 for both families. These are the first non-trivial theoretical results for the asymptotic merit factor of families of truly two-dimensional binary arrays.
Large-Scale Music Annotation and Retrieval: Learning to Rank in Joint Semantic Spaces
Venue: arXiv cs.LG 2011
Year: 2011

Music prediction tasks range from predicting tags given a song or clip of audio, predicting the name of the artist, or predicting related songs given a song, clip, artist name or tag. That is, we are interested in every semantic relationship between the different musical concepts in our database. In realistically sized databases, the number of songs is measured in the hundreds of thousands or more, and the number of artists in the tens of thousands or more, providing a considerable challenge to standard machine learning techniques. In this work, we propose a method that scales to such datasets which attempts to capture the semantic similarities between the database items by modeling audio, artist names, and tags in a single low-dimensional semantic space. This choice of space is learnt by optimizing the set of prediction tasks of interest jointly using multi-task learning. Our method both outperforms baseline methods and, in comparison to them, is faster and consumes less memory. We then demonstrate how our method learns an interpretable model, where the semantic space captures well the similarities of interest.
Common Edge-Unzippings for Tetrahedra
Venue: arXiv cs.CG 2011
Year: 2011

It is shown that there are examples of distinct polyhedra, each with a Hamiltonian path of edges, which when cut, unfolds the surfaces to a common net. In particular, it is established for infinite classes of triples of tetrahedra.
The Gn,m Phase Transition is Not Hard for the Hamiltonian Cycle Problem
Venue: arXiv cs.AI 2011
Year: 2011

Using an improved backtrack algorithm with sophisticated pruning techniques, we revise previous observations correlating a high frequency of hard to solve Hamiltonian Cycle instances with the Gn,m phase transition between Hamiltonicity and non-Hamiltonicity. Instead all tested graphs of 100 to 1500 vertices are easily solved. When we artificially restrict the degree sequence with a bounded maximum degree, although there is some increase in difficulty, the frequency of hard graphs is still low. When we consider more regular graphs based on a generalization of knight's tours, we observe frequent instances of really hard graphs, but on these the average degree is bounded by a constant. We design a set of graphs with a feature our algorithm is unable to detect and so are very hard for our algorithm, but in these we can vary the average degree from O(1) to O(n). We have so far found no class of graphs correlated with the Gn,m phase transition which asymptotically produces a high frequency of hard instances.
AntNet: Distributed Stigmergetic Control for Communications Networks
Venue: arXiv cs.AI 2011
Year: 2011

This paper introduces AntNet, a novel approach to the adaptive learning of routing tables in communications networks. AntNet is a distributed, mobile agents based Monte Carlo system that was inspired by recent work on the ant colony metaphor for solving optimization problems. AntNet's agents concurrently explore the network and exchange collected information. The communication among the agents is indirect and asynchronous, mediated by the network itself. This form of communication is typical of social insects and is called stigmergy. We compare our algorithm with six state-of-the-art routing algorithms coming from the telecommunications and machine learning fields. The algorithms' performance is evaluated over a set of realistic testbeds. We run many experiments over real and artificial IP datagram networks with increasing number of nodes and under several paradigmatic spatial and temporal traffic distributions. Results are very encouraging. AntNet showed superior performance under all the experimental conditions with respect to its competitors. We analyze the main characteristics of the algorithm and try to explain the reasons for its superiority.
Improving Anonymity in Shared Key Primitives Based on Perfect Hash Families
Venue: arXiv cs.CR 2011
Year: 2011

We propose a new scheme for sharing symmetric key operations among a set of participants according to a (t,n) threshold access structure. We focus on anonymity properties of this scheme and show that this scheme provides improved values of anonymity measures than the existing ones. In particular, the scheme can provide optimal and equitable participant anonymity when it is based on balanced perfect hash families.
Relational Schema Protocol (RSP)
Venue: arXiv cs.DS 2011
Year: 2011

This document specifies the Relational Schema Protocol (RSP). RSP enables loosely coupled applications to share and exchange relational data. It defines fixed message format for an arbitrary relational schema so that the changes in the data schema do not affect the message format. This prevents the interacting applications from having to be reimplemented during the data schema evolvement.
Publicity of the intimate text (the blog studying and publication)
Venue: arXiv cs.OH 2011
Year: 2011

One of the important problems of a modern society - communications. At all readiness of this question both humanitarian, and engineering science, process of transfer and information reception remains in the centre of attention of researchers. The dialogue phenomenon in a network becomes the significant factor of such attention. The fact of the publication of blogs and increasing popularity of bloggers is connected, in our opinion, with an increasing openness of a blog sphere (each record can be commented any user), and accordingly, the Internet as a whole.
Regular realizability problems and models of a generalized nondeterminism
Venue: arXiv cs.FL 2011
Year: 2011

Models of a generalized nondeterminism are defined by limitations on nonde- terministic behavior of a computing device. A regular realizability problem is a problem of verifying existence of a special sort word in a regular language. These notions are closely connected. In this paper we consider regular realizability problems for languages consist- ing of all prefixes of an infinite word. These problems are related to the automata on infinite words and to the decidability of monadic second-order theories. The main contribution is a new decidability condition for regular realizability problems and for monadic-second order theories. We also show that decidability of a regular realizability problem is equivalent to decidability of some prefix realizability problem.
Probabilistic Analysis of the Network Reliability Problem on a Random Graph Ensemble
Venue: arXiv cs.IT 2011
Year: 2011

In the field of computer science, the network reliability problem for evaluating the network failure probability has been extensively investigated. For a given undirected graph $G$, the network failure probability is the probability that edge failures (i.e., edge erasures) make $G$ unconnected. Edge failures are assumed to occur independently with the same probability. The main contributions of the present paper are the upper and lower bounds on the expected network failure probability. We herein assume a simple random graph ensemble that is closely related to the Erdős-Rényi random graph ensemble. These upper and lower bounds exhibit the typical behavior of the network failure probability. The proof is based on the fact that the cut-set space of $G$ is a linear space over $\Bbb F_2$ spanned by the incident matrix of $G$. The present study shows a close relationship between the ensemble analysis of the network failure probability and the ensemble analysis of the error detection probability of LDGM codes with column weight 2.
Need to categorize: A comparative look at the categories of the Universal Decimal Classification system (UDC) and Wikipedia
Venue: arXiv cs.DL 2011
Year: 2011

This study analyzes the differences between the category structure of the Universal Decimal Classification (UDC) system (which is one of the widely used library classification systems in Europe) and Wikipedia. In particular, we compare the emerging structure of category-links to the structure of classes in the UDC. With this comparison we would like to scrutinize the question of how do knowledge maps of the same domain differ when they are created socially (i.e. Wikipedia) as opposed to when they are created formally (UDC) using classificatio theory. As a case study, we focus on the category of "Arts".
Airborne TDMA for High Throughput and Fast Weather Conditions Notification
Venue: arXiv cs.CE 2011
Year: 2011

As air traffic grows significantly, aircraft accidents increase. Many aviation accidents could be prevented if the precise aircraft positions and weather conditions on the aircraft's route were known. Existing studies propose determining the precise aircraft positions via a VHF channel with an air-to-air radio relay system that is based on mobile ad-hoc networks. However, due to the long propagation delay, the existing TDMA MAC schemes underutilize the networks. The existing TDMA MAC sends data and receives ACK in one time slot, which requires two guard times in one time slot. Since aeronautical communications spans a significant distance, the guard time occupies a significantly large portion of the slot. To solve this problem, we propose a piggybacking mechanism ACK. Our proposed MAC has one guard time in one time slot, which enables the transmission of more data. Using this additional data, we can send weather conditions that pertain to the aircraft's current position. Our analysis shows that this proposed MAC performs better than the existing MAC, since it offers better throughput and network utilization. In addition, our weather condition notification model achieves a much lower transmission delay than a HF (high frequency) voice communication.
Modulation for MIMO Networks with Several Users
Venue: arXiv cs.IT 2011
Year: 2011

In a recent work, a capacity-achieving scheme for the common-message two-user MIMO broadcast channel, based on single-stream coding and decoding, was described. This was obtained via a novel joint unitary triangularization which is applied to the corresponding channel matrices. In this work, the triangularization is generalized, to any (finite) number of matrices, allowing multi-user applications. To that end, multiple channel uses are jointly treated, in a manner reminiscent of space-time coding. As opposed to the two-user case, in the general case there does not always exist a perfect (capacity-achieving) solution. However, a nearly optimal scheme (with vanishing loss in the limit of large blocks) always exists. Common-message broadcasting is but one example of communication networks with MIMO links which can be solved using an approach coined "Network Modulation"; the extension beyond two links carries over to these problems.
A Modeling Framework for Gossip-based Information Spread
Venue: arXiv cs.DC 2011
Year: 2011

We present an analytical framework for gossip protocols based on the pairwise information exchange between interacting nodes. This framework allows for studying the impact of protocol parameters on the performance of the protocol. Previously, gossip-based information dissemination protocols have been analyzed under the assumption of perfect, lossless communication channels. We extend our framework for the analysis of networks with lossy channels. We show how the presence of message loss, coupled with specific topology configurations,impacts the expected behavior of the protocol. We validate the obtained models against simulations for two protocols.
The Perceptron with Dynamic Margin
Venue: arXiv cs.LG 2011
Year: 2011

The classical perceptron rule provides a varying upper bound on the maximum margin, namely the length of the current weight vector divided by the total number of updates up to that time. Requiring that the perceptron updates its internal state whenever the normalized margin of a pattern is found not to exceed a certain fraction of this dynamic upper bound we construct a new approximate maximum margin classifier called the perceptron with dynamic margin (PDM). We demonstrate that PDM converges in a finite number of steps and derive an upper bound on them. We also compare experimentally PDM with other perceptron-like algorithms and support vector machines on hard margin tasks involving linear kernels which are equivalent to 2-norm soft margin.
A Strictly Improved Achievable Region for Multiple Descriptions Using Combinatorial Message Sharing
Venue: arXiv cs.IT 2011
Year: 2011

We recently proposed a new coding scheme for the L-channel multiple descriptions (MD) problem for general sources and distortion measures involving `Combinatorial Message Sharing' (CMS) [7] leading to a new achievable rate-distortion region. Our objective in this paper is to establish that this coding scheme strictly subsumes the most popular region for this problem due to Venkataramani, Kramer and Goyal (VKG) [3]. In particular, we show that for a binary symmetric source under Hamming distortion measure, the CMS scheme provides a strictly larger region for all L>2. The principle of the CMS coding scheme is to include a common message in every subset of the descriptions, unlike the VKG scheme which sends a single common message in all the descriptions. In essence, we show that allowing for a common codeword in every subset of descriptions provides better freedom in coordinating the messages which can be exploited constructively to achieve points outside the VKG region.
Assisted Common Information: Further Results
Venue: arXiv cs.IT 2011
Year: 2011

We presented assisted common information as a generalization of Gács-Körner (GK) common information at ISIT 2010. The motivation for our formulation was to improve upperbounds on the efficiency of protocols for secure two-party sampling (which is a form of secure multi-party computation). Our upperbound was based on a monotonicity property of a rate-region (called the assisted residual information region) associated with the assisted common information formulation. In this note we present further results. We explore the connection of assisted common information with the Gray-Wyner system. We show that the assisted residual information region and the Gray-Wyner region are connected by a simple relationship: the assisted residual information region is the increasing hull of the Gray-Wyner region under an affine map. Several known relationships between GK common information and Gray-Wyner system fall out as consequences of this. Quantities which arise in other source coding contexts acquire new interpretations. In previous work we showed that assisted common information can be used to derive upperbounds on the rate at which a pair of parties can {\em securely sample} correlated random variables, given correlated random variables from another distribution. Here we present an example where the bound derived using assisted common information is much better than previously known bounds, and in fact is tight. This example considers correlated random variables defined in terms of standard variants of oblivious transfer, and is interesting on its own as it answers a natural question about these cryptographic primitives.
Energy efficient prediction clustering algorithm for multilevel heterogeneous wireless sensor networks
Venue: arXiv cs.NI 2011
Year: 2011

In designing wireless sensor networks, it is important to reduce energy dissipation and prolong network lifetime. In this paper, a new model with energy and monitored objects heterogeneity is proposed for heterogeneous wireless sensor networks. We put forward an energy-efficient prediction clustering algorithm, which is adaptive to the heterogeneous model. This algorithm enables the nodes to select the cluster head according to factors such as energy and communication cost, thus the nodes with higher residual energy have higher probability to become a cluster head than those with lower residual energy, so that the network energy can be dissipated uniformly. In order to reduce energy consumption when broadcasting in clustering phase and prolong network lifetime, an energy consumption prediction model is established for regular data acquisition nodes. Simulation results show that compared with current clustering algorithms, this algorithm can achieve longer sensor network lifetime, higher energy efficiency and superior network monitoring quality.
An Innovative Approach for E-Government Transformation
Venue: arXiv cs.CY 2011
Year: 2011

Despite the immeasurable investment in e-government initiatives throughout the world, such initiatives have yet to succeed in fully meeting expectations and desired outcomes. A key objective of this research article is to support the government of the UAE in realizing its vision of e-government transformation. It presents an innovative framework to support e-government implementation, which was developed from a practitioner's perspective and based on learnings from numerous e-government practices around the globe. The framework presents an approach to guide governments worldwide, and UAE in particular, to develop a top down strategy and leverage technology in order realize its long term goal of e-government transformation. The study also outlines the potential role of modern national identity schemes in enabling the transformation of traditional identities into digital identities. The work presented in this study is envisaged to help bridge the gap between policy makers and implementers, by providing greater clarity and reducing misalignment on key elements of e-government transformation. In the hands of leaders that have a strong will to invest in e-government transformation, the work presented in this study is envisaged to become a powerful tool to communicate and coordinate initiatives, and provide a clear visualization of an integrated approach to e-government transformation.
Message-Passing Estimation from Quantized Samples
Venue: arXiv cs.IT 2011
Year: 2011

Estimation of a vector from quantized linear measurements is a common problem for which simple linear techniques are suboptimal -- sometimes greatly so. This paper develops generalized approximate message passing (GAMP) algorithms for minimum mean-squared error estimation of a random vector from quantized linear measurements, notably allowing the linear expansion to be overcomplete or undercomplete and the scalar quantization to be regular or non-regular. GAMP is a recently-developed class of algorithms that uses Gaussian approximations in belief propagation and allows arbitrary separable input and output channels. Scalar quantization of measurements is incorporated into the output channel formalism, leading to the first tractable and effective method for high-dimensional estimation problems involving non-regular scalar quantization. Non-regular quantization is empirically demonstrated to greatly improve rate-distortion performance in some problems with oversampling or with undersampling combined with a sparsity-inducing prior. Under the assumption of a Gaussian measurement matrix with i.i.d. entries, the asymptotic error performance of GAMP can be accurately predicted and tracked through the state evolution formalism. We additionally use state evolution to design MSE-optimal scalar quantizers for GAMP signal reconstruction and empirically demonstrate the superior error performance of the resulting quantizers.
Evolution of Things
Venue: arXiv cs.NE 2011
Year: 2011

Evolution is one of the major omnipresent powers in the universe that has been studied for about two centuries. Recent scientific and technical developments make it possible to make the transition from passively understanding to actively mastering evolution. As of today, the only area where human experimenters can design and manipulate evolutionary processes in full is that of Evolutionary Computing, where evolutionary processes are carried out in a digital space, inside computers, in simulation. We argue that in the near future it will be possible to move evolutionary computing outside such imaginary spaces and make it physically embodied. In other words, we envision the "Evolution of Things", rather than just the evolution of code, leading to a new field of Embodied Artificial Evolution (EAE). The main objective of the present paper is to offer an umbrella term and vision in order to aid the development of this high potential research area. To this end, we introduce the notion of EAE, discuss a few examples and applications, and elaborate on the expected benefits as well as the grand challenges this developing field will have to address.
The Good Old Davis-Putnam Procedure Helps Counting Models
Venue: arXiv cs.AI 2011
Year: 2011

As was shown recently, many important AI problems require counting the number of models of propositional formulas. The problem of counting models of such formulas is, according to present knowledge, computationally intractable in a worst case. Based on the Davis-Putnam procedure, we present an algorithm, CDP, that computes the exact number of models of a propositional CNF or DNF formula F. Let m and n be the number of clauses and variables of F, respectively, and let p denote the probability that a literal l of F occurs in a clause C of F, then the average running time of CDP is shown to be O(nm^d), where d=-1/log(1-p). The practical performance of CDP has been estimated in a series of experiments on a wide variety of CNF formulas.