OpenRaiser/Intern-Atlas huggingface dataset:
Designing and Implementing Future Aerial Communication Networks
Venue: arXiv cs.NI 2016
Year: 2016

Providing "connectivity from the sky" is the new innovative trend in wireless communications. High and low altitude platforms, drones, aircrafts and airships are being considered as the candidates for deploying wireless communications complementing the terrestrial communication infrastructure. In this article, we report the detailed account of the design and implementation challenges of an aerial network consisting of LTE Advanced (LTE-A) base stations. In particular, we review achievements and innovations harnessed by an aerial network composed of Helikite platforms. Helikites can be raised in the sky to bring Internet access during special events and in the aftermath of an emergency. The trial phase of the system mounting LTE-A technology onboard Helikites to serve users on the ground showed not only to be very encouraging but that such a system could offer even a longer lasting solution provided that inefficiency in powering the radio frequency equipment in the Helikite can be overcome.
Secret Sharing Homomorphism and Secure E-voting
Venue: arXiv cs.CR 2016
Year: 2016

Secure E-voting is a challenging protocol. Several approaches based on homomorphic crypto systems, mix-nets blind signatures are proposed in the literature .But most of them need complicated homomorphic encryption which involves complicated encryption decryption process and key management which is not efficient. In this paper we propose a secure and efficient E-voting scheme based on secret sharing homomorphism. Here E-voting is viewed as special case of multi party computation where several voters jointly compute the result without revealing his vote. Secret sharing schemes are good alternative for secure multi party computation and are computationally efficient and secure compared with the cryptographic techniques. It is the first proposal, which makes use of the additive homomorphic property of the Shamir secret sharing scheme and the encoding decoding of votes to obtain the individual votes obtained by each candidate apart from the election result. We have achieved integrity and privacy while keeping the efficiency of the system.
Language recognition power and succintness of affine automata
Venue: arXiv cs.FL 2016
Year: 2016

In this work we study a non-linear generalization based on affine transformations of probabilistic and quantum automata proposed recently by Díaz-Caro and Yakaryılmaz \cite{DCY16A} referred as affine automata. First, we present efficient simulations of probabilistic and quantum automata by means of affine automata which allows us to characterize the class of exclusive stochastic languages. Then, we initiate a study on the succintness of affine automata. In particular, we show that an infinite family of unary regular languages can be recognized by 2-state affine automata but the state numbers of quantum and probabilistic automata cannot be bounded. Finally, we present the characterization of all (regular) unary languages recognized by two-state affine automata.
Distributed Strong Diameter Network Decomposition
Venue: arXiv cs.DS 2016
Year: 2016

For a pair of positive parameters $D,χ$, a partition ${\cal P}$ of the vertex set $V$ of an $n$-vertex graph $G = (V,E)$ into disjoint clusters of diameter at most $D$ each is called a $(D,χ)$ network decomposition, if the supergraph ${\cal G}({\cal P})$, obtained by contracting each of the clusters of ${\cal P}$, can be properly $χ$-colored. The decomposition ${\cal P}$ is said to be strong (resp., weak) if each of the clusters has strong (resp., weak) diameter at most $D$, i.e., if for every cluster $C \in {\cal P}$ and every two vertices $u,v \in C$, the distance between them in the induced graph $G(C)$ of $C$ (resp., in $G$) is at most $D$. Network decomposition is a powerful construct, very useful in distributed computing and beyond. It was shown by Awerbuch \etal \cite{AGLP89} and Panconesi and Srinivasan \cite{PS92}, that strong $(2^{O(\sqrt{\log n})},2^{O(\sqrt{\log n})})$ network decompositions can be computed in $2^{O(\sqrt{\log n})}$ distributed time. Linial and Saks \cite{LS93} devised an ingenious randomized algorithm that constructs {\em weak} $(O(\log n),O(\log n))$ network decompositions in $O(\log^2 n)$ time. It was however open till now if {\em strong} network decompositions with both parameters $2^{o(\sqrt{\log n})}$ can be constructed in distributed $2^{o(\sqrt{\log n})}$ time. In this paper we answer this long-standing open question in the affirmative, and show that strong $(O(\log n),O(\log n))$ network decompositions can be computed in $O(\log^2 n)$ time. We also present a tradeoff between parameters of our network decomposition. Our work is inspired by and relies on the "shifted shortest path approach", due to Blelloch \etal \cite{BGKMPT11}, and Miller \etal \cite{MPX13}. These authors developed this approach for PRAM algorithms for padded partitions. We adapt their approach to network decompositions in the distributed model of computation.
Performance Analysis of Project-and-Forward Relaying in Mixed MIMO-Pinhole and Rayleigh Dual-Hop Channel
Venue: arXiv cs.IT 2016
Year: 2016

In this letter, we present an end-to-end performance analysis of dual-hop project-and-forward relaying in a realistic scenario, where the source-relay and the relay-destination links are experiencing MIMO-pinhole and Rayleigh channel conditions, respectively. We derive the probability density function of both the relay post-processing and the end-to-end signal-to-noise ratios, and the obtained expressions are used to derive the outage probability of the analyzed system as well as its end-to-end ergodic capacity in terms of generalized functions. Applying then the residue theory to Mellin-Barnes integrals, we infer the system asymptotic behavior for different channel parameters. As the bivariate Meijer-G function is involved in the analysis, we propose a new and fast MATLAB implementation enabling an automated definition of the complex integration contour. Extensive Monte-Carlo simulations are invoked to corroborate the analytical results.
A High-Quality Speech and Audio Codec With Less Than 10 ms Delay
Venue: arXiv cs.SD 2016
Year: 2016

With increasing quality requirements for multimedia communications, audio codecs must maintain both high quality and low delay. Typically, audio codecs offer either low delay or high quality, but rarely both. We propose a codec that simultaneously addresses both these requirements, with a delay of only 8.7 ms at 44.1 kHz. It uses gain-shape algebraic vector quantisation in the frequency domain with time-domain pitch prediction. We demonstrate that the proposed codec operating at 48 kbit/s and 64 kbit/s out-performs both G.722.1C and MP3 and has quality comparable to AAC-LD, despite having less than one fourth of the algorithmic delay of these codecs.
Compact Flow Diagrams for State Sequences
Venue: arXiv cs.DS 2016
Year: 2016

We introduce the concept of compactly representing a large number of state sequences, e.g., sequences of activities, as a flow diagram. We argue that the flow diagram representation gives an intuitive summary that allows the user to detect patterns among large sets of state sequences. Simplified, our aim is to generate a small flow diagram that models the flow of states of all the state sequences given as input. For a small number of state sequences we present efficient algorithms to compute a minimal flow diagram. For a large number of state sequences we show that it is unlikely that efficient algorithms exist. More specifically, the problem is W[1]-hard if the number of state sequences is taken as a parameter. We thus introduce several heuristics for this problem. We argue about the usefulness of the flow diagram by applying the algorithms to two problems in sports analysis. We evaluate the performance of our algorithms on a football data set and generated data.
When the Filter Bubble Bursts: Collective Evaluation Dynamics in Online Communities
Venue: arXiv cs.SI 2016
Year: 2016

We analyze online collective evaluation processes through positive and negative votes in various social media. We find two modes of collective evaluations that stem from the existence of filter bubbles. Above a threshold of collective attention, negativity grows faster with positivity, as a sign of the burst of a filter bubble when information reaches beyond the local social context of a user. We analyze how collectively evaluated content can reach large social contexts and create polarization, showing that emotions expressed through text play a key role in collective evaluation processes.
Massive Multiple Access Based on Superposition Raptor Codes for M2M Communications
Venue: arXiv cs.IT 2016
Year: 2016

Machine-to-machine (M2M) wireless systems aim to provide ubiquitous connectivity between machine type communication (MTC) devices without any human intervention. Given the exponential growth of MTC traffic, it is of utmost importance to ensure that future wireless standards are capable of handling this traffic. In this paper, we focus on the design of a very efficient massive access strategy for highly dense cellular networks with M2M communications. Several MTC devices are allowed to simultaneously transmit at the same resource block by incorporating Raptor codes and superposition modulation. This significantly reduces the access delay and improves the achievable system throughput. A simple yet efficient random access strategy is proposed to only detect the selected preambles and the number of devices which have chosen them. No device identification is needed in the random access phase which significantly reduces the signalling overhead. The proposed scheme is analyzed and the maximum number of MTC devices that can be supported in a resource block is characterized as a function of the message length, number of available resources, and the number of preambles. Simulation results show that the proposed scheme can effectively support a massive number of MTC devices for a limited number of available resources, when the message size is small.
Adaptive Least Mean Squares Estimation of Graph Signals
Venue: arXiv cs.LG 2016
Year: 2016

The aim of this paper is to propose a least mean squares (LMS) strategy for adaptive estimation of signals defined over graphs. Assuming the graph signal to be band-limited, over a known bandwidth, the method enables reconstruction, with guaranteed performance in terms of mean-square error, and tracking from a limited number of observations over a subset of vertices. A detailed mean square analysis provides the performance of the proposed method, and leads to several insights for designing useful sampling strategies for graph signals. Numerical results validate our theoretical findings, and illustrate the performance of the proposed method. Furthermore, to cope with the case where the bandwidth is not known beforehand, we propose a method that performs a sparse online estimation of the signal support in the (graph) frequency domain, which enables online adaptation of the graph sampling strategy. Finally, we apply the proposed method to build the power spatial density cartography of a given operational region in a cognitive network environment.
Channel Covariance Estimation in Massive MIMO Frequency Division Duplex Systems
Venue: arXiv cs.IT 2016
Year: 2016

Channel covariance is emerging as a critical ingredient of the acquisition of instantaneous channel state information (CSI) in multi-user Massive MIMO systems operating in frequency division duplex (FDD) mode. In this context, channel reciprocity does not hold, and it is generally expected that covariance information about the downlink channel must be estimated and fed back by the user equipment (UE). As an alternative CSI acquisition technique, we propose to infer the downlink covariance based on the observed uplink covariance. This inference process relies on a dictionary of uplink/downlink covariance matrices, and on interpolation in the corresponding Riemannian space; once the dictionary is known, the estimation does not rely on any form of feedback from the UE. In this article, we present several variants of the interpolation method, and benchmark them through simulations.
Tight Hardness Results for Maximum Weight Rectangles
Venue: arXiv cs.DS 2016
Year: 2016

Given $n$ weighted points (positive or negative) in $d$ dimensions, what is the axis-aligned box which maximizes the total weight of the points it contains? The best known algorithm for this problem is based on a reduction to a related problem, the Weighted Depth problem [T. M. Chan, FOCS'13], and runs in time $O(n^d)$. It was conjectured [Barbay et al., CCCG'13] that this runtime is tight up to subpolynomial factors. We answer this conjecture affirmatively by providing a matching conditional lower bound. We also provide conditional lower bounds for the special case when points are arranged in a grid (a well studied problem known as Maximum Subarray problem) as well as for other related problems. All our lower bounds are based on assumptions that the best known algorithms for the All-Pairs Shortest Paths problem (APSP) and for the Max-Weight k-Clique problem in edge-weighted graphs are essentially optimal.
TwoPaCo: An efficient algorithm to build the compacted de Bruijn graph from many complete genomes
Venue: arXiv cs.DS 2016
Year: 2016

Motivation: De Bruijn graphs have been proposed as a data structure to facilitate the analysis of related whole genome sequences, in both a population and comparative genomic settings. However, current approaches do not scale well to many genomes of large size (such as mammalian genomes). Results: In this paper, we present TwoPaCo, a simple and scalable low memory algorithm for the direct construction of the compacted de Bruijn graph from a set of complete genomes. We demonstrate that it can construct the graph for 100 simulated human genomes in less then a day and eight real primates in less than two hours, on a typical shared-memory machine. We believe that this progress will enable novel biological analyses of hundreds of mammalian-sized genomes. Availability: Our code and data is available for download from github.com/medvedevgroup/TwoPaCo Contact: ium125@psu.edu
Plücker Correction Problem: Analysis and Improvements in Efficiency
Venue: arXiv cs.CV 2016
Year: 2016

A given six dimensional vector represents a 3D straight line in Plucker coordinates if its coordinates satisfy the Klein quadric constraint. In many problems aiming to find the Plucker coordinates of lines, noise in the data and other type of errors contribute for obtaining 6D vectors that do not correspond to lines, because of that constraint. A common procedure to overcome this drawback is to find the Plucker coordinates of the lines that are closest to those vectors. This is known as the Plucker correction problem. In this article we propose a simple, closed-form, and global solution for this problem. When compared with the state-of-the-art method, one can conclude that our algorithm is easier and requires much less operations than previous techniques (it does not require Singular Value Decomposition techniques).
On a Class of Almost Difference Sets Constructed by Using the Ding-Helleseth-Martinsens Constructions
Venue: arXiv cs.CR 2016
Year: 2016

Pseudorandom binary sequences with optimal balance and autocorrelation have many applications in stream cipher, communication, coding theory, etc. It is known that binary sequences with three-level autocorrelation should have an almost difference set as their characteristic sets. How to construct new families of almost difference set is an important research topic in such fields as communication, coding theory and cryptography. In a work of Ding, Helleseth, and Martinsen in 2001, the authors developed a new method, known as the Ding-Helleseth-Martinsens Constructions in literature, of constructing an almost difference set from product sets of GF(2) and the union of two cyclotomic classes of order four. In the present paper, we have constructed two classes of almost difference set with product sets between GF(2) and union sets of the cyclotomic classes of order 12 using that method. In addition, we could find there do not exist the Ding-Helleseth-Martinsens Constructions for the cyclotomic classes of order six and eight.
Programmable Packet Scheduling
Venue: arXiv cs.NI 2016
Year: 2016

Switches today provide a small set of scheduling algorithms. While we can tweak scheduling parameters, we cannot modify algorithmic logic, or add a completely new algorithm, after the switch has been designed. This paper presents a design for a programmable packet scheduler, which allows scheduling algorithms---potentially algorithms that are unknown today---to be programmed into a switch without requiring hardware redesign. Our design builds on the observation that scheduling algorithms make two decisions: in what order to schedule packets and when to schedule them. Further, in many scheduling algorithms these decisions can be made when packets are enqueued. We leverage this observation to build a programmable scheduler using a single abstraction: the push-in first-out queue (PIFO), a priority queue that maintains the scheduling order and time for such algorithms. We show that a programmable scheduler using PIFOs lets us program a wide variety of scheduling algorithms. We present a detailed hardware design for this scheduler for a 64-port 10 Gbit/s shared-memory switch with <4% chip area overhead on a 16-nm standard-cell library. Our design lets us program many sophisticated algorithms, such as a 5-level hierarchical scheduler with programmable scheduling algorithms at each level.
Tribes Is Hard in the Message Passing Model
Venue: arXiv cs.CC 2016
Year: 2016

We consider the point-to-point message passing model of communication in which there are $k$ processors with individual private inputs, each $n$-bit long. Each processor is located at the node of an underlying undirected graph and has access to private random coins. An edge of the graph is a private channel of communication between its endpoints. The processors have to compute a given function of all their inputs by communicating along these channels. While this model has been widely used in distributed computing, strong lower bounds on the amount of communication needed to compute simple functions have just begun to appear. In this work, we prove a tight lower bound of $Ω(kn)$ on the communication needed for computing the Tribes function, when the underlying graph is a star of $k+1$ nodes that has $k$ leaves with inputs and a center with no input. Lower bound on this topology easily implies comparable bounds for others. Our lower bounds are obtained by building upon the recent information theoretic techniques of Braverman et.al (FOCS'13) and combining it with the earlier work of Jayram, Kumar and Sivakumar (STOC'03). This approach yields information complexity bounds that is of independent interest.
Optimal Low-Complexity Self-Interference Cancellation for Full-Duplex MIMO Small Cells
Venue: arXiv cs.IT 2016
Year: 2016

Self-interference (SI) significantly limits the performance of full-duplex (FD) radio devices if not properly cancelled. State-of-the-art SI cancellation (SIC) techniques at the receive chain implicitly set an upper bound on the transmit power of the device. This paper starts from this observation and proposes a transmit beamforming design for FD multiple-antenna radios that: i) leverages the inherent SIC capabilities at the receiver and the channel state information; and ii) exploits the potential of multiple antennas in terms of spatial SIC. The proposed solution not only maximizes the throughput while complying with the SIC requirements of the FD device, but also enjoys a very low complexity that allows it to outperform state-of-the-art counterparts in terms of processing time and power requirements. Numerical results show that our transmit beamforming design achieves significant gains with respect to applying zero-forcing to the SI channel when the number of transmit antennas is small to moderate, which makes it particularly appealing for FD small-cell base stations.
Big Data Meets Telcos: A Proactive Caching Perspective
Venue: arXiv cs.IT 2016
Year: 2016

Mobile cellular networks are becoming increasingly complex to manage while classical deployment/optimization techniques and current solutions (i.e., cell densification, acquiring more spectrum, etc.) are cost-ineffective and thus seen as stopgaps. This calls for development of novel approaches that leverage recent advances in storage/memory, context-awareness, edge/cloud computing, and falls into framework of big data. However, the big data by itself is yet another complex phenomena to handle and comes with its notorious 4V: velocity, voracity, volume and variety. In this work, we address these issues in optimization of 5G wireless networks via the notion of proactive caching at the base stations. In particular, we investigate the gains of proactive caching in terms of backhaul offloadings and request satisfactions, while tackling the large-amount of available data for content popularity estimation. In order to estimate the content popularity, we first collect users' mobile traffic data from a Turkish telecom operator from several base stations in hours of time interval. Then, an analysis is carried out locally on a big data platform and the gains of proactive caching at the base stations are investigated via numerical simulations. It turns out that several gains are possible depending on the level of available information and storage size. For instance, with 10% of content ratings and 15.4 Gbyte of storage size (87% of total catalog size), proactive caching achieves 100% of request satisfaction and offloads 98% of the backhaul when considering 16 base stations.
Communication Cost in Parallel Query Processing
Venue: arXiv cs.DB 2016
Year: 2016

We study the problem of computing conjunctive queries over large databases on parallel architectures without shared storage. Using the structure of such a query $q$ and the skew in the data, we study tradeoffs between the number of processors, the number of rounds of communication, and the per-processor load -- the number of bits each processor can send or can receive in a single round -- that are required to compute $q$. When the data is free of skew, we obtain essentially tight upper and lower bounds for one round algorithms and we show how the bounds degrade when there is skew in the data. In the case of skewed data, we show how to improve the algorithms when approximate degrees of the heavy-hitter elements are available, obtaining essentially optimal algorithms for queries such as simple joins and triangle join queries. For queries that we identify as tree-like, we also prove nearly matching upper and lower bounds for multi-round algorithms for a natural class of skew-free databases. One consequence of these latter lower bounds is that for any $\varepsilon>0$, using $p$ processors to compute the connected components of a graph, or to output the path, if any, between a specified pair of vertices of a graph with $m$ edges and per-processor load that is $O(m/p^{1-\varepsilon})$ requires $Ω(\log p)$ rounds of communication. Our upper bounds are given by simple structured algorithms using MapReduce. Our one-round lower bounds are proved in a very general model, which we call the Massively Parallel Communication (MPC) model, that allows processors to communicate arbitrary bits. Our multi-round lower bounds apply in a restricted version of the MPC model in which processors in subsequent rounds after the first communication round are only allowed to send tuples.