OpenRaiser/Intern-Atlas huggingface dataset:
Technical Rate of Substitution of Spectrum in Future Mobile Broadband Provisioning
Venue: arXiv cs.NI 2015
Year: 2015

Dense deployment of base stations (BSs) and multi-antenna techniques are considered key enablers for future mobile networks. Meanwhile, spectrum sharing techniques and utilization of higher frequency bands make more bandwidth available. An important question for future system design is which element is more effective than others. In this paper, we introduce the concept of technical rate of substitution (TRS) from microeconomics and study the TRS of spectrum in terms of BS density and antenna number per BS. Numerical results show that TRS becomes higher with increasing user data rate requirement, suggesting that spectrum is the most effective means of provisioning extremely fast mobile broadband.
Two-dimensional Decoding Algorithms and Recording Techniques for Bit Patterned Media Feasibility Demonstrations
Venue: arXiv cs.IT 2015
Year: 2015

Recording experiments and decoding algorithms are presented for evaluating the bit-error-rate of state-of-the-art magnetic bitpatterned media. The recording experiments are performed with a static tester and conventional hard-disk-drive heads. As the reader dimensions are larger than the bit dimensions in both the down-track and the cross-track directions, a two-dimensional bit decoding algorithm is required. Two such algorithms are presented in details together with the methodology implemented to accurately retrieve island positions during recording. Using these techniques, a 1.6 Td/in$^2$ magnetic bit pattern media is demonstrated to support 2D bit error rates below 1e-2 under shingled magnetic recording conditions.
Energy Efficiency and Sum Rate Tradeoffs for Massive MIMO Systems with Underlaid Device-to-Device Communications
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we investigate the coexistence of two technologies that have been put forward for the fifth generation (5G) of cellular networks, namely, network-assisted device-to-device (D2D) communications and massive MIMO (multiple-input multiple-output). Potential benefits of both technologies are known individually, but the tradeoffs resulting from their coexistence have not been adequately addressed. To this end, we assume that D2D users reuse the downlink resources of cellular networks in an underlay fashion. In addition, multiple antennas at the BS are used in order to obtain precoding gains and simultaneously support multiple cellular users using multiuser or massive MIMO technique. Two metrics are considered, namely the average sum rate (ASR) and energy efficiency (EE). We derive tractable and directly computable expressions and study the tradeoffs between the ASR and EE as functions of the number of BS antennas, the number of cellular users and the density of D2D users within a given coverage area. Our results show that both the ASR and EE behave differently in scenarios with low and high density of D2D users, and that coexistence of underlay D2D communications and massive MIMO is mainly beneficial in low densities of D2D users.
On Slepian--Wolf Theorem with Interaction
Venue: arXiv cs.CC 2015
Year: 2015

In this paper we study interactive "one-shot" analogues of the classical Slepian-Wolf theorem. Alice receives a value of a random variable $X$, Bob receives a value of another random variable $Y$ that is jointly distributed with $X$. Alice's goal is to transmit $X$ to Bob (with some error probability $\varepsilon$). Instead of one-way transmission, which is studied in the classical coding theory, we allow them to interact. They may also use shared randomness. We show, that Alice can transmit $X$ to Bob in expected $H(X|Y) + 2\sqrt{H(X|Y)} + O(\log_2\left(\frac{1}{\varepsilon}\right))$ number of bits. Moreover, we show that every one-round protocol $π$ with information complexity $I$ can be compressed to the (many-round) protocol with expected communication about $I + 2\sqrt{I}$ bits. This improves a result by Braverman and Rao \cite{braverman2011information}, where they had $5\sqrt{I}$. Further, we show how to solve this problem (transmitting $X$) using $3H(X|Y) + O(\log_2\left(\frac{1}{\varepsilon}\right))$ bits and $4$ rounds on average. This improves a result of~\cite{brody2013towards}, where they had $4H(X|Y) + O(\log1/\varepsilon)$ bits and 10 rounds on average. In the end of the paper we discuss how many bits Alice and Bob may need to communicate on average besides $H(X|Y)$. The main question is whether the upper bounds mentioned above are tight. We provide an example of $(X, Y)$, such that transmission of $X$ from Alice to Bob with error probability $\varepsilon$ requires $H(X|Y) + Ω\left(\log_2\left(\frac{1}{\varepsilon}\right)\right)$ bits on average.
Characterisation of Strongly Stable Matchings
Venue: arXiv cs.DS 2015
Year: 2015

An instance of a strongly stable matching problem (SSMP) is an undirected bipartite graph $G=(A \cup B, E)$, with an adjacency list of each vertex being a linearly ordered list of ties, which are subsets of vertices equally good for a given vertex. Ties are disjoint and may contain one vertex. A matching $M$ is a set of vertex-disjoint edges. An edge $(x,y) \in E \setminus M$ is a {\em blocking edge} for $M$ if $x$ is either unmatched or strictly prefers $y$ to its current partner in $M$, and $y$ is either unmatched or strictly prefers $x$ to its current partner in $M$ or is indifferent between them. A matching is {\em strongly stable} if there is no blocking edge with respect to it. We present an algorithm for the generation of all strongly stable matchings, thus solving an open problem already stated in the book by Gusfield and Irving \cite{GI}. It has previously been shown that strongly stable matchings form a distributive lattice and although the number of strongly stable matchings can be exponential in the number of vertices, we show that there exists a partial order with $O(m)$ elements representing all strongly stable matchings, where $m$ denotes the number of edges in the graph. We give two algorithms that construct two such representations: one in $O(nm^2)$ time and the other in $O(nm)$ time, where $n$ denotes the number of vertices in the graph. Note that the construction of the second representation has the same time complexity as that of computing a single strongly stable matching.
Multi-Version Coding - An Information Theoretic Perspective of Consistent Distributed Storage
Venue: arXiv cs.IT 2015
Year: 2015

In applications of distributed storage systems to distributed computing and implementation of key- value stores, the following property, usually referred to as consistency in computer science and engineering, is an important requirement: as the data stored changes, the latest version of the data must be accessible to a client that connects to the storage system. An information theoretic formulation called multi-version coding is introduced in the paper, in order to study storage costs of consistent distributed storage systems. Multi-version coding is characterized by ν totally ordered versions of a message, and a storage system with n servers. At each server, values corresponding to an arbitrary subset of the ν versions are received and encoded. For any subset of c servers in the storage system, the value corresponding to the latest common version, or a later version as per the total ordering, among the c servers is required to be decodable. An achievable multi-version code construction via linear coding and a converse result that shows that the construction is approximately tight, are provided. An implication of the converse is that there is an inevitable price, in terms of storage cost, to ensure consistency in distributed storage systems.
Quantifying Creativity in Art Networks
Venue: arXiv cs.AI 2015
Year: 2015

Can we develop a computer algorithm that assesses the creativity of a painting given its context within art history? This paper proposes a novel computational framework for assessing the creativity of creative products, such as paintings, sculptures, poetry, etc. We use the most common definition of creativity, which emphasizes the originality of the product and its influential value. The proposed computational framework is based on constructing a network between creative products and using this network to infer about the originality and influence of its nodes. Through a series of transformations, we construct a Creativity Implication Network. We show that inference about creativity in this network reduces to a variant of network centrality problems which can be solved efficiently. We apply the proposed framework to the task of quantifying creativity of paintings (and sculptures). We experimented on two datasets with over 62K paintings to illustrate the behavior of the proposed framework. We also propose a methodology for quantitatively validating the results of the proposed algorithm, which we call the "time machine experiment".
Rumor Spreading with Bounded In-Degree
Venue: arXiv cs.DC 2015
Year: 2015

In the classic gossip-based model of communication for disseminating information in a network, in each time unit, every node $u$ is allowed to contact a single random neighbor $v$. If $u$ knows the data (rumor) to be disseminated, it disperses it to $v$ (known as PUSH) and if it does not, it requests it from $v$ (known as PULL). While in the classic gossip model, each node is only allowed to contact a single neighbor in each time unit, each node can possibly be contacted by many neighboring nodes. In the present paper, we consider a restricted model where at each node only one incoming request can be served. As long as only a single piece of information needs to be disseminated, this does not make a difference for push requests. It however has a significant effect on pull requests. In the paper, we therefore concentrate on this weaker pull version, which we call 'restricted pull'. We distinguish two versions of the restricted pull protocol depending on whether the request to be served among a set of pull requests at a given node is chosen adversarially or uniformly at random. As a first result, we prove an exponential separation between the two variants. We show that there are instances where if an adversary picks the request to be served, the restricted pull protocol requires a polynomial number of rounds whereas if the winning request is chosen uniformly at random, the restricted pull protocol only requires a polylogarithmic number of rounds to inform the whole network. Further, as the main technical contribution, we show that if the request to be served is chosen randomly, the slowdown of using restricted pull versus using the classic pull protocol can w.h.p. be upper bounded by $O(Δ/ δ\log n)$, where $Δ$ and $δ$ are the largest and smallest degree of the network.
The Degree of Squares is an Atom (Extended Version)
Venue: arXiv cs.FL 2015
Year: 2015

We answer an open question in the theory of degrees of infinite sequences with respect to transducibility by finite-state transducers. An initial study of this partial order of degrees was carried out in (Endrullis, Hendriks, Klop, 2011), but many basic questions remain unanswered. One of the central questions concerns the existence of atom degrees, other than the degree of the `identity sequence' 1 0^0 1 0^1 1 0^2 1 0^3 .... A degree is called an `atom' if below it there is only the bottom degree 0, which consists of the ultimately periodic sequences. We show that also the degree of the `squares sequence' 1 0^0 1 0^1 1 0^4 1 0^9 1 0^{16} ... is an atom. As the main tool for this result we characterise the transducts of `spiralling' sequences and their degrees. We use this to show that every transduct of a `polynomial sequence' either is in 0 or can be transduced back to a polynomial sequence for a polynomial of the same order.
Compressive Sensing with Prior Support Quality Information and Application to Massive MIMO Channel Estimation with Temporal Correlation
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we consider the problem of compressive sensing (CS) recovery with a prior support and the prior support quality information available. Different from classical works which exploit prior support blindly, we shall propose novel CS recovery algorithms to exploit the prior support adaptively based on the quality information. We analyze the distortion bound of the recovered signal from the proposed algorithm and we show that a better quality prior support can lead to better CS recovery performance. We also show that the proposed algorithm would converge in $\mathcal{O}\left(\log\mbox{SNR}\right)$ steps. To tolerate possible model mismatch, we further propose some robustness designs to combat incorrect prior support quality information. Finally, we apply the proposed framework to sparse channel estimation in massive MIMO systems with temporal correlation to further reduce the required pilot training overhead.
Facial Expressions Tracking and Recognition: Database Protocols for Systems Validation and Evaluation
Venue: arXiv cs.CV 2015
Year: 2015

Each human face is unique. It has its own shape, topology, and distinguishing features. As such, developing and testing facial tracking systems are challenging tasks. The existing face recognition and tracking algorithms in Computer Vision mainly specify concrete situations according to particular goals and applications, requiring validation methodologies with data that fits their purposes. However, a database that covers all possible variations of external and factors does not exist, increasing researchers' work in acquiring their own data or compiling groups of databases. To address this shortcoming, we propose a methodology for facial data acquisition through definition of fundamental variables, such as subject characteristics, acquisition hardware, and performance parameters. Following this methodology, we also propose two protocols that allow the capturing of facial behaviors under uncontrolled and real-life situations. As validation, we executed both protocols which lead to creation of two sample databases: FdMiee (Facial database with Multi input, expressions, and environments) and FACIA (Facial Multimodal database driven by emotional induced acting). Using different types of hardware, FdMiee captures facial information under environmental and facial behaviors variations. FACIA is an extension of FdMiee introducing a pipeline to acquire additional facial behaviors and speech using an emotion-acting method. Therefore, this work eases the creation of adaptable database according to algorithm's requirements and applications, leading to simplified validation and testing processes.
Finding Intermediary Topics Between People of Opposing Views: A Case Study
Venue: arXiv cs.SI 2015
Year: 2015

In micro-blogging platforms, people can connect with others and have conversations on a wide variety of topics. However, because of homophily and selective exposure, users tend to connect with like-minded people and only read agreeable information. Motivated by this scenario, in this paper we study the diversity of intermediary topics, which are latent topics estimated from user generated content. These topics can be used as features in recommender systems aimed at introducing people of diverse political viewpoints. We conducted a case study on Twitter, considering the debate about a sensitive issue in Chile, where we quantified homophilic behavior in terms of political discussion and then we evaluated the diversity of intermediary topics in terms of political stances of users.
Can network coding bridge the digital divide in the Pacific?
Venue: arXiv cs.IT 2015
Year: 2015

Conventional TCP performance is significantly impaired under long latency and/or constrained bandwidth. While small Pacific Island states on satellite links experience this in the extreme, small populations and remoteness often rule out submarine fibre connections and their communities struggle to reap the benefits of the Internet. Network-coded TCP (TCP/NC) can increase goodput under high latency and packet loss, but has not been used to tunnel conventional TCP and UDP across satellite links before. We report on a feasibility study aimed at determining expected goodput gain across such TCP/NC tunnels into island targets on geostationary and medium earth orbit satellite links.
Energy-Efficient Future Wireless Networks: A Marriage between Massive MIMO and Small Cells
Venue: arXiv cs.IT 2015
Year: 2015

How would a cellular network designed for high energy efficiency look like? To answer this fundamental question, we model cellular networks using stochastic geometry and optimize the energy efficiency with respect to the density of base stations, the number of antennas and users per cell, the transmit power levels, and the pilot reuse. The highest efficiency is neither achieved by a pure small-cell approach, nor by a pure massive MIMO solution. Interestingly, it is the combination of these approaches that provides the highest energy efficiency; small cells contributes by reducing the propagation losses while massive MIMO enables multiplexing of users with controlled interference.
Homogeneous Spiking Neuromorphic System for Real-World Pattern Recognition
Venue: arXiv cs.NE 2015
Year: 2015

A neuromorphic chip that combines CMOS analog spiking neurons and memristive synapses offers a promising solution to brain-inspired computing, as it can provide massive neural network parallelism and density. Previous hybrid analog CMOS-memristor approaches required extensive CMOS circuitry for training, and thus eliminated most of the density advantages gained by the adoption of memristor synapses. Further, they used different waveforms for pre and post-synaptic spikes that added undesirable circuit overhead. Here we describe a hardware architecture that can feature a large number of memristor synapses to learn real-world patterns. We present a versatile CMOS neuron that combines integrate-and-fire behavior, drives passive memristors and implements competitive learning in a compact circuit module, and enables in-situ plasticity in the memristor synapses. We demonstrate handwritten-digits recognition using the proposed architecture using transistor-level circuit simulations. As the described neuromorphic architecture is homogeneous, it realizes a fundamental building block for large-scale energy-efficient brain-inspired silicon chips that could lead to next-generation cognitive computing.
The two-unicast problem
Venue: arXiv cs.IT 2015
Year: 2015

We consider the communication capacity of wireline networks for a two-unicast traffic pattern. The network has two sources and two destinations with each source communicating a message to its own destination, subject to the capacity constraints on the directed edges of the network. We propose a simple outer bound for the problem that we call the Generalized Network Sharing (GNS) bound. We show this bound is the tightest edge-cut bound for two-unicast networks and is tight in several bottleneck cases, though it is not tight in general. We also show that the problem of computing the GNS bound is NP-complete. Finally, we show that despite its seeming simplicity, the two-unicast problem is as hard as the most general network coding problem. As a consequence, linear coding is insufficient to achieve capacity for general two-unicast networks, and non-Shannon inequalities are necessary for characterizing capacity of general two-unicast networks.
Open-Source Simulators for Cloud Computing: Comparative Study and Challenging Issues
Venue: arXiv cs.DC 2015
Year: 2015

Resource scheduling in infrastructure as a service (IaaS) is one of the keys for large-scale Cloud applications. Extensive research on all issues in real environment is extremely difficult because it requires developers to consider network infrastructure and the environment, which may be beyond the control. In addition, the network conditions cannot be controlled or predicted. Performance evaluations of workload models and Cloud provisioning algorithms in a repeatable manner under different configurations are difficult. Therefore, simulators are developed. To understand and apply better the state-of-the-art of cloud computing simulators, and to improve them, we study four known open-source simulators. They are compared in terms of architecture, modeling elements, simulation process, performance metrics and scalability in performance. Finally, a few challenging issues as future research trends are outlined.
On the "Naturalness" of Buggy Code
Venue: arXiv cs.SE 2015
Year: 2015

Real software, the kind working programmers produce by the kLOC to solve real-world problems, tends to be "natural", like speech or natural language; it tends to be highly repetitive and predictable. Researchers have captured this naturalness of software through statistical models and used them to good effect in suggestion engines, porting tools, coding standards checkers, and idiom miners. This suggests that code that appears improbable, or surprising, to a good statistical language model is "unnatural" in some sense, and thus possibly suspicious. In this paper, we investigate this hypothesis. We consider a large corpus of bug fix commits (ca.~8,296), from 10 different Java projects, and we focus on its language statistics, evaluating the naturalness of buggy code and the corresponding fixes. We find that code with bugs tends to be more entropic (i.e., unnatural), becoming less so as bugs are fixed. Focusing on highly entropic lines is similar in cost-effectiveness to some well-known static bug finders (PMD, FindBugs) and ordering warnings from these bug finders using an entropy measure improves the cost-effectiveness of inspecting code implicated in warnings. This suggests that entropy may be a valid language-independent and simple way to complement the effectiveness of PMD or FindBugs, and that search-based bug-fixing methods may benefit from using entropy both for fault-localization and searching for fixes.
Color Image Retrieval Using Fuzzy Measure Hamming and S-Tree
Venue: arXiv cs.CV 2015
Year: 2015

This chapter approaches the image retrieval system on the base of the colors of image. It creates fuzzy signature to describe the color of image on color space HSV and builds fuzzy Hamming distance (FHD) to evaluate the similarity between the images. In order to reduce the storage space and speed up the search of similar images, it aims to create S-tree to store fuzzy signature relies on FHD and builds image retrieval algorithm on S-tree. Then, it provides the content-based image retrieval (CBIR) and an image retrieval method on FHD and S-tree. Last but not least, based on this theory, it also presents an application and experimental assessment of the process of querying similar image on the database system over 10,000 images.
A Hybrid Model for Enhancing Lexical Statistical Machine Translation (SMT)
Venue: arXiv cs.CL 2015
Year: 2015

The interest in statistical machine translation systems increases currently due to political and social events in the world. A proposed Statistical Machine Translation (SMT) based model that can be used to translate a sentence from the source Language (English) to the target language (Arabic) automatically through efficiently incorporating different statistical and Natural Language Processing (NLP) models such as language model, alignment model, phrase based model, reordering model, and translation model. These models are combined to enhance the performance of statistical machine translation (SMT). Many implementation tools have been used in this work such as Moses, Gizaa++, IRSTLM, KenLM, and BLEU. Based on the implementation, evaluation of this model, and comparing the generated translation with other implemented machine translation systems like Google Translate, it was proved that this proposed model has enhanced the results of the statistical machine translation, and forms a reliable and efficient model in this field of research.