OpenRaiser/Intern-Atlas huggingface dataset:
Algebraic Properties of Polar Codes From a New Polynomial Formalism
Venue: arXiv cs.IT 2016
Year: 2016

Polar codes form a very powerful family of codes with a low complexity decoding algorithm that attain many information theoretic limits in error correction and source coding. These codes are closely related to Reed-Muller codes because both can be described with the same algebraic formalism, namely they are generated by evaluations of monomials. However, finding the right set of generating monomials for a polar code which optimises the decoding performances is a hard task and channel dependent. The purpose of this paper is to reveal some universal properties of these monomials. We will namely prove that there is a way to define a nontrivial (partial) order on monomials so that the monomials generating a polar code devised fo a binary-input symmetric channel always form a decreasing set. This property turns out to have rather deep consequences on the structure of the polar code. Indeed, the permutation group of a decreasing monomial code contains a large group called lower triangular affine group. Furthermore, the codewords of minimum weight correspond exactly to the orbits of the minimum weight codewords that are obtained from (evaluations) of monomials of the generating set. In particular, it gives an efficient way of counting the number of minimum weight codewords of a decreasing monomial code and henceforth of a polar code.
Shapley Values in Weighted Voting Games with Random Weights
Venue: arXiv cs.GT 2016
Year: 2016

We investigate the distribution of the well-studied Shapley--Shubik values in weighted voting games where the agents are stochastically determined. The Shapley--Shubik value measures the voting power of an agent, in typical collective decision making systems. While easy to estimate empirically given the parameters of a weighted voting game, the Shapley values are notoriously hard to reason about analytically. We propose a probabilistic approach in which the agent weights are drawn i.i.d. from some known exponentially decaying distribution. We provide a general closed-form characterization of the highest and lowest expected Shapley values in such a game, as a function of the parameters of the underlying distribution. To do so, we give a novel reinterpretation of the stochastic process that generates the Shapley variables as a renewal process. We demonstrate the use of our results on the uniform and exponential distributions. Furthermore, we show the strength of our theoretical predictions on several synthetic datasets.
Coping with Prospective Memory Failures: An Optimal Reminder System Design
Venue: arXiv cs.HC 2016
Year: 2016

Forgetting is in common in daily life, and 50-80% everyday's forgetting is due to prospective memory failures, which have significant impacts on our life. More seriously, some of these memory lapses can bring fatal consequences such as forgetting a sleeping infant in the back seat of a car. People tend to use various techniques to improve their prospective memory performance. Setting up a reminder is one of the most important techniques. The existing studies provide evidences in support of using reminders to cope with prospective memory failures. However, people are not satisfied with existing reminders because of their limitations in different aspects including reliability, optimization, and adaption. Through analysing the functions and features of existing reminder systems, this book draft summarizes their advantages and limitations. We are motivated to improve the performance of reminder systems. For the improvements, the relevant theories and mechanisms of prospective memory from psychology must be complied with, incorporated, and applied in this new study. Based on the literature review, a new reminder model is proposed, which includes a novel reminder planer, a prospective memory based agent, and a personalized user model. The reminder planer is responsible for determining the optimal reminder plan (including the optimal number of reminders, the optimal reminding schedule and the optimal reminding way). The prospective memory agent is responsible for executing the reminding processes. The personalized user model is proposed to learn from users' behaviors and preferences based on human-system interactions and is responsible for adapting the reminder plan to meet users' preferences as much as possible.
Using compatible shape descriptor for lexicon reduction of printed Farsi subwords
Venue: arXiv cs.CV 2016
Year: 2016

This Paper presents a method for lexicon reduction of Printed Farsi subwords based on their holistic shape features. Because of the large number of Persian subwords variously shaped from a simple letter to a complex combination of several connected characters, it is not easy to find a fixed shape descriptor suitable for all subwords. In this paper, we propose to select the descriptor according to the input shape characteristics. To do this, a neural network is trained to predict the appropriate descriptor of the input image. This network is implemented in the proposed lexicon reduction system to decide on the descriptor used for comparison of the query image with the lexicon entries. Evaluating the proposed method on a dataset of Persian subwords allows one to attest the effectiveness of the proposed idea of dealing differently with various query shapes.
A Characterization for the Existence of Connected $f$-Factors of $\textit{ Large}$ Minimum Degree
Venue: arXiv cs.DS 2016
Year: 2016

It is well known that when $f(v)$ is a constant for each vertex $v$, the connected $f$-factor problem is NP-Complete. In this note we consider the case when $f(v) \geq \lceil \frac{n}{2.5}\rceil$ for each vertex $v$, where $n$ is the number of vertices. We present a diameter based characterization of graphs having a connected $f$-factor (for such $f$). We show that if a graph $G$ has a connected $f$-factor and an $f$-factor with 2 connected components, then it has a connected $f$-factor of diameter at least 3. This result yields a polynomial time algorithm which first executes the Tutte's $f$-factor algorithm, and if the output has 2 connected components, our algorithm searches for a connected $f$-factor of diameter at least 3.
Channels with Synchronization/Substitution Errors and Computation of Error Control Codes
Venue: arXiv cs.IT 2016
Year: 2016

We introduce the concept of an \ff-maximal error-detecting block code, for some parameter \ff{} between 0 and 1, in order to formalize the situation where a block code is close to maximal with respect to being error-detecting. Our motivation for this is that constructing a maximal error-detecting code is a computationally hard problem. We present a randomized algorithm that takes as input two positive integers $N,\ell$, a probability value \ff, and a specification of the errors permitted in some application, and generates an error-detecting, or error-correcting, block code having up to $N$ codewords of length $\ell$. If the algorithm finds less than $N$ codewords, then those codewords constitute a code that is \ff-maximal with high probability. The error specification (also called channel) is modelled as a transducer, which allows one to model any rational combination of substitution and synchronization errors. We also present some elements of our implementation of various error-detecting properties and their associated methods. Then, we show several tests of the implemented randomized algorithm on various channels. A methodological contribution is the presentation of how various desirable error combinations can be expressed formally and processed algorithmically.
Balanced XOR-ed Coding
Venue: arXiv cs.IT 2016
Year: 2016

This paper concerns with the construction of codes over $GF(2)$ which reach the max-flow for single source multicast acyclic networks with delay. The coding is always a bitwise XOR of packets with equal lengths, and is based on highly symmetrical and balanced designs. For certain setups and parameters, our approach offers additional plausible security properties: an adversary needs to eavesdrop at least max-flow links in order to decode at least one original packet.
Efficiency and Optimality of Largest Deficit First Prioritization: Resource Allocation for Real-Time Applications
Venue: arXiv cs.NI 2016
Year: 2016

An increasing number of real-time applications with compute and/or communication deadlines are being supported on shared infrastructure. Such applications can often tolerate occasional deadline violations without substantially impacting their Quality of Service (QoS). A fundamental problem in such systems is deciding how to allocate shared resources so as to meet applications' QoS requirements. A simple framework to address this problem is to, (1) dynamically prioritize users as a possibly complex function of their deficits (difference of achieved vs required QoS), and (2) allocate resources so to expedite users with higher priority. This paper focuses on a general class of systems using such priority-based resource allocation. We first characterize the set of feasible QoS requirements and show the optimality of max weight-like prioritization. We then consider simple weighted Largest Deficit First (w-LDF) prioritization policies, where users with higher weighted QoS deficits are given higher priority. The paper gives an inner bound for the feasible set under w-LDF policies, and, under an additional monotonicity assumption, characterizes its geometry leading to a sufficient condition for optimality. Additional insights on the efficiency ratio of w-LDF policies, the optimality of hierarchical-LDF and characterization of clustering of failures are also discussed.
Generalized Degrees of Freedom of the Symmetric K-User Interference Channel under Finite Precision CSIT
Venue: arXiv cs.IT 2016
Year: 2016

The generalized degrees of freedom (GDoF) characterization of the symmetric K-user interference channel is obtained under finite precision channel state information at the transmitters (CSIT). The symmetric setting is where each cross channel is capable of carrying degrees of freedom (DoF) while each direct channel is capable of carrying 1 DoF. Remarkably, under finite precision CSIT the symmetric K-user interference channel loses all the GDoF benefits of interference alignment. The GDoF per user diminish with the number of users everywhere except in the very strong (optimal for every receiver to decode all messages) and very weak (optimal to treat all interference as noise) interference regimes. The result stands in sharp contrast to prior work on the symmetric setting under perfect CSIT, where the GDoF per user remain undiminished due to interference alignment. The result also stands in contrast to prior work on a subclass of asymmetric settings under finite precision CSIT, i.e., the topological interference management problem, where interference alignment plays a crucial role and provides substantial GDoF benefits.
Teaching Robots to Do Object Assembly using Multi-modal 3D Vision
Venue: arXiv cs.RO 2016
Year: 2016

The motivation of this paper is to develop a smart system using multi-modal vision for next-generation mechanical assembly. It includes two phases where in the first phase human beings teach the assembly structure to a robot and in the second phase the robot finds objects and grasps and assembles them using AI planning. The crucial part of the system is the precision of 3D visual detection and the paper presents multi-modal approaches to meet the requirements: AR markers are used in the teaching phase since human beings can actively control the process. Point cloud matching and geometric constraints are used in the robot execution phase to avoid unexpected noises. Experiments are performed to examine the precision and correctness of the approaches. The study is practical: The developed approaches are integrated with graph model-based motion planning, implemented on an industrial robots and applicable to real-world scenarios.
Panda: Neighbor Discovery on a Power Harvesting Budget
Venue: arXiv cs.NI 2016
Year: 2016

Object tracking applications are gaining popularity and will soon utilize Energy Harvesting (EH) low-power nodes that will consume power mostly for Neighbor Discovery (ND) (i.e., identifying nodes within communication range). Although ND protocols were developed for sensor networks, the challenges posed by emerging EH low-power transceivers were not addressed. Therefore, we design an ND protocol tailored for the characteristics of a representative EH prototype: the TI eZ430-RF2500-SEH. We present a generalized model of ND accounting for unique prototype characteristics (i.e., energy costs for transmission/reception, and transceiver state switching times/costs). Then, we present the Power Aware Neighbor Discovery Asynchronously (Panda) protocol in which nodes transition between the sleep, receive, and transmit states. We analyze \name and select its parameters to maximize the ND rate subject to a homogeneous power budget. We also present Panda-D, designed for non-homogeneous EH nodes. We perform extensive testbed evaluations using the prototypes and study various design tradeoffs. We demonstrate a small difference (less then 2%) between experimental and analytical results, thereby confirming the modeling assumptions. Moreover, we show that Panda improves the ND rate by up to 3x compared to related protocols. Finally, we show that Panda-D operates well under non-homogeneous power harvesting.
Robust Influence Maximization
Venue: arXiv cs.SI 2016
Year: 2016

In this paper, we address the important issue of uncertainty in the edge influence probability estimates for the well studied influence maximization problem --- the task of finding $k$ seed nodes in a social network to maximize the influence spread. We propose the problem of robust influence maximization, which maximizes the worst-case ratio between the influence spread of the chosen seed set and the optimal seed set, given the uncertainty of the parameter input. We design an algorithm that solves this problem with a solution-dependent bound. We further study uniform sampling and adaptive sampling methods to effectively reduce the uncertainty on parameters and improve the robustness of the influence maximization task. Our empirical results show that parameter uncertainty may greatly affect influence maximization performance and prior studies that learned influence probabilities could lead to poor performance in robust influence maximization due to relatively large uncertainty in parameter estimates, and information cascade based adaptive sampling method may be an effective way to improve the robustness of influence maximization.
Generalizing Prototype Theory: A Formal Quantum Framework
Venue: arXiv cs.AI 2016
Year: 2016

Theories of natural language and concepts have been unable to model the flexibility, creativity, context-dependence, and emergence, exhibited by words, concepts and their combinations. The mathematical formalism of quantum theory has instead been successful in capturing these phenomena such as graded membership, situational meaning, composition of categories, and also more complex decision making situations, which cannot be modeled in traditional probabilistic approaches. We show how a formal quantum approach to concepts and their combinations can provide a powerful extension of prototype theory. We explain how prototypes can interfere in conceptual combinations as a consequence of their contextual interactions, and provide an illustration of this using an intuitive wave-like diagram. This quantum-conceptual approach gives new life to original prototype theory, without however making it a privileged concept theory, as we explain at the end of our paper.
A Two-Prong Approach to Energy-Efficient WSNs: Wake-Up Receivers plus Dedicated, Model-Based Sensing
Venue: arXiv cs.NI 2016
Year: 2016

Energy neutral operation of WSNs can be achieved by exploiting the idleness of the workload to bring the average power consumption of each node below the harvesting power available. This paper proposes a combination of state-of-the-art low-power design techniques to minimize the local and global impact of the two main activities of each node: sampling and communication. Dynamic power management is adopted to exploit low-power modes during idle periods, while asynchronous wake-up and prediction-based data collection are used to opportunistically activate hardware components and network nodes only when they are strictly required. Furthermore, the concept of "model-based sensing" is introduced to push prediction-based data collection techniques as close as possible to the sensing elements. The results achieved on representative real-world WSN case studies show that the combined benefits of the design techniques adopted is more than linear, providing an overall power reduction of more than 3 orders of magnitude.
Scalable Anomaly Ranking of Attributed Neighborhoods
Venue: arXiv cs.SI 2016
Year: 2016

Given a graph with node attributes, what neighborhoods are anomalous? To answer this question, one needs a quality score that utilizes both structure and attributes. Popular existing measures either quantify the structure only and ignore the attributes (e.g., conductance), or only consider the connectedness of the nodes inside the neighborhood and ignore the cross-edges at the boundary (e.g., density). In this work we propose normality, a new quality measure for attributed neighborhoods. Normality utilizes structure and attributes together to quantify both internal consistency and external separability. It exhibits two key advantages over other measures: (1) It allows many boundary-edges as long as they can be "exonerated"; i.e., either (i) are expected under a null model, and/or (ii) the boundary nodes do not exhibit the subset of attributes shared by the neighborhood members. Existing measures, in contrast, penalize boundary edges irrespectively. (2) Normality can be efficiently maximized to automatically infer the shared attribute subspace (and respective weights) that characterize a neighborhood. This efficient optimization allows us to process graphs with millions of attributes. We capitalize on our measure to present a novel approach for Anomaly Mining of Entity Neighborhoods (AMEN). Experiments on real-world attributed graphs illustrate the effectiveness of our measure at anomaly detection, outperforming popular approaches including conductance, density, OddBall, and SODA. In addition to anomaly detection, our qualitative analysis demonstrates the utility of normality as a powerful tool to contrast the correlation between structure and attributes across different graphs.
Resiliency and Robustness of Complex, Multi-Genre Networks
Venue: arXiv cs.SI 2016
Year: 2016

We explore the resiliency and robustness of systems while viewing them as complex, multi-genre networks. The term "complex, multi-genre networks" refers to networks that combine several distinct genres - networks of physical resources, communication networks, information networks, and social and cognitive networks. We show that this perspective is fruitful and adds to our understanding of fundamental challenges and tradeoffs in robustness and resiliency, as well as potential solutions to the challenges. Study of systems as multi-genre networks is relatively uncommon; instead, it is customary in research and engineering literature to focus on a view of a network comprised of homogeneous elements, (e.g., a network of communication devices, or a network of social beings). Yet, most if not all real-world networks are multi-genre - it is hard to find any real system of a significant complexity that does not include a combination of interconnected physical elements, communication devices and channels, data collections, and human users forming an integrated, inter-dependent whole. Most approaches to improving resiliency and robustness involve compromises, and the key challenge is to find a favorable compromise. Such compromises involve reducing or managing the complexity of the network: coupling, rigidity and dependency. We discuss several of these compromises, e.g., performance vs resiliency; resiliency to one type of disruption vs resiliency to another disruption type; and complexity vs resiliency.
The Utility of Hedged Assertions in the Emergence of Shared Categorical Labels
Venue: arXiv cs.AI 2016
Year: 2016

We investigate the emergence of shared concepts in a community of language users using a multi-agent simulation. We extend results showing that negated assertions are of use in developing shared categories, to include assertions modified by linguistic hedges. Results show that using hedged assertions positively affects the emergence of shared categories in two distinct ways. Firstly, using contraction hedges like `very' gives better convergence over time. Secondly, using expansion hedges such as `quite' reduces concept overlap. However, both these improvements come at a cost of slower speed of development.
Multivariate information measures: a unification using Möbius operators on subset lattices
Venue: arXiv cs.IT 2016
Year: 2016

Information related measures are useful tools for multi variable data analysis, as measures of dependence among variables, and as descriptions of order in biological and physical systems. Information related measures, like marginal entropies, mutual / interaction / multi-information, have been used in a number of fields including descriptions of systems complexity and biological data analysis. The mathematical relationships among these measures are therefore of significant interest. Relations between common information measures include the duality relations based on Möbius inversion on lattices. These are the direct consequence of the symmetries of the lattices of the sets of variables (subsets ordered by inclusion). While the mathematical properties and relationships among these information-related measures are of significant interest, there has been, to our knowledge, no systematic examination of the full range of relationships and no unification of this diverse range of functions into a single formalism as we do here. In this paper we define operators on functions on these lattices based on the Möbius inversion idea that map the functions into one another (Möbius operators.) We show that these operators form a simple group isomorphic to the symmetric group S3. Relations among the set of functions on the lattice are transparently expressed in terms of the operator algebra, and, applied to the information measures, can be used to derive a wide range of relationships among measures. We describe a direct relation between sums of conditional log-likelihoods and previously defined dependency measures. The algebra is naturally generalized which yields more extensive relationships. This formalism provides a fundamental unification of information related measures, but isomorphism of all distributive lattices with the subset lattice implies broad potential application of these results.
Variational formulas for the power of the binary hypothesis testing problem with applications
Venue: arXiv cs.IT 2016
Year: 2016

Two variational formulas for the power of the binary hypothesis testing problem are derived. The first is given as the Legendre transform of a certain function and the second, induced from the first, is given in terms of the Cumulative Distribution Function (CDF) of the log-likelihood ratio. One application of the first formula is an upper bound on the power of the binary hypothesis testing problem in terms of the Re'nyi divergence. The second formula provide a general framework for proving asymptotic and non-asymptotic expressions for the power of the test utilizing corresponding expressions for the CDF of the log-likelihood. The framework is demonstrated in the central limit regime (i.e., for non-vanishing type I error) and in the large deviations regime.