OpenRaiser/Intern-Atlas huggingface dataset:
On Universal Properties of Capacity-Approaching LDPC Ensembles
Venue: arXiv cs.IT 2015
Year: 2015

This paper is focused on the derivation of some universal properties of capacity-approaching low-density parity-check (LDPC) code ensembles whose transmission takes place over memoryless binary-input output-symmetric (MBIOS) channels. Properties of the degree distributions, graphical complexity and the number of fundamental cycles in the bipartite graphs are considered via the derivation of information-theoretic bounds. These bounds are expressed in terms of the target block/ bit error probability and the gap (in rate) to capacity. Most of the bounds are general for any decoding algorithm, and some others are proved under belief propagation (BP) decoding. Proving these bounds under a certain decoding algorithm, validates them automatically also under any sub-optimal decoding algorithm. A proper modification of these bounds makes them universal for the set of all MBIOS channels which exhibit a given capacity. Bounds on the degree distributions and graphical complexity apply to finite-length LDPC codes and to the asymptotic case of an infinite block length. The bounds are compared with capacity-approaching LDPC code ensembles under BP decoding, and they are shown to be informative and are easy to calculate. Finally, some interesting open problems are considered.
Pseudorandom Generators Against Advised Context-Free Languages
Venue: arXiv cs.FL 2015
Year: 2015

Pseudorandomness has played a central role in modern cryptography, finding theoretical and practical applications to various fields of computer science. A function that generates pseudorandom strings from shorter but truly random seeds is known as a pseudorandom generator. Our generators are designed to fool languages (or equivalently, Boolean-valued functions). In particular, our generator fools advised context-free languages, namely, context-free languages assisted by external information known as advice, and moreover our generator is made almost one-to-one, stretching $n$-bit seeds to $n+1$ bits. We explicitly construct such a pseudorandom generator, which is computed by a deterministic Turing machine using logarithmic space and also belongs to CFLMV(2)/n---a functional extension of the 2-conjunctive closure of CFL with the help of appropriate deterministic advice. In contrast, we show that there is no almost one-to-one pseudorandom generator against context-free languages if we demand that it should be computed by a nondeterministic pushdown automaton equipped with a write-only output tape. Our generator naturally extends known pseudorandom generators against advised regular languages. Our proof of the CFL/n-pseudorandomness of the generator is quite elementary, and in particular, one part of the proof utilizes a special feature of the behaviors of nondeterministic pushdown automata, called a swapping property, which is interesting in its own right, generalizing the swapping lemma for context-free languages.
Learning Exponential Families in High-Dimensions: Strong Convexity and Sparsity
Venue: arXiv cs.LG 2015
Year: 2015

The versatility of exponential families, along with their attendant convexity properties, make them a popular and effective statistical model. A central issue is learning these models in high-dimensions, such as when there is some sparsity pattern of the optimal parameter. This work characterizes a certain strong convexity property of general exponential families, which allow their generalization ability to be quantified. In particular, we show how this property can be used to analyze generic exponential families under L_1 regularization.
User Scheduling for Cooperative Base Station Transmission Exploiting Channel Asymmetry
Venue: arXiv cs.IT 2015
Year: 2015

We study low-signalling overhead scheduling for downlink coordinated multi-point (CoMP) transmission with multi-antenna base stations (BSs) and single-antenna users. By exploiting the asymmetric channel feature, i.e., the pathloss differences towards different BSs, we derive a metric to judge orthogonality among users only using their average channel gains, based on which we propose a semi-orthogonal scheduler that can be applied in a two-stage transmission strategy. Simulation results demonstrate that the proposed scheduler performs close to the semi-orthogonal scheduler with full channel information, especially when each BS is with more antennas and the celledge region is large. Compared with other overhead reduction strategies, the proposed scheduler requires much less training overhead to achieve the same cell-average data rate.
ActorScript(TM) extension of C sharp (TM), Java(TM), and Objective C(TM): iAdaptive(TM) concurrency for antiCloud(TM) privacy and security
Venue: arXiv cs.PL 2015
Year: 2015

ActorScript(TM) is a general purpose programming language for implementing discretionary, adaptive concurrency that manages resources and demand. It is differentiated from previous languages by the following: - Universality *** Ability to specify what Actors can do *** Specify interface between hardware and software *** Everything in the language is accomplished using message passing including the very definition of ActorScript itself *** Functional, Imperative, Logic, and Concurrent programming are integrated. *** Concurrency dynamically adapts to resources available and current load. *** Programs do not expose low-level implementation mechanisms such as threads, tasks, locks, cores, etc. *** Messages can be directly communicated without requiring indirection through brokers, channels, class hierarchies, mailboxes, pipes, ports, queues etc. *** Variable races are eliminated. *** Binary XML and JSON are data types. *** Application binary interfaces are afforded so that no identifier symbol need be looked up at runtime. - Safety and Security *** Programs are extension invariant, i.e., extending a program does not change its meaning. *** Applications cannot directly harm each other. - Performance *** Impose no overhead on implementation of Actor systems *** Message passing has essentially same overhead as procedure calling and looping. *** Allow execution to be dynamically adjusted for system load and capacity (e.g. cores) *** Locality because execution is not bound by a sequential global memory model *** Inherent concurrency because execution is not bound by communicating sequential processes *** Minimize latency along critical paths
Drawing Trees with Perfect Angular Resolution and Polynomial Area
Venue: arXiv cs.CG 2015
Year: 2015

We study methods for drawing trees with perfect angular resolution, i.e., with angles at each node v equal to 2π/d(v). We show: 1. Any unordered tree has a crossing-free straight-line drawing with perfect angular resolution and polynomial area. 2. There are ordered trees that require exponential area for any crossing-free straight-line drawing having perfect angular resolution. 3. Any ordered tree has a crossing-free Lombardi-style drawing (where each edge is represented by a circular arc) with perfect angular resolution and polynomial area. Thus, our results explore what is achievable with straight-line drawings and what more is achievable with Lombardi-style drawings, with respect to drawings of trees with perfect angular resolution.
Simple arithmetic versus intuitive understanding: The case of the impact factor
Venue: arXiv cs.DL 2015
Year: 2015

We show that as a consequence of basic properties of elementary arithmetic journal impact factors show a counterintuitive behaviour with respect to adding non-cited articles. Synchronous as well as diachronous journal impact factors are affected. Our findings provide a rationale for not taking uncitable publications into account in impact factor calculations, at least if these items are truly uncitable.
Some Notes on Quantum Information Theory and Emerging Computing Technologies
Venue: arXiv cs.IT 2015
Year: 2015

It is considered an interdependence of the theory of quantum computing and some perspective information technologies. A couple of illustrative and useful examples are discussed. The reversible computing from very beginning had the serious impact on the design of quantum computers and it is revisited first. Some applications of ternary circuits are also quite instructive and it may be useful in the quantum information theory.
On Bisimulations for Description Logics
Venue: arXiv cs.LO 2015
Year: 2015

We study bisimulations for useful description logics. The simplest among the considered logics is $\mathcal{ALC}_{reg}$ (a variant of PDL). The others extend that logic with inverse roles, nominals, quantified number restrictions, the universal role, and/or the concept constructor for expressing the local reflexivity of a role. They also allow role axioms. We give results about invariance of concepts, TBoxes and ABoxes, preservation of RBoxes and knowledge bases, and the Hennessy-Milner property w.r.t. bisimulations in the considered description logics. Using the invariance results we compare the expressiveness of the considered description logics w.r.t. concepts, TBoxes and ABoxes. Our results about separating the expressiveness of description logics are naturally extended to the case when instead of $\mathcal{ALC}_{reg}$ we have any sublogic of $\mathcal{ALC}_{reg}$ that extends $\mathcal{ALC}$. We also provide results on the largest auto-bisimulations and quotient interpretations w.r.t. such equivalence relations. Such results are useful for minimizing interpretations and concept learning in description logics. To deal with minimizing interpretations for the case when the considered logic allows quantified number restrictions and/or the constructor for the local reflexivity of a role, we introduce a new notion called QS-interpretation, which is needed for obtaining expected results. By adapting Hopcroft's automaton minimization algorithm and the Paige-Tarjan algorithm, we give efficient algorithms for computing the partition corresponding to the largest auto-bisimulation of a finite interpretation.
A Tighter Insertion-based Approximation of the Crossing Number
Venue: arXiv cs.DM 2015
Year: 2015

Let G be a planar graph and F a set of additional edges not yet in G. The multiple edge insertion problem (MEI) asks for a drawing of G+F with the minimum number of pairwise edge crossings, such that the subdrawing of G is plane. Finding an exact solution to MEI is NP-hard for general F. We present the first polynomial time algorithm for MEI that achieves an additive approximation guarantee -- depending only on the size of F and the maximum degree of G, in the case of connected G. Our algorithm seems to be the first directly implementable one in that realm, too, next to the single edge insertion. It is also known that an (even approximate) solution to the MEI problem would approximate the crossing number of the F-almost-planar graph G+F, while computing the crossing number of G+F exactly is NP-hard already when |F|=1. Hence our algorithm induces new, improved approximation bounds for the crossing number problem of F-almost-planar graphs, achieving constant-factor approximation for the large class of such graphs of bounded degrees and bounded size of F.
Explicit Bounds for Entropy Concentration under Linear Constraints
Venue: arXiv cs.IT 2015
Year: 2015

Consider the set of all sequences of $n$ outcomes, each taking one of $m$ values, that satisfy a number of linear constraints. If $m$ is fixed while $n$ increases, most sequences that satisfy the constraints result in frequency vectors whose entropy approaches that of the maximum entropy vector satisfying the constraints. This well-known "entropy concentration" phenomenon underlies the maximum entropy method. Existing proofs of the concentration phenomenon are based on limits or asymptotics and unrealistically assume that constraints hold precisely, supporting maximum entropy inference more in principle than in practice. We present, for the first time, non-asymptotic, explicit lower bounds on $n$ for a number of variants of the concentration result to hold to any prescribed accuracies, with the constraints holding up to any specified tolerance, taking into account the fact that allocations of discrete units can satisfy constraints only approximately. Again unlike earlier results, we measure concentration not by deviation from the maximum entropy value, but by the $\ell_1$ and $\ell_2$ distances from the maximum entropy-achieving frequency vector. One of our results holds independently of the alphabet size $m$ and is based on a novel proof technique using the multi-dimensional Berry-Esseen theorem. We illustrate and compare our results using various detailed examples.
New Improvements on the Echelon-Ferrers Construction
Venue: arXiv cs.IT 2015
Year: 2015

We show how to improve the echelon-Ferrers construction of random network codes introduced by Etzion and Silberstein to attain codes of larger size for a given minimum distance.
Improved Smoothed Analysis of Multiobjective Optimization
Venue: arXiv cs.DS 2015
Year: 2015

We present several new results about smoothed analysis of multiobjective optimization problems. Motivated by the discrepancy between worst-case analysis and practical experience, this line of research has gained a lot of attention in the last decade. We consider problems in which d linear and one arbitrary objective function are to be optimized over a subset S of {0,1}^n of feasible solutions. We improve the previously best known bound for the smoothed number of Pareto-optimal solutions to O(n^{2d} phi^d), where phi denotes the perturbation parameter. Additionally, we show that for any constant c the c-th moment of the smoothed number of Pareto-optimal solutions is bounded by O((n^{2d} phi^d)^c). This improves the previously best known bounds significantly. Furthermore, we address the criticism that the perturbations in smoothed analysis destroy the zero-structure of problems by showing that the smoothed number of Pareto-optimal solutions remains polynomially bounded even for zero-preserving perturbations. This broadens the class of problems captured by smoothed analysis and it has consequences for non-linear objective functions. One corollary of our result is that the smoothed number of Pareto-optimal solutions is polynomially bounded for polynomial objective functions.
Discrete and fuzzy dynamical genetic programming in the XCSF learning classifier system
Venue: arXiv cs.AI 2015
Year: 2015

A number of representation schemes have been presented for use within learning classifier systems, ranging from binary encodings to neural networks. This paper presents results from an investigation into using discrete and fuzzy dynamical system representations within the XCSF learning classifier system. In particular, asynchronous random Boolean networks are used to represent the traditional condition-action production system rules in the discrete case and asynchronous fuzzy logic networks in the continuous-valued case. It is shown possible to use self-adaptive, open-ended evolution to design an ensemble of such dynamical systems within XCSF to solve a number of well-known test problems.
Iterative Reconstruction of Rank-One Matrices in Noise
Venue: arXiv cs.IT 2015
Year: 2015

We consider the problem of estimating a rank-one matrix in Gaussian noise under a probabilistic model for the left and right factors of the matrix. The probabilistic model can impose constraints on the factors including sparsity and positivity that arise commonly in learning problems. We propose a family of algorithms that reduce the problem to a sequence of scalar estimation computations. These algorithms are similar to approximate message passing techniques based on Gaussian approximations of loopy belief propagation that have been used recently in compressed sensing. Leveraging analysis methods by Bayati and Montanari, we show that the asymptotic behavior of the algorithm is described by a simple scalar equivalent model, where the distribution of the estimates at each iteration is identical to certain scalar estimates of the variables in Gaussian noise. Moreover, the effective Gaussian noise level is described by a set of state evolution equations. The proposed approach to deriving algorithms thus provides a computationally simple and general method for rank-one estimation problems with a precise analysis in certain high-dimensional settings.
A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs
Venue: arXiv cs.DS 2015
Year: 2015

The NP-complete Permutation Pattern Matching problem asks whether a $k$-permutation $P$ is contained in a $n$-permutation $T$ as a pattern. This is the case if there exists an order-preserving embedding of $P$ into $T$. In this paper, we present a fixed-parameter algorithm solving this problem with a worst-case runtime of $\mathcal{O}(1.79^{\mathsf{run}(T)}\cdot n\cdot k)$, where $\mathsf{run}(T)$ denotes the number of alternating runs of $T$. This algorithm is particularly well-suited for instances where $T$ has few runs, i.e., few ups and downs. Moreover, since $\mathsf{run}(T)<n$, this can be seen as a $\mathcal{O}(1.79^{n}\cdot n\cdot k)$ algorithm which is the first to beat the exponential $2^n$ runtime of brute-force search. Furthermore, we prove that under standard complexity theoretic assumptions such a fixed-parameter tractability result is not possible for $\mathsf{run}(P)$.
On the Complexity of Finding Second-Best Abductive Explanations
Venue: arXiv cs.LO 2015
Year: 2015

While looking for abductive explanations of a given set of manifestations, an ordering between possible solutions is often assumed. The complexity of finding/verifying optimal solutions is already known. In this paper we consider the computational complexity of finding second-best solutions. We consider different orderings, and consider also different possible definitions of what a second-best solution is.
Tight Bounds for Low Dimensional Star Stencils in the Parallel External Memory Model
Venue: arXiv cs.CC 2015
Year: 2015

Stencil computations on low dimensional grids are kernels of many scientific applications including finite difference methods used to solve partial differential equations. On typical modern computer architectures, such stencil computations are limited by the performance of the memory subsystem, namely by the bandwidth between main memory and the cache. This work considers the computation of star stencils, like the 5-point and 7-point stencil, in the external memory model and parallel external memory model and analyses the constant of the leading term of the non-compulsory I/Os. While optimizing stencil computations is an active field of research, there has been a significant gap between the lower bounds and the performance of the algorithms so far. In two dimensions, this work provides matching constants for lower and upper bounds closing a multiplicative gap of 4. In three dimensions, the bounds match up to a factor of $\sqrt{2}$ improving the known results by a factor of $2 \sqrt{3}\sqrt{B}$, where $B$ is the block (cache line) size of the external memory model. For dimensions $d\geq 4$, the lower bound is improved between a factor of $4$ and $6$. For arbitrary dimension~$d$, the first analysis of the constant of the leading term of the non-compulsory I/Os is presented. For $d\geq 3$ the lower and upper bound match up to a factor of $\sqrt[d-1]{d!}\approx \frac{d}{e}$.
Unique Parallel Decomposition in Branching and Weak Bisimulation Semantics
Venue: arXiv cs.LO 2015
Year: 2015

We consider the property of unique parallel decomposition modulo branching and weak bisimilarity. First, we show that infinite behaviours may fail to have parallel decompositions at all. Then, we prove that totally normed behaviours always have parallel decompositions, but that these are not necessarily unique. Finally, we establish that weakly bounded behaviours have unique parallel decompositions. We derive the latter result from a general theorem about unique decompositions in partial commutative monoids.
Algorithmic randomness and stochastic selection function
Venue: arXiv cs.IT 2015
Year: 2015

We show algorithmic randomness versions of the two classical theorems on subsequences of normal numbers. One is Kamae-Weiss theorem (Kamae 1973) on normal numbers, which characterize the selection function that preserves normal numbers. Another one is the Steinhaus (1922) theorem on normal numbers, which characterize the normality from their subsequences. In van Lambalgen (1987), an algorithmic analogy to Kamae-Weiss theorem is conjectured in terms of algorithmic randomness and complexity. In this paper we consider two types of algorithmic random sequence; one is ML-random sequences and the other one is the set of sequences that have maximal complexity rate. Then we show algorithmic randomness versions of corresponding theorems to the above classical results.
Robust frequency offset estimator for OFDM over fast varying multipath channel
Venue: arXiv cs.IT 2015
Year: 2015

This paper presents a robust carrier frequency offset(CFO) estimation algorithm suitable for fast varying multipath channels. The proposed algorithm estimates CFO both in time-domain and frequency-domain using two carefully designed sequences. This novel technique possesses high accuracy as well as large estimation range and works well in fast varying channels.
Power Series Solution to Non-Linear Partial Differential equations of Mathematical Physics
Venue: arXiv cs.SC 2015
Year: 2015

Power Series Solution method has been used traditionally for to solve Linear Differential Equations, in Ordinary and Partial form. But this method has been limited to this kind of problems. We present the solution of problems of Non Linear Partial Differential equations of Physical Mathematical using power series.
The Parameterized Complexity of Domination-type Problems and Application to Linear Codes
Venue: arXiv cs.CC 2015
Year: 2015

We study the parameterized complexity of domination-type problems. (sigma,rho)-domination is a general and unifying framework introduced by Telle: a set D of vertices of a graph G is (sigma,rho)-dominating if for any v in D, |N(v)\cap D| in sigma and for any $v\notin D, |N(v)\cap D| in rho. We mainly show that for any sigma and rho the problem of (sigma,rho)-domination is W[2] when parameterized by the size of the dominating set. This general statement is optimal in the sense that several particular instances of (sigma,rho)-domination are W[2]-complete (e.g. Dominating Set). We also prove that (sigma,rho)-domination is W[2] for the dual parameterization, i.e. when parameterized by the size of the dominated set. We extend this result to a class of domination-type problems which do not fall into the (sigma,rho)-domination framework, including Connected Dominating Set. We also consider problems of coding theory which are related to domination-type problems with parity constraints. In particular, we prove that the problem of the minimal distance of a linear code over Fq is W[2] for both standard and dual parameterizations, and W[1]-hard for the dual parameterization. To prove W[2]-membership of the domination-type problems we extend the Turing-way to parameterized complexity by introducing a new kind of non deterministic Turing machine with the ability to perform `blind' transitions, i.e. transitions which do not depend on the content of the tapes. We prove that the corresponding problem Short Blind Multi-Tape Non-Deterministic Turing Machine is W[2]-complete. We believe that this new machine can be used to prove W[2]-membership of other problems, not necessarily related to domination