OpenRaiser/Intern-Atlas huggingface dataset:
Exact Inference of Hidden Structure from Sample Data in Noisy-OR Networks
Venue: arXiv cs.AI 2013
Year: 2013

In the literature on graphical models, there has been increased attention paid to the problems of learning hidden structure (see Heckerman [H96] for survey) and causal mechanisms from sample data [H96, P88, S93, P95, F98]. In most settings we should expect the former to be difficult, and the latter potentially impossible without experimental intervention. In this work, we examine some restricted settings in which perfectly reconstruct the hidden structure solely on the basis of observed sample data.
Learning From What You Don't Observe
Venue: arXiv cs.AI 2013
Year: 2013

The process of diagnosis involves learning about the state of a system from various observations of symptoms or findings about the system. Sophisticated Bayesian (and other) algorithms have been developed to revise and maintain beliefs about the system as observations are made. Nonetheless, diagnostic models have tended to ignore some common sense reasoning exploited by human diagnosticians; In particular, one can learn from which observations have not been made, in the spirit of conversational implicature. There are two concepts that we describe to extract information from the observations not made. First, some symptoms, if present, are more likely to be reported before others. Second, most human diagnosticians and expert systems are economical in their data-gathering, searching first where they are more likely to find symptoms present. Thus, there is a desirable bias toward reporting symptoms that are present. We develop a simple model for these concepts that can significantly improve diagnostic inference.
Empirical Evaluation of Approximation Algorithms for Probabilistic Decoding
Venue: arXiv cs.AI 2013
Year: 2013

It was recently shown that the problem of decoding messages transmitted through a noisy channel can be formulated as a belief updating task over a probabilistic network [McEliece]. Moreover, it was observed that iterative application of the (linear time) Pearl's belief propagation algorithm designed for polytrees outperformed state of the art decoding algorithms, even though the corresponding networks may have many cycles. This paper demonstrates empirically that an approximation algorithm approx-mpe for solving the most probable explanation (MPE) problem, developed within the recently proposed mini-bucket elimination framework [Dechter96], outperforms iterative belief propagation on classes of coding networks that have bounded induced width. Our experiments suggest that approximate MPE decoders can be good competitors to the approximate belief updating decoders.
Technical Report: A Receding Horizon Algorithm for Informative Path Planning with Temporal Logic Constraints
Venue: arXiv cs.RO 2013
Year: 2013

This technical report is an extended version of the paper 'A Receding Horizon Algorithm for Informative Path Planning with Temporal Logic Constraints' accepted to the 2013 IEEE International Conference on Robotics and Automation (ICRA). This paper considers the problem of finding the most informative path for a sensing robot under temporal logic constraints, a richer set of constraints than have previously been considered in information gathering. An algorithm for informative path planning is presented that leverages tools from information theory and formal control synthesis, and is proven to give a path that satisfies the given temporal logic constraints. The algorithm uses a receding horizon approach in order to provide a reactive, on-line solution while mitigating computational complexity. Statistics compiled from multiple simulation studies indicate that this algorithm performs better than a baseline exhaustive search approach.
On the Construction and Decoding of Concatenated Polar Codes
Venue: arXiv cs.IT 2013
Year: 2013

A scheme for concatenating the recently invented polar codes with interleaved block codes is considered. By concatenating binary polar codes with interleaved Reed-Solomon codes, we prove that the proposed concatenation scheme captures the capacity-achieving property of polar codes, while having a significantly better error-decay rate. We show that for any $ε> 0$, and total frame length $N$, the parameters of the scheme can be set such that the frame error probability is less than $2^{-N^{1-ε}}$, while the scheme is still capacity achieving. This improves upon $2^{-N^{0.5-\eps}}$, the frame error probability of Arikan's polar codes. We also propose decoding algorithms for concatenated polar codes, which significantly improve the error-rate performance at finite block lengths while preserving the low decoding complexity.
A Fully Distributed Opportunistic Network Coding Scheme for Cellular Relay Networks
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we propose an opportunistic network coding (ONC) scheme in cellular relay networks, which operates depending on whether the relay decodes source messages successfully or not. A fully distributed method is presented to implement the proposed opportunistic network coding scheme without the need of any feedback between two network nodes. We consider the use of proposed ONC for cellular downlink transmissions and derive its closed-form outage probability expression considering cochannel interference in a Rayleigh fading environment. Numerical results show that the proposed ONC scheme outperforms the traditional non-cooperation in terms of outage probability. We also develop the diversity-multiplexing tradeoff (DMT) of proposed ONC and show that the ONC scheme obtains the full diversity and an increased multiplexing gain as compared with the conventional cooperation protocols.
Energy Efficiency of Network Cooperation for Cellular Uplink Transmissions
Venue: arXiv cs.IT 2013
Year: 2013

There is a growing interest in energy efficient or so-called "green" wireless communication to reduce the energy consumption in cellular networks. Since today's wireless terminals are typically equipped with multiple network access interfaces such as Bluetooth, Wi-Fi, and cellular networks, this paper investigates user terminals cooperating with each other in transmitting their data packets to a base station (BS) by exploiting the multiple network access interfaces, referred to as inter-network cooperation, to improve the energy efficiency in cellular uplink transmission. Given target outage probability and data rate requirements, we develop a closed-form expression of energy efficiency in Bits-per-Joule for the inter-network cooperation by taking into account the path loss, fading, and thermal noise effects. Numerical results show that when the cooperating users move towards to each other, the proposed inter-network cooperation significantly improves the energy efficiency as compared with the traditional non-cooperation and intra-network cooperation. This implies that given a certain amount of bits to be transmitted, the inter-network cooperation requires less energy than the traditional non-cooperation and intra-network cooperation, showing the energy saving benefit of inter-network cooperation.
Content Based Traffic Engineering in Software Defined Information Centric Networks
Venue: arXiv cs.NI 2013
Year: 2013

This paper describes a content centric network architecture which uses software defined networking principles to implement efficient metadata driven services by extracting content metadata at the network layer. The ability to access content metadata transparently enables a number of new services in the network. Specific examples discussed here include: a metadata driven traffic engineering scheme which uses prior knowledge of content length to optimize content delivery, a metadata driven content firewall which is more resilient than traditional firewalls and differentiated treatment of content based on the type of content being accessed. A detailed outline of an implementation of the proposed architecture is presented along with some basic evaluation.
Homology Groups of Pipeline Petri Nets
Venue: arXiv cs.LO 2013
Year: 2013

We study homology groups of elementary Petri nets for the pipeline systems. We show that the integral homology groups of these nets in dimensions 0 and 1 equal the group of integers, and they are zero in other dimensions. We prove that directed homology groups of elementary Petri nets are zero in all dimensions.
An Experiment on Parallel Model Checking of a CTL Fragment
Venue: arXiv cs.LO 2013
Year: 2013

We propose a parallel algorithm for local, on the fly, model checking of a fragment of CTL that is well-suited for modern, multi-core architectures. This model-checking algorithm takes bene t from a parallel state space construction algorithm, which we described in a previous work, and shares the same basic set of principles: there are no assumptions on the models that can be analyzed; no restrictions on the way states are distributed; and no restrictions on the way work is shared among processors. We evaluate the performance of diff erent versions of our algorithm and compare our results with those obtained using other parallel model checking tools. One of the most novel contributions of this work is to study a space-e fficient variant for CTL model-checking that does not require to store the whole transition graph but that operates on a reverse spanning tree.
Exact algorithms for dominating induced matchings
Venue: arXiv cs.DM 2013
Year: 2013

Say that an edge of a graph G dominates itself and every other edge adjacent to it. An edge dominating set of a graph G = (V,E) is a subset of edges E' of E which dominates all edges of G. In particular, if every edge of G is dominated by exactly one edge of E' then E' is a dominating induced matching. It is known that not every graph admits a dominating induced matching, while the problem to decide if it does admit is NP-complete. In this paper we consider the problem of finding a minimum weighted dominating induced matching, if any, of a graph with weighted edges. We describe two exact algorithms for general graphs. The algorithms are efficient in the cases where G admits a known vertex dominating set of small size, or when G contains a polynomial number of maximal independent sets.
Efficient Partial Order CDCL Using Assertion Level Choice Heuristics
Venue: arXiv cs.AI 2013
Year: 2013

We previously designed Partial Order Conflict Driven Clause Learning (PO-CDCL), a variation of the satisfiability solving CDCL algorithm with a partial order on decision levels, and showed that it can speed up the solving on problems with a high independence between decision levels. In this paper, we more thoroughly analyze the reasons of the efficiency of PO-CDCL. Of particular importance is that the partial order introduces several candidates for the assertion level. By evaluating different heuristics for this choice, we show that the assertion level selection has an important impact on solving and that a carefully designed heuristic can significantly improve performances on relevant benchmarks.
Adaptive Control of Scalar Plants in the Presence of Unmodeled Dynamics
Venue: arXiv cs.SY 2013
Year: 2013

Robust adaptive control of scalar plants in the presence of unmodeled dynamics is established in this paper. It is shown that implementation of a projection algorithm with standard adaptive control of a scalar plant ensures global boundedness of the overall adaptive system for a class of unmodeled dynamics.
Universal Wyner-Ziv Coding for Distortion Constrained General Side-Information
Venue: arXiv cs.IT 2013
Year: 2013

We investigate the Wyner-Ziv coding in which the statistics of the principal source is known but the statistics of the channel generating the side-information is unknown except that it is in a certain class. The class consists of channels such that the distortion between the principal source and the side-information is smaller than a threshold, but channels may be neither stationary nor ergodic. In this situation, we define a new rate-distortion function as the minimum rate such that there exists a Wyner-Ziv code that is universal for every channel in the class. Then, we show an upper bound and a lower bound on the rate-distortion function, and derive a matching condition such that the upper and lower bounds coincide. The relation between the new rate-distortion function and the rate-distortion function of the Heegard-Berger problem is also discussed.
PREMIER - PRobabilistic Error-correction using Markov Inference in Errored Reads
Venue: arXiv cs.IT 2013
Year: 2013

In this work we present a flexible, probabilistic and reference-free method of error correction for high throughput DNA sequencing data. The key is to exploit the high coverage of sequencing data and model short sequence outputs as independent realizations of a Hidden Markov Model (HMM). We pose the problem of error correction of reads as one of maximum likelihood sequence detection over this HMM. While time and memory considerations rule out an implementation of the optimal Baum-Welch algorithm (for parameter estimation) and the optimal Viterbi algorithm (for error correction), we propose low-complexity approximate versions of both. Specifically, we propose an approximate Viterbi and a sequential decoding based algorithm for the error correction. Our results show that when compared with Reptile, a state-of-the-art error correction method, our methods consistently achieve superior performances on both simulated and real data sets.
Compound Polar Codes
Venue: arXiv cs.IT 2013
Year: 2013

A capacity-achieving scheme based on polar codes is proposed for reliable communication over multi-channels which can be directly applied to bit-interleaved coded modulation schemes. We start by reviewing the ground-breaking work of polar codes and then discuss our proposed scheme. Instead of encoding separately across the individual underlying channels, which requires multiple encoders and decoders, we take advantage of the recursive structure of polar codes to construct a unified scheme with a single encoder and decoder that can be used over the multi-channels. We prove that the scheme achieves the capacity over this multi-channel. Numerical analysis and simulation results for BICM channels at finite block lengths shows a considerable improvement in the probability of error comparing to a conventional separated scheme.
Highly Available Transactions: Virtues and Limitations (Extended Version)
Venue: arXiv cs.DB 2013
Year: 2013

To minimize network latency and remain online during server failures and network partitions, many modern distributed data storage systems eschew transactional functionality, which provides strong semantic guarantees for groups of multiple operations over multiple data items. In this work, we consider the problem of providing Highly Available Transactions (HATs): transactional guarantees that do not suffer unavailability during system partitions or incur high network latency. We introduce a taxonomy of highly available systems and analyze existing ACID isolation and distributed data consistency guarantees to identify which can and cannot be achieved in HAT systems. This unifies the literature on weak transactional isolation, replica consistency, and highly available systems. We analytically and experimentally quantify the availability and performance benefits of HATs--often two to three orders of magnitude over wide-area networks--and discuss their necessary semantic compromises.
Dynamic Spectrum Refarming with Overlay for Legacy Devices
Venue: arXiv cs.NI 2013
Year: 2013

The explosive growth in data traffic is resulting in a spectrum crunch forcing many wireless network operators to look towards refarming their 2G spectrum and deploy more spectrally efficient Long Term Evolution (LTE) technology. However, mobile network operators face a challenge when it comes to spectrum refarming because 2G technologies such as Global System for Mobile (GSM) is still widely used for low bandwidth machine-to-machine (M2M) devices. M2M devices typically have long life cycles, e.g. smart meters, and it is expensive to migrate these devices to newer technology since a truck roll will typically be required to the site where a device is deployed. Furthermore, with cost of 2G modules several times less than that of LTE, even newly deployed M2M devices tend to adopt 2G technology. Nevertheless, operators are keen to either force their 2G M2M customers to migrate so that they can refarm the spectrum or set aside a portion of the 2G spectrum for continuing operating 2G and only refarm the rest for LTE. In this paper we propose a novel solution to provide GSM connectivity within an LTE carrier through an efficient overlay by reserving a few physical resource blocks for GSM. With this approach, operators can refarm their 2G spectrum to LTE efficiently while still providing some GSM connectivity to their low data rate M2M customers. Furthermore, spectrum can be dynamically shared between LTE and GSM. An approach similar to that proposed in this paper can also be applied for other narrow band technology overlays over LTE.
An Efficient CCA2-Secure Variant of the McEliece Cryptosystem in the Standard Model
Venue: arXiv cs.CR 2013
Year: 2013

Recently, a few chosen-ciphertext secure (CCA2-secure) variants of the McEliece public-key encryption (PKE) scheme in the standard model were introduced. All the proposed schemes are based on encryption repetition paradigm and use general transformation from CPA-secure scheme to a CCA2-secure one. Therefore, the resulting encryption scheme needs \textit{separate} encryption and has \textit{large} key size compared to the original scheme, which complex public key size problem in the code-based PKE schemes. Thus, the proposed schemes are not sufficiently efficient to be used in practice. In this work, we propose an efficient CCA2-secure variant of the McEliece PKE scheme in the standard model. The main novelty is that, unlike previous approaches, our approach is a generic conversion and can be applied to \textit{any} one-way trapdoor function (OW-TDF), the lowest-level security notion in the context of public-key cryptography, resolving a big fundamental and central problem that has remained unsolved in the past two decades.
Parallel D2-Clustering: Large-Scale Clustering of Discrete Distributions
Venue: arXiv cs.LG 2013
Year: 2013

The discrete distribution clustering algorithm, namely D2-clustering, has demonstrated its usefulness in image classification and annotation where each object is represented by a bag of weighed vectors. The high computational complexity of the algorithm, however, limits its applications to large-scale problems. We present a parallel D2-clustering algorithm with substantially improved scalability. A hierarchical structure for parallel computing is devised to achieve a balance between the individual-node computation and the integration process of the algorithm. Additionally, it is shown that even with a single CPU, the hierarchical structure results in significant speed-up. Experiments on real-world large-scale image data, Youtube video data, and protein sequence data demonstrate the efficiency and wide applicability of the parallel D2-clustering algorithm. The loss in clustering accuracy is minor in comparison with the original sequential algorithm.
On the performance of 1-level LDPC lattices
Venue: arXiv cs.IT 2013
Year: 2013

The low-density parity-check (LDPC) lattices perform very well in high dimensions under generalized min-sum iterative decoding algorithm. In this work we focus on 1-level LDPC lattices. We show that these lattices are the same as lattices constructed based on Construction A and low-density lattice-code (LDLC) lattices. In spite of having slightly lower coding gain, 1-level regular LDPC lattices have remarkable performances. The lower complexity nature of the decoding algorithm for these type of lattices allows us to run it for higher dimensions easily. Our simulation results show that a 1-level LDPC lattice of size 10000 can work as close as 1.1 dB at normalized error probability (NEP) of $10^{-5}$.This can also be reported as 0.6 dB at symbol error rate (SER) of $10^{-5}$ with sum-product algorithm.
Improved Bounds on RIP for Generalized Orthogonal Matching Pursuit
Venue: arXiv cs.IT 2013
Year: 2013

Generalized Orthogonal Matching Pursuit (gOMP) is a natural extension of OMP algorithm where unlike OMP, it may select $N (\geq1)$ atoms in each iteration. In this paper, we demonstrate that gOMP can successfully reconstruct a $K$-sparse signal from a compressed measurement $ {\bf y}={\bf Φx}$ by $K^{th}$ iteration if the sensing matrix ${\bf Φ}$ satisfies restricted isometry property (RIP) of order $NK$ where $δ_{NK} < \frac {\sqrt{N}}{\sqrt{K}+2\sqrt{N}}$. Our bound offers an improvement over the very recent result shown in \cite{wang_2012b}. Moreover, we present another bound for gOMP of order $NK+1$ with $δ_{NK+1} < \frac {\sqrt{N}}{\sqrt{K}+\sqrt{N}}$ which exactly relates to the near optimal bound of $δ_{K+1} < \frac {1}{\sqrt{K}+1}$ for OMP (N=1) as shown in \cite{wang_2012a}.
Minimum Distance Distribution of Irregular Generalized LDPC Code Ensembles
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, the minimum distance distribution of irregular generalized LDPC (GLDPC) code ensembles is investigated. Two classes of GLDPC code ensembles are analyzed; in one case, the Tanner graph is regular from the variable node perspective, and in the other case the Tanner graph is completely unstructured and irregular. In particular, for the former ensemble class we determine exactly which ensembles have minimum distance growing linearly with the block length with probability approaching unity with increasing block length. This work extends previous results concerning LDPC and regular GLDPC codes to the case where a hybrid mixture of check node types is used.
A Class of Three-Weight Cyclic Codes
Venue: arXiv cs.IT 2013
Year: 2013

Cyclic codes are a subclass of linear codes and have applications in consumer electronics, data storage systems, and communication systems as they have efficient encoding and decoding algorithms. In this paper, a class of three-weight cyclic codes over $\gf(p)$ whose duals have two zeros is presented, where $p$ is an odd prime. The weight distribution of this class of cyclic codes is settled. Some of the cyclic codes are optimal. The duals of a subclass of the cyclic codes are also studied and proved to be optimal.
Tigers vs Lions: Towards Characterizing Solitary and Group User Behavior in MMORPG
Venue: arXiv cs.NI 2013
Year: 2013

The development of Internet technologies enables software developers to build virtual worlds such as Massively Multi-Player Online Role-Playing Games (MMORPGs). The population of such games shows super-linear growing tendency. It is estimated that the number of Internet users subscribed in MMORPGs is more than 22 million worldwide [1]. However, only little is known about the characteristics of traffic generated by such games as well as the behavior of their subscribers. In this paper, we characterize the traffic behavior of World of Warcraft, the most subscribed MMORPG in the world, by analyzing Internet traffic data sets collected from a European tier-1 ISP in two different time periods. We find that World of Warcraft is an influential application regarding the time spent by users (1.76 and 4.17 Hours/day on average in our measurement), while its traffic share is comparatively low (< 1 %). In this respect, we look at the World of Warcraft subscriber's gaming behavior by categorizing them into two different types of users (solitary users and group users) and compare these two groups in relation to the playing behavior (duration as the metric) and the in-game behavior (distance as the metric).