OpenRaiser/Intern-Atlas huggingface dataset:
Some new results on permutation polynomials over finite fields
Venue: arXiv cs.IT 2016
Year: 2016

Permutation polynomials over finite fields constitute an active research area and have applications in many areas of science and engineering. In this paper, four classes of monomial complete permutation polynomials and one class of trinomial complete permutation polynomials are presented, one of which confirms a conjecture proposed by Wu et al. (Sci. China Math., to appear. Doi: 10.1007/s11425-014-4964-2). Furthermore, we give two classes of trinomial permutation polynomials, and make some progress on a conjecture about the differential uniformity of power permutation polynomials proposed by Blondeau et al. (Int. J. Inf. Coding Theory, 2010, 1, pp. 149-170).
Phase-Rotation-Aided Relay Selection in Two-Way Decode-and-Forward Relay Networks
Venue: arXiv cs.IT 2016
Year: 2016

This paper proposes a relay selection scheme that aims to improve the end-to-end symbol error rate (SER) performance of a two-way relay network (TWRN). The TWRN consists of two single-antenna sources and multiple relays employing decode-and-forward (DF) protocol. It is shown that the SER performance is determined by the minimum decision distance (DD) observed in the TWRN. However, the minimum DD is likely to be made arbitrarily small by channel fading. To tackle this problem, a phase rotation (PR) aided relay selection (RS) scheme is proposed to enlarge the minium DD, which in turn improves the SER performance. The proposed PR based scheme rotates the phases of the transmitted symbols of one source and of the selected relay according to the channel state information, aiming for increasing all DDs to be above a desired bound. The lower bound is further optimized by using a MaxMin-RS criterion associated with the channel gains. It is demonstrated that the PR aided MaxMin-RS approach achieves full diversity gain and an improved array gain. Furthermore, compared with the existing DF based schemes, the proposed scheme allows more flexible relay antenna configurations.
A Theory of Local Learning, the Learning Channel, and the Optimality of Backpropagation
Venue: arXiv cs.LG 2016
Year: 2016

In a physical neural system, where storage and processing are intimately intertwined, the rules for adjusting the synaptic weights can only depend on variables that are available locally, such as the activity of the pre- and post-synaptic neurons, resulting in local learning rules. A systematic framework for studying the space of local learning rules is obtained by first specifying the nature of the local variables, and then the functional form that ties them together into each learning rule. Such a framework enables also the systematic discovery of new learning rules and exploration of relationships between learning rules and group symmetries. We study polynomial local learning rules stratified by their degree and analyze their behavior and capabilities in both linear and non-linear units and networks. Stacking local learning rules in deep feedforward networks leads to deep local learning. While deep local learning can learn interesting representations, it cannot learn complex input-output functions, even when targets are available for the top layer. Learning complex input-output functions requires local deep learning where target information is communicated to the deep layers through a backward learning channel. The nature of the communicated information about the targets and the structure of the learning channel partition the space of learning algorithms. We estimate the learning channel capacity associated with several algorithms and show that backpropagation outperforms them by simultaneously maximizing the information rate and minimizing the computational cost, even in recurrent networks. The theory clarifies the concept of Hebbian learning, establishes the power and limitations of local learning rules, introduces the learning channel which enables a formal analysis of the optimality of backpropagation, and explains the sparsity of the space of learning rules discovered so far.
Synchronization of Bernoulli sequences on shared letters
Venue: arXiv cs.FL 2016
Year: 2016

The topic of this paper is the distributed and incremental generation of long executions of concurrent systems, uniformly or more generally with weights associated to elementary actions. Synchronizing sequences of letters on alphabets sharing letters are known to produce a trace in the concurrency theoretic sense, i.e., a labeled partially ordered set. We study the probabilistic aspects by considering the synchronization of Bernoulli sequences of letters, under the light of Bernoulli and uniform measures recently introduced for trace monoids. We introduce two algorithms that produce random traces, using only local random primitives. We thoroughly study some specific examples, the path model and the ring model, both of arbitrary size. For these models, we show how to generate any Bernoulli distributed random traces, which includes the case of uniform generation.
Bounds for the Clique Cover Width of Factors of the Apex Graph of the Planar Grid
Venue: arXiv cs.DM 2016
Year: 2016

The {\it clique cover width} of $G$, denoted by $ccw(G)$, is the minimum value of the bandwidth of all graphs that are obtained by contracting the cliques in a clique cover of $G$ into a single vertex. For $i=1,2,...,d,$ let $G_i$ be a graph with $V(G_i)=V$, and let $G$ be a graph with $V(G)=V$ and $E(G)=\cap_{i=1}^d(G_i)$, then we write $G=\cap_{i=1}^dG_i$ and call each $G_i,i=1,2,...,d$ a factor of $G$. We are interested in the case where $G_1$ is chordal, and $ccw(G_i),i=2,3...,d$ for each factor $G_i$ is "small". Here we show a negative result. Specifically, let ${\hat G}(k,n)$ be the graph obtained by joining a set of $k$ apex vertices of degree $n^2$ to all vertices of an $n\times n$ grid, and then adding some possible edges among these $k$ vertices. We prove that if ${\hat G}(k,n)=\cap_{i=1}^dG_i$, with $G_1$ being chordal, then, $max_{2\le i\le d}\{ccw(G_i)\}\ge {n^{1\over d-1}\over 2.{(2c)}^{1\over {d-1}}}$, where $c$ is a constant. Furthermore, for $d=2$, we construct a chordal graph $G_1$ and a graph $G_2$ with $ccw(G_2)\le {n\over 2}+k$ so that ${\hat G}(k,n)=G_1\cap G_2$. Finally, let ${\hat G}$ be the clique sum graph of ${\hat G}(k_i, n_i), i=1,2,...t$, where the underlying grid is $n_i\times n_i$ and the sum is taken at apex vertices. Then, we show ${\hat G}=G_1\cap G_2$, where, $G_1$ is chordal and $ccw(G_2)\le \sum_{i=1}^t(n_i+k_i)$. The implications and applications of the results are discussed, including addressing a recent question of David Wood.
AccFFT: A library for distributed-memory FFT on CPU and GPU architectures
Venue: arXiv cs.DC 2016
Year: 2016

We present a new library for parallel distributed Fast Fourier Transforms (FFT). The importance of FFT in science and engineering and the advances in high performance computing necessitate further improvements. AccFFT extends existing FFT libraries for CUDA-enabled Graphics Processing Units (GPUs) to distributed memory clusters. We use overlapping communication method to reduce the overhead of PCIe transfers from/to GPU. We present numerical results on the Maverick platform at the Texas Advanced Computing Center (TACC) and on the Titan system at the Oak Ridge National Laboratory (ORNL). We present the scaling of the library up to 4,096 K20 GPUs of Titan.
Bisimulation and expressivity for conditional belief, degrees of belief, and safe belief
Venue: arXiv cs.AI 2016
Year: 2016

Plausibility models are Kripke models that agents use to reason about knowledge and belief, both of themselves and of each other. Such models are used to interpret the notions of conditional belief, degrees of belief, and safe belief. The logic of conditional belief contains that modality and also the knowledge modality, and similarly for the logic of degrees of belief and the logic of safe belief. With respect to these logics, plausibility models may contain too much information. A proper notion of bisimulation is required that characterises them. We define that notion of bisimulation and prove the required characterisations: on the class of image-finite and preimage-finite models (with respect to the plausibility relation), two pointed Kripke models are modally equivalent in either of the three logics, if and only if they are bisimilar. As a result, the information content of such a model can be similarly expressed in the logic of conditional belief, or the logic of degrees of belief, or that of safe belief. This, we found a surprising result. Still, that does not mean that the logics are equally expressive: the logics of conditional and degrees of belief are incomparable, the logics of degrees of belief and safe belief are incomparable, while the logic of safe belief is more expressive than the logic of conditional belief. In view of the result on bisimulation characterisation, this is an equally surprising result. We hope our insights may contribute to the growing community of formal epistemology and on the relation between qualitative and quantitative modelling.
Support Recovery for Sparse Deconvolution of Positive Measures
Venue: arXiv cs.IT 2016
Year: 2016

We study sparse spikes deconvolution over the space of Radon measures on $\mathbb{R}$ or $\mathbb{T}$ when the input measure is a finite sum of positive Dirac masses using the BLASSO convex program. We focus on the recovery properties of the support and the amplitudes of the initial measure in the presence of noise as a function of the minimum separation $t$ of the input measure (the minimum distance between two spikes). We show that when ${w}/λ$, ${w}/t^{2N-1}$ and $λ/t^{2N-1}$ are small enough (where $λ$ is the regularization parameter, $w$ the noise and $N$ the number of spikes), which corresponds roughly to a sufficient signal-to-noise ratio and a noise level small enough with respect to the minimum separation, there exists a unique solution to the BLASSO program with exactly the same number of spikes as the original measure. We show that the amplitudes and positions of the spikes of the solution both converge toward those of the input measure when the noise and the regularization parameter drops to zero faster than $t^{2N-1}$.
Large-scale Optimization-based Non-negative Computational Framework for Diffusion Equations: Parallel Implementation and Performance Studies
Venue: arXiv cs.NA 2016
Year: 2016

It is well-known that the standard Galerkin formulation, which is often the formulation of choice under the finite element method for solving self-adjoint diffusion equations, does not meet maximum principles and the non-negative constraint for anisotropic diffusion equations. Recently, optimization-based methodologies that satisfy maximum principles and the non-negative constraint for steady-state and transient diffusion-type equations have been proposed. To date, these methodologies have been tested only on small-scale academic problems. The purpose of this paper is to systematically study the performance of the non-negative methodology in the context of high performance computing (HPC). PETSc and TAO libraries are, respectively, used for the parallel environment and optimization solvers. For large-scale problems, it is important for computational scientists to understand the computational performance of current algorithms available in these scientific libraries. The numerical experiments are conducted on the state-of-the-art HPC systems, and a single-core performance model is used to better characterize the efficiency of the solvers. Our studies indicate that the proposed non-negative computational framework for diffusion-type equations exhibits excellent strong scaling for real-world large-scale problems.
WYSIWYE: An Algebra for Expressing Spatial and Textual Rules for Visual Information Extraction
Venue: arXiv cs.CL 2016
Year: 2016

The visual layout of a webpage can provide valuable clues for certain types of Information Extraction (IE) tasks. In traditional rule based IE frameworks, these layout cues are mapped to rules that operate on the HTML source of the webpages. In contrast, we have developed a framework in which the rules can be specified directly at the layout level. This has many advantages, since the higher level of abstraction leads to simpler extraction rules that are largely independent of the source code of the page, and, therefore, more robust. It can also enable specification of new types of rules that are not otherwise possible. To the best of our knowledge, there is no general framework that allows declarative specification of information extraction rules based on spatial layout. Our framework is complementary to traditional text based rules framework and allows a seamless combination of spatial layout based rules with traditional text based rules. We describe the algebra that enables such a system and its efficient implementation using standard relational and text indexing features of a relational database. We demonstrate the simplicity and efficiency of this system for a task involving the extraction of software system requirements from software product pages.
A polynomial kernel for Block Graph Deletion
Venue: arXiv cs.DS 2016
Year: 2016

In the Block Graph Deletion problem, we are given a graph $G$ on $n$ vertices and a positive integer $k$, and the objective is to check whether it is possible to delete at most $k$ vertices from $G$ to make it a block graph, i.e., a graph in which each block is a clique. In this paper, we obtain a kernel with $\mathcal{O}(k^{6})$ vertices for the Block Graph Deletion problem. This is a first step to investigate polynomial kernels for deletion problems into non-trivial classes of graphs of bounded rank-width, but unbounded tree-width. Our result also implies that Chordal Vertex Deletion admits a polynomial-size kernel on diamond-free graphs. For the kernelization and its analysis, we introduce the notion of `complete degree' of a vertex. We believe that the underlying idea can be potentially applied to other problems. We also prove that the Block Graph Deletion problem can be solved in time $10^{k}\cdot n^{\mathcal{O}(1)}$.
Efficient and Parsimonious Agnostic Active Learning
Venue: arXiv cs.LG 2016
Year: 2016

We develop a new active learning algorithm for the streaming setting satisfying three important properties: 1) It provably works for any classifier representation and classification problem including those with severe noise. 2) It is efficiently implementable with an ERM oracle. 3) It is more aggressive than all previous approaches satisfying 1 and 2. To do this we create an algorithm based on a newly defined optimization problem and analyze it. We also conduct the first experimental analysis of all efficient agnostic active learning algorithms, evaluating their strengths and weaknesses in different settings.
Online Learning to Sample
Venue: arXiv cs.LG 2016
Year: 2016

Stochastic Gradient Descent (SGD) is one of the most widely used techniques for online optimization in machine learning. In this work, we accelerate SGD by adaptively learning how to sample the most useful training examples at each time step. First, we show that SGD can be used to learn the best possible sampling distribution of an importance sampling estimator. Second, we show that the sampling distribution of an SGD algorithm can be estimated online by incrementally minimizing the variance of the gradient. The resulting algorithm - called Adaptive Weighted SGD (AW-SGD) - maintains a set of parameters to optimize, as well as a set of parameters to sample learning examples. We show that AWSGD yields faster convergence in three different applications: (i) image classification with deep features, where the sampling of images depends on their labels, (ii) matrix factorization, where rows and columns are not sampled uniformly, and (iii) reinforcement learning, where the optimized and exploration policies are estimated at the same time, where our approach corresponds to an off-policy gradient algorithm.
A Dynamic Game Model of Collective Choice in Multi-Agent Systems
Venue: arXiv cs.SY 2016
Year: 2016

Inspired by successful biological collective decision mechanisms such as honey bees searching for a new colony or the collective navigation of fish schools, we consider a mean field games (MFG)-like scenario where a large number of agents have to make a choice among a set of different potential target destinations. Each individual both influences and is influenced by the group's decision, as well as the mean trajectory of all the agents. The model can be interpreted as a stylized version of opinion crystallization in an election for example. The agents' biases are dictated first by their initial spatial position and, in a subsequent generalization of the model, by a combination of initial position and a priori individual preference. The agents have linear dynamics and are coupled through a modified form of quadratic cost. Fixed point based finite population equilibrium conditions are identified and associated existence conditions are established. In general multiple equilibria may exist and the agents need to know all initial conditions to compute them precisely. However, as the number of agents increases sufficiently, we show that 1) the computed fixed point equilibria qualify as epsilon Nash equilibria, 2) agents no longer require all initial conditions to compute the equilibria but rather can do so based on a representative probability distribution of these conditions now viewed as random variables. Numerical results are reported.
An MDP Model for Optimal Handover Decisions in mmWave Cellular Networks
Venue: arXiv cs.NI 2016
Year: 2016

The new frontier in cellular networks is harnessing the enormous spectrum available at millimeter wave (mmWave) frequencies above 28 GHz. The challenging radio propagation characteristics at these frequencies, and the use of highly directional beamforming, lead to intermittent links between the base station (BS) and the user equipment (UE). In this paper, we revisit the problem of cell selection to maintain an acceptable level of service, despite the underlying intermittent link connectivity typical of mmWave links. We propose a Markov Decision Process (MDP) framework to study the properties and performance of our proposed cell selection strategy, which jointly considers several factors such as dynamic channel load and link quality. We use the Value Iteration Algorithm (VIA) to solve the MDP, and obtain the optimal set of associations. We address the multi user problem through a distributed iterative approach, in which each UE characterizes the evolution of the system based on stationary channel distribution and cell selection statistics of other UEs. Through simulation results, we show that our proposed technique makes judicious handoff choices, thereby providing a significant improvement in the overall network capacity. Further, our technique reduces the total number of handoffs, thus lowering the signaling overhead, while providing a higher quality of service to the UEs.
Secure Massive MIMO Transmission with an Active Eavesdropper
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we investigate secure and reliable transmission strategies for multi-cell multi-user massive multiple-input multiple-output (MIMO) systems with a multi-antenna active eavesdropper. We consider a time-division duplex system where uplink training is required and an active eavesdropper can attack the training phase to cause pilot contamination at the transmitter. This forces the precoder used in the subsequent downlink transmission phase to implicitly beamform towards the eavesdropper, thus increasing its received signal power. Assuming matched filter precoding and artificial noise (AN) generation at the transmitter, we derive an asymptotic achievable secrecy rate when the number of transmit antennas approaches infinity. For the case of a single-antenna active eavesdropper, we obtain a closed-form expression for the optimal power allocation policy for the transmit signal and the AN, and find the minimum transmit power required to ensure reliable secure communication. Furthermore, we show that the transmit antenna correlation diversity of the intended users and the eavesdropper can be exploited in order to improve the secrecy rate. In fact, under certain orthogonality conditions of the channel covariance matrices, the secrecy rate loss introduced by the eavesdropper can be completely mitigated.
Perfect Secrecy in Physical Layer Network Coding Systems from Structured Interference
Venue: arXiv cs.IT 2016
Year: 2016

Physical layer network coding (PNC) has been proposed for next generation networks. In this contribution, we investigate PNC schemes with embedded perfect secrecy by exploiting structured interference in relay networks with two users and a single relay. In a practical scenario where both users employ finite and uniform signal input distributions we propose upper bounds (UBs) on the achievable perfect secrecy rates and make these explicit when PAM modems are used. We then describe two simple, explicit encoders that can achieve perfect secrecy rates close to these UBs with respect to an untrustworthy relay in the single antenna and single relay setting. Lastly, we generalize our system to a MIMO relay channel where the relay has more antennas than the users and optimal precoding matrices which maintain a required secrecy constraint are studied. Our results establish that the design of PNC transmission schemes with enhanced throughput and guaranteed data confidentiality is feasible in next generation systems.
Universal Decoding for Source-Channel Coding with Side Information
Venue: arXiv cs.IT 2016
Year: 2016

We consider a setting of Slepian--Wolf coding, where the random bin of the source vector undergoes channel coding, and then decoded at the receiver, based on additional side information, correlated to the source. For a given distribution of the randomly selected channel codewords, we propose a universal decoder that depends on the statistics of neither the correlated sources nor the channel, assuming first that they are both memoryless. Exact analysis of the random-binning/random-coding error exponent of this universal decoder shows that it is the same as the one achieved by the optimal maximum a-posteriori (MAP) decoder. Previously known results on universal Slepian-Wolf source decoding, universal channel decoding, and universal source-channel decoding, are all obtained as special cases of this result. Subsequently, we further generalize the results in several directions, including: (i) finite-state sources and finite-state channels, along with a universal decoding metric that is based on Lempel-Ziv parsing, (ii) arbitrary sources and channels, where the universal decoding is with respect to a given class of decoding metrics, and (iii) full (symmetric) Slepian-Wolf coding, where both source streams are separately fed into random-binning source encoders, followed by random channel encoders, which are then jointly decoded by a universal decoder.