OpenRaiser/Intern-Atlas huggingface dataset:
Dynamic Weighted Bit-Flipping Decoding Algorithms for LDPC Codes
Venue: arXiv cs.IT 2015
Year: 2015

Bit-flipping (BF) decoding of low-density parity-check codes is of low complexity but gives inferior performance in general. To improve performance and provide new BF decoder options for complexity-performance tradeoffs, we propose new designs for the flipping function (FF), the flipped bit selection (FBS) rule and the checksum weight updating schedule. The new FF adjusts the checksum weights in every iteration while our FBS rules take more information into account. These two modifications represent efforts to track more closely the evolutions of both check and variable nodes' reliabilities. Two selective update schedules are proposed to offer more performance and complexity tradeoffs. The combinations of the new FBS rule and known FFs result in new BF decoders with improved performance and a modest complexity increase. On the other hand, combining the new FF and FBS rule gives a new decoder with performance comparable to that of the normalized min-sum algorithm while if we use a much simpler FBS rule instead, the decoder suffers little performance loss with reduced complexity. We also present a simple decision-theoretical argument to justify the new checksum weight formula and a time-expanded factor graph model to explain the proposed selective weight-updating schedules.
A Systematic Scheme for Measuring the Performance of the Display-Camera Channel
Venue: arXiv cs.MM 2015
Year: 2015

Display-camera communication has become a promising direction in both computer vision and wireless communication communities. However, the consistency of the channel measurement is an open issue since precise calibration of the experimental setting has not been fully studied in the literatures. This paper focuses on establishing a scheme for precise calibration of the display-camera channel performance. To guarantee high consistency of the experiment, we propose an accurate measurement scheme for the geometric parameters, and identify some unstable channel factors, e.g., Moire effect, rolling shutter effect, blocking artifacts, inconsistency in auto-focus, trembling and vibration. In the experiment, we first define the consistency criteria according to the error-prone region in bit error rate (BER) plots of the channel measurements. It is demonstrated that the consistency of the experimental result can be improved by the proposed precise calibration scheme.
Critical Database Size for Effective Caching
Venue: arXiv cs.IT 2015
Year: 2015

Replicating or caching popular content in memories distributed across the network is a technique to reduce peak network loads. Conventionally, the performance gain of caching was thought to result from making part of the requested data available closer to end users. Recently, it has been shown that by using a carefully designed technique to store the contents in the cache and coding across data streams a much more significant gain can be achieved in reducing the network load. Inner and outer bounds on the network load v/s cache memory tradeoff were obtained in (Maddah-Ali and Niesen, 2012). We give an improved outer bound on the network load v/s cache memory tradeoff. We address the question of to what extent caching is effective in reducing the server load when the number of files becomes large as compared to the number of users. We show that the effectiveness of caching become small when the number of files becomes comparable to the square of the number of users.
Belief Hierarchical Clustering
Venue: arXiv cs.AI 2015
Year: 2015

In the data mining field many clustering methods have been proposed, yet standard versions do not take into account uncertain databases. This paper deals with a new approach to cluster uncertain data by using a hierarchical clustering defined within the belief function framework. The main objective of the belief hierarchical clustering is to allow an object to belong to one or several clusters. To each belonging, a degree of belief is associated, and clusters are combined based on the pignistic properties. Experiments with real uncertain data show that our proposed method can be considered as a propitious tool.
On Vulnerabilities of the Security Association in the IEEE 802.15.6 Standard
Venue: arXiv cs.CR 2015
Year: 2015

Wireless Body Area Networks (WBAN) support a variety of real-time health monitoring and consumer electronics applications. The latest international standard for WBAN is the IEEE 802.15.6. The security association in this standard includes four elliptic curve-based key agreement protocols that are used for generating a master key. In this paper, we challenge the security of the IEEE 802.15.6 standard by showing vulnerabilities of those four protocols to several attacks. We perform a security analysis on the protocols, and show that they all have security problems, and are vulnerable to different attacks.
Energy Harvesting Small Cell Networks: Feasibility, Deployment and Operation
Venue: arXiv cs.IT 2015
Year: 2015

Small cell networks (SCNs) have attracted great attention in recent years due to their potential to meet the exponential growth of mobile data traffic and the increasing demand for better quality of service and user experience in mobile applications. Nevertheless, a wide deployment of SCNs has not happened yet because of the complexity in the network planning and optimization, as well as the high expenditure involved in deployment and operation. In particular, it is difficult to provide grid power supply to all the small cell base stations (SCBSs) in a cost effective way. Moreover, a dense deployment of SCBSs, which is needed to meet the capacity and coverage of the next generation wireless networks, will increase operators' electricity bills and lead to significant carbon emission. Thus, it is crucial to exploit off-grid and green energy sources to power SCNs, for which energy harvesting (EH) technology is a viable solution. In this article, we will conduct a comprehensive study of EH-SCNs, and investigate important aspects, including the feasibility analysis, network deployment, and network operation issues. The advantages, as well as unique challenges, of EH-SCNs will be highlighted, together with potential solutions and effective design methodologies.
Texture Retrieval via the Scattering Transform
Venue: arXiv cs.IR 2015
Year: 2015

This work studies the problem of content-based image retrieval, specifically, texture retrieval. It focuses on feature extraction and similarity measure for texture images. Our approach employs a recently developed method, the so-called Scattering transform, for the process of feature extraction in texture retrieval. It shares a distinctive property of providing a robust representation, which is stable with respect to spatial deformations. Recent work has demonstrated its capability for texture classification, and hence as a promising candidate for the problem of texture retrieval. Moreover, we adopt a common approach of measuring the similarity of textures by comparing the subband histograms of a filterbank transform. To this end we derive a similarity measure based on the popular Bhattacharyya Kernel. Despite the popularity of describing histograms using parametrized probability density functions, such as the Generalized Gaussian Distribution, it is unfortunately not applicable for describing most of the Scattering transform subbands, due to the complex modulus performed on each one of them. In this work, we propose to use the Weibull distribution to model the Scattering subbands of descendant layers. Our numerical experiments demonstrated the effectiveness of the proposed approach, in comparison with several state of the arts.
Evaluation of Pervasive Games: Recruitment of Qualified Participants through Preparatory Game Phases
Venue: arXiv cs.HC 2015
Year: 2015

In this paper we present the evaluation process for Barbarossa, a pervasive role playing game. Barbarossa involves an invitational (preparatory) and a main execution phase. The former is freely available though Google Play store and may be played anytime/ anywhere. The latter defines three inter-dependent player roles acted by players who need to collaborate in a treasure hunting game. The eligibility of players for participating in the main game phase is restricted among those ranked relatively high in the invitational phase. Herein, we investigate the impact of the invitational game mode on the players overall game experience. The main hypothesis tested is that game awareness (gained from participating in a preliminary game phase) may serve as a means for recruiting the most suitable subjects for user trials on pervasive game research prototypes.
Closing the Gap -- Formally Verifying Dynamically Typed Programs like Statically Typed Ones Using Hoare Logic -- Extended Version --
Venue: arXiv cs.PL 2015
Year: 2015

Dynamically typed object-oriented languages enable programmers to write elegant, reusable and extensible programs. However, with the current methodology for program verification, the absence of static type information creates significant overhead. Our proposal is two-fold: First, we propose a layer of abstraction hiding the complexity of dynamic typing when provided with sufficient type information. Since this essentially creates the illusion of verifying a statically-typed program, the effort required is equivalent to the statically-typed case. Second, we show how the required type information can be efficiently derived for all type-safe programs by integrating a type inference algorithm into Hoare logic, yielding a semi-automatic procedure allowing the user to focus on those typing problems really requiring his attention. While applying type inference to dynamically typed programs is a well-established method by now, our approach complements conventional soft typing systems by offering formal proof as a third option besides modifying the program (static typing) and accepting the presence of runtime type errors (dynamic typing).
Max-Cost Discrete Function Evaluation Problem under a Budget
Venue: arXiv cs.LG 2015
Year: 2015

We propose novel methods for max-cost Discrete Function Evaluation Problem (DFEP) under budget constraints. We are motivated by applications such as clinical diagnosis where a patient is subjected to a sequence of (possibly expensive) tests before a decision is made. Our goal is to develop strategies for minimizing max-costs. The problem is known to be NP hard and greedy methods based on specialized impurity functions have been proposed. We develop a broad class of \emph{admissible} impurity functions that admit monomials, classes of polynomials, and hinge-loss functions that allow for flexible impurity design with provably optimal approximation bounds. This flexibility is important for datasets when max-cost can be overly sensitive to "outliers." Outliers bias max-cost to a few examples that require a large number of tests for classification. We design admissible functions that allow for accuracy-cost trade-off and result in $O(\log n)$ guarantees of the optimal cost among trees with corresponding classification accuracy levels.
Topological properties on the diameters of the integer simplex
Venue: arXiv cs.DM 2015
Year: 2015

Wide diameter $d_ω(G)$ and fault-diameter $D_ω(G)$ of an interconnection network $G$ have been recently studied by many authors. We determine the wide diameter and fault-diameter of the integer simplex $T_m^n$. Note that $d_1(T_m^n)=D_1(T_m^n)= d(T_m^n)$, where $d(T_m^n)$ is the diameter of $T_m^n$. We prove that $d_ω(T_m^n)=D_ω(T_m^n)= d(T_m^n)+1$ when $2\leqω\leq n$. Since a triangular pyramid $TP_L$ is $T_L^3$, we have $d_ω(TP_L)=D_ω(TP_L)= d(TP_L)+1$ when $2\leqω\leq 3$.
Applications of Repeated Games in Wireless Networks: A Survey
Venue: arXiv cs.GT 2015
Year: 2015

A repeated game is an effective tool to model interactions and conflicts for players aiming to achieve their objectives in a long-term basis. Contrary to static noncooperative games that model an interaction among players in only one period, in repeated games, interactions of players repeat for multiple periods; and thus the players become aware of other players' past behaviors and their future benefits, and will adapt their behavior accordingly. In wireless networks, conflicts among wireless nodes can lead to selfish behaviors, resulting in poor network performances and detrimental individual payoffs. In this paper, we survey the applications of repeated games in different wireless networks. The main goal is to demonstrate the use of repeated games to encourage wireless nodes to cooperate, thereby improving network performances and avoiding network disruption due to selfish behaviors. Furthermore, various problems in wireless networks and variations of repeated game models together with the corresponding solutions are discussed in this survey. Finally, we outline some open issues and future research directions.
Trajectory Aware Macro-cell Planning for Mobile Users
Venue: arXiv cs.NI 2015
Year: 2015

We design and evaluate algorithms for efficient user-mobility driven macro-cell planning in cellular networks. As cellular networks embrace heterogeneous technologies (including long range 3G/4G and short range WiFi, Femto-cells, etc.), most traffic generated by static users gets absorbed by the short-range technologies, thereby increasingly leaving mobile user traffic to macro-cells. To this end, we consider a novel approach that factors in the trajectories of mobile users as well as the impact of city geographies and their associated road networks for macro-cell planning. Given a budget k of base-stations that can be upgraded, our approach selects a deployment that impacts the most number of user trajectories. The generic formulation incorporates the notion of quality of service of a user trajectory as a parameter to allow different application-specific requirements, and operator choices.We show that the proposed trajectory utility maximization problem is NP-hard, and design multiple heuristics. We evaluate our algorithms with real and synthetic data sets emulating different city geographies to demonstrate their efficacy. For instance, with an upgrade budget k of 20%, our algorithms perform 3-8 times better in improving the user quality of service on trajectories in different city geographies when compared to greedy location-based base-station upgrades.
Low Complexity Transceiver Design for GFDM
Venue: arXiv cs.IT 2015
Year: 2015

Due to its attractive properties, generalized frequency division multiplexing (GFDM) is recently being discussed as a candidate waveform for the fifth generation of wireless communication systems (5G). GFDM is introduced as a generalized form of the widely used orthogonal frequency division multiplexing (OFDM) modulation scheme and since it uses only one cyclic prefix (CP) for a group of symbols rather than a CP per symbol, it is more bandwidth efficient than OFDM. In this paper, we propose novel transceiver structures for GFDM by taking advantage of the particular structure in the modulation matrix. Our proposed transmitter is based on modulation matrix sparsification through application of fast Fourier transform (FFT) to reduce the implementation complexity. A unified receiver structure for matched filter (MF), zero forcing (ZF) and minimum mean square error (MMSE) receivers is also derived. The proposed receiver techniques harness the special block circulant property of the matrices involved in the demodulation stage to reduce the computational cost of the system implementation. We have derived the closed forms for the ZF and MMSE receiver filters. Additionally, our algorithms do not incur any performance loss as they maintain the optimal performance. The computational costs of our proposed techniques are analyzed in detail and are compared with the existing solutions that are known to have the lowest complexity. It is shown that through application of our transceiver structure a substantial amount of computational complexity reduction can be achieved.
D2D-based V2V Communications with Latency and Reliability Constraints
Venue: arXiv cs.IT 2015
Year: 2015

Direct device-to-device (D2D) communication has been proposed as a possible enabler for vehicle-to-vehicle (V2V) applications, where the incurred intra-cell interference and the stringent latency and reliability requirements are challenging issues. In this paper, we investigate the radio resource management problem for D2D-based V2V communications. Firstly, we analyze and mathematically model the actual requirements for vehicular communications and traditional cellular links. Secondly, we propose a problem formulation to fulfill these requirements, and then a Separate Resource Block allocation and Power control (SRBP) algorithm to solve this problem. Finally, simulations are presented to illustrate the improved performance of the proposed SRBP scheme compared to some other existing methods.
On Lipschitz Bijections between Boolean Functions
Venue: arXiv cs.DM 2015
Year: 2015

For two functions $f,g:\{0,1\}^n\to\{0,1\}$ a mapping $ψ:\{0,1\}^n\to\{0,1\}^n$ is said to be a $\textit{mapping from $f$ to $g$}$ if it is a bijection and $f(z)=g(ψ(z))$ for every $z\in\{0,1\}^n$. In this paper we study Lipschitz mappings between boolean functions. Our first result gives a construction of a $C$-Lipschitz mapping from the ${\sf Majority}$ function to the ${\sf Dictator}$ function for some universal constant $C$. On the other hand, there is no $n/2$-Lipschitz mapping in the other direction, namely from the ${\sf Dictator}$ function to the ${\sf Majority}$ function. This answers an open problem posed by Daniel Varga in the paper of Benjamini et al. (FOCS 2014). We also show a mapping from ${\sf Dictator}$ to ${\sf XOR}$ that is 3-local, 2-Lipschitz, and its inverse is $O(\log(n))$-Lipschitz, where by $L$-local mapping we mean that each of its output bits depends on at most $L$ input bits. Next, we consider the problem of finding functions such that any mapping between them must have large \emph{average stretch}, where the average stretch of a mapping $ϕ$ is defined as ${\sf avgStretch}(ϕ) = {\mathbb E}_{x,i}[dist(ϕ(x),ϕ(x+e_i)]$. We show that any mapping $ϕ$ from ${\sf XOR}$ to ${\sf Majority}$ must satisfy ${\sf avgStretch}(ϕ) \geq Ω(\sqrt{n})$. In some sense, this gives a "function analogue" to the question of Benjamini et al. (FOCS 2014), who asked whether there exists a set $A \subset \{0,1\}^n$ of density 0.5 such that any bijection from $\{0,1\}^{n-1}$ to $A$ has large average stretch. Finally, we show that for a random balanced function $f:\{0,1\}^n\to\{0,1\}^n$ with high probability there is a mapping $ϕ$ from ${\sf Dictator}$ to $f$ such that both $ϕ$ and $ϕ^{-1}$ have constant average stretch. In particular, this implies that one cannot obtain lower bounds on average stretch by taking uniformly random functions.
Secure and trustworthy file sharing over cloud storage using eID tokens
Venue: arXiv cs.CR 2015
Year: 2015

This paper presents a multi-platform, open-source application that aims to protect data stored and shared in existing cloud storage services. The access to the cryptographic material used to protect data is implemented using the identification and authentication functionalities of national electronic identity (eID) tokens. All peer to peer dialogs to exchange cryptographic material is implemented using the cloud storage facilities. Furthermore, we have included a set of mechanisms to prevent files from being permanently lost or damaged due to concurrent modification, deletion and malicious tampering. We have implemented a prototype in Java that is agnostic relatively to cloud storage providers; it only manages local folders, one of them being the local image of a cloud folder. We have successfully tested our prototype in Windows, Mac OS X and Linux, with Dropbox, OneDrive, Google Drive and SugarSync.
The cavity method for analysis of large-scale penalized regression
Venue: arXiv cs.IT 2015
Year: 2015

Penalized regression methods aim to retrieve reliable predictors among a large set of putative ones from a limited amount of measurements. In particular, penalized regression with singular penalty functions is important for sparse reconstruction algorithms. For large-scale problems, these algorithms exhibit sharp phase transition boundaries where sparse retrieval breaks down. Large optimization problems associated with sparse reconstruction have been analyzed in the literature by setting up corresponding statistical mechanical models at a finite temperature. Using replica method for mean field approximation, and subsequently taking a zero temperature limit, this approach reproduces the algorithmic phase transition boundaries. Unfortunately, the replica trick and the non-trivial zero temperature limit obscure the underlying reasons for the failure of a sparse reconstruction algorithm, and of penalized regression methods, in general. In this paper, we employ the ``cavity method'' to give an alternative derivation of the mean field equations, working directly in the zero-temperature limit. This derivation provides insight into the origin of the different terms in the self-consistency conditions. The cavity method naturally involves a quantity, the average local susceptibility, whose behavior distinguishes different phases in this system. This susceptibility can be generalized for analysis of a broader class of sparse reconstruction algorithms.
Tighter Estimates for epsilon-nets for Disks
Venue: arXiv cs.CG 2015
Year: 2015

The geometric hitting set problem is one of the basic geometric combinatorial optimization problems: given a set $P$ of points, and a set $\mathcal{D}$ of geometric objects in the plane, the goal is to compute a small-sized subset of $P$ that hits all objects in $\mathcal{D}$. In 1994, Bronniman and Goodrich made an important connection of this problem to the size of fundamental combinatorial structures called $ε$-nets, showing that small-sized $ε$-nets imply approximation algorithms with correspondingly small approximation ratios. Very recently, Agarwal and Pan showed that their scheme can be implemented in near-linear time for disks in the plane. Altogether this gives $O(1)$-factor approximation algorithms in $\tilde{O}(n)$ time for hitting sets for disks in the plane. This constant factor depends on the sizes of $ε$-nets for disks; unfortunately, the current state-of-the-art bounds are large -- at least $24/ε$ and most likely larger than $40/ε$. Thus the approximation factor of the Agarwal and Pan algorithm ends up being more than $40$. The best lower-bound is $2/ε$, which follows from the Pach-Woeginger construction for halfspaces in two dimensions. Thus there is a large gap between the best-known upper and lower bounds. Besides being of independent interest, finding precise bounds is important since this immediately implies an improved linear-time algorithm for the hitting-set problem. The main goal of this paper is to improve the upper-bound to $13.4/ε$ for disks in the plane. The proof is constructive, giving a simple algorithm that uses only Delaunay triangulations. We have implemented the algorithm, which is available as a public open-source module. Experimental results show that the sizes of $ε$-nets for a variety of data-sets is lower, around $9/ε$.
Progress, Fairness and Justness in Process Algebra
Venue: arXiv cs.LO 2015
Year: 2015

To prove liveness properties of concurrent systems, it is often necessary to postulate progress, fairness and justness properties. This paper investigates how the necessary progress, fairness and justness assumptions can be added to or incorporated in a standard process-algebraic specification formalism. We propose a formalisation that can be applied to a wide range of process algebras. The presented formalism is used to reason about route discovery and packet delivery in the setting of wireless networks.