OpenRaiser/Intern-Atlas huggingface dataset:
Conditional Information Inequalities and Combinatorial Applications
Venue: arXiv cs.IT 2017
Year: 2017

We show that the inequality $H(A \mid B,X) + H(A \mid B,Y) \le H(A\mid B)$ for jointly distributed random variables $A,B,X,Y$, which does not hold in general case, holds under some natural condition on the support of the probability distribution of $A,B,X,Y$. This result generalizes a version of the conditional Ingleton inequality: if for some distribution $I(X: Y \mid A) = H(A\mid X,Y)=0$, then $I(A : B) \le I(A : B \mid X) + I(A: B \mid Y) + I(X : Y)$. We present two applications of our result. The first one is the following easy-to-formulate combinatorial theorem: assume that the edges of a bipartite graph are partitioned into $K$ matchings such that for each pair (left vertex $x$, right vertex $y$) there is at most one matching in the partition involving both $x$ and $y$; assume further that the degree of each left vertex is at least $L$ and the degree of each right vertex is at least $R$. Then $K\ge LR$. The second application is a new method to prove lower bounds for biclique coverings of bipartite graphs.
Real Polynomial Root-finding by Means of Matrix and Polynomial Iterations
Venue: arXiv cs.SC 2017
Year: 2017

Univariate polynomial root-finding is a classical subject, still important for modern computing. Frequently one seeks just the real roots of a polynomial with real coefficients. They can be approximated at a low computational cost if the polynomial has no nonreal roots, but for high degree polynomials, nonreal roots are typically much more numerous than the real ones. The challenge is known for a long time, and the subject has been intensively studied. Nevertheless, we produce some novel ideas and techniques and obtain dramatic acceleration of the known algorithms. In order to achieve our progress we exploit the correlation between the computations with matrices and polynomials, randomized matrix computations, and complex plane geometry, extend the techniques of the matrix sign iterations, and use the structure of the companion matrix of the input polynomial. The results of our extensive tests with benchmark polynomials and random matrices are quite encouraging. In particular in our tests the number of iterations required for convergence of our algorithms grew very slowly (if at all) as we increased the degree of the univariate input polynomials and the dimension of the input matrices from 64 to 1024.
Sampling Constrained Asynchronous Communication: How to Sleep Efficiently
Venue: arXiv cs.IT 2017
Year: 2017

The minimum energy, and, more generally, the minimum cost, to transmit one bit of information has been recently derived for bursty communication when information is available infrequently at random times at the transmitter. Furthermore, it has been shown that even if the receiver is constrained to sample only a fraction $ρ\in (0,1]$ of the channel outputs, there is no capacity penalty. That is, for any strictly positive sampling rate $ρ>0$, the asynchronous capacity per unit cost is the same as under full sampling, i.e., when $ρ=1$. Moreover, there is no penalty in terms of decoding delay. The above results are asymptotic in nature, considering the limit as the number $B$ of bits to be transmitted tends to infinity, while the sampling rate $ρ$ remains fixed. A natural question is then whether the sampling rate $ρ(B)$ can drop to zero without introducing a capacity (or delay) penalty compared to full sampling. We answer this question affirmatively. The main result of this paper is an essentially tight characterization of the minimum sampling rate. We show that any sampling rate that grows at least as fast as $ω(1/B)$ is achievable, while any sampling rate smaller than $o(1/B)$ yields unreliable communication. The key ingredient in our improved achievability result is a new, multi-phase adaptive sampling scheme for locating transient changes, which we believe may be of independent interest for certain change-point detection problems.
High Dimensional Low Rank plus Sparse Matrix Decomposition
Venue: arXiv cs.NA 2017
Year: 2017

This paper is concerned with the problem of low rank plus sparse matrix decomposition for big data. Conventional algorithms for matrix decomposition use the entire data to extract the low-rank and sparse components, and are based on optimization problems with complexity that scales with the dimension of the data, which limits their scalability. Furthermore, existing randomized approaches mostly rely on uniform random sampling, which is quite inefficient for many real world data matrices that exhibit additional structures (e.g. clustering). In this paper, a scalable subspace-pursuit approach that transforms the decomposition problem to a subspace learning problem is proposed. The decomposition is carried out using a small data sketch formed from sampled columns/rows. Even when the data is sampled uniformly at random, it is shown that the sufficient number of sampled columns/rows is roughly O(rμ), where μis the coherency parameter and r the rank of the low rank component. In addition, adaptive sampling algorithms are proposed to address the problem of column/row sampling from structured data. We provide an analysis of the proposed method with adaptive sampling and show that adaptive sampling makes the required number of sampled columns/rows invariant to the distribution of the data. The proposed approach is amenable to online implementation and an online scheme is proposed.
Belief Revision, Minimal Change and Relaxation: A General Framework based on Satisfaction Systems, and Applications to Description Logics
Venue: arXiv cs.AI 2017
Year: 2017

Belief revision of knowledge bases represented by a set of sentences in a given logic has been extensively studied but for specific logics, mainly propositional, and also recently Horn and description logics. Here, we propose to generalize this operation from a model-theoretic point of view, by defining revision in an abstract model theory known under the name of satisfaction systems. In this framework, we generalize to any satisfaction systems the characterization of the well known AGM postulates given by Katsuno and Mendelzon for propositional logic in terms of minimal change among interpretations. Moreover, we study how to define revision, satisfying the AGM postulates, from relaxation notions that have been first introduced in description logics to define dissimilarity measures between concepts, and the consequence of which is to relax the set of models of the old belief until it becomes consistent with the new pieces of knowledge. We show how the proposed general framework can be instantiated in different logics such as propositional, first-order, description and Horn logics. In particular for description logics, we introduce several concrete relaxation operators tailored for the description logic $\ALC{}$ and its fragments $\EL{}$ and $\ELext{}$, discuss their properties and provide some illustrative examples.
Reachability is in DynFO
Venue: arXiv cs.LO 2017
Year: 2017

Patnaik and Immerman introduced the dynamic complexity class DynFO of database queries that can be maintained by first-order dynamic programs with the help of auxiliary relations under insertions and deletions of edges (Patnaik and Immerman 1997). This article confirms their conjecture that the Reachability query is in DynFO. As a byproduct it is shown that the rank of a matrix with small values can be maintained in DynFO(+,x). It is further shown that the (size of the) maximum matching of a graph can be maintained in non-uniform DynFO, another extension of DynFO, with non-uniform initialisation of the auxiliary relations.
Models and Information Rates for Wiener Phase Noise Channels
Venue: arXiv cs.IT 2017
Year: 2017

A waveform channel is considered where the transmitted signal is corrupted by Wiener phase noise and additive white Gaussian noise. A discrete-time channel model that takes into account the effect of filtering on the phase noise is developed. The model is based on a multi-sample receiver, i.e., an integrate-and-dump filter whose output is sampled at a rate higher than the signaling rate. It is shown that, at high Signal-to-Noise Ratio (SNR), the multi-sample receiver achieves a rate that grows logarithmically with the SNR if the number of samples per symbol (oversampling factor) grows with the cubic root of the SNR. Moreover, the pre-log factor is at least 1/2 and can be achieved by amplitude modulation. For an approximate discrete-time model of the multi-sample receiver, the capacity pre-log at high SNR is shown to be at least 3/4 if the number of samples per symbol grows with the square root of the SNR. The analysis shows that phase modulation achieves a pre-log of at least 1/4 while amplitude modulation still achieves a pre-log of 1/2. This is strictly greater than the capacity pre-log of the (approximate) discrete-time Wiener phase noise channel with only one sample per symbol, which is 1/2. Numerical simulations are used to compute lower bounds on the information rates achieved by the multi-sample receiver. The simulations show that oversampling is beneficial for both strong and weak phase noise at high SNR. In fact, the information rates are sometimes substantially larger than when using commonly-used approximate discrete-time models.
Two-Player Tower of Hanoi
Venue: arXiv cs.GT 2017
Year: 2017

The Tower of Hanoi game is a classical puzzle in recreational mathematics (Lucas 1883) which also has a strong record in pure mathematics. In a borderland between these two areas we find the characterization of the minimal number of moves, which is $2^n-1$, to transfer a tower of $n$ disks. But there are also other variations to the game, involving for example real number weights on the moves of the disks. This gives rise to a similar type of problem, but where the final score seeks to be optimized. We study extensions of the one-player setting to two players, invoking classical winning conditions in combinatorial game theory such as the player who moves last wins, or the highest score wins. Here we solve both these winning conditions on three heaps.
Modeling and Energy Optimization of LDPC Decoder Circuits with Timing Violations
Venue: arXiv cs.IT 2017
Year: 2017

This paper proposes a "quasi-synchronous" design approach for signal processing circuits, in which timing violations are permitted, but without the need for a hardware compensation mechanism. The case of a low-density parity-check (LDPC) decoder is studied, and a method for accurately modeling the effect of timing violations at a high level of abstraction is presented. The error-correction performance of code ensembles is then evaluated using density evolution while taking into account the effect of timing faults. Following this, several quasi-synchronous LDPC decoder circuits based on the offset min-sum algorithm are optimized, providing a 23%-40% reduction in energy consumption or energy-delay product, while achieving the same performance and occupying the same area as conventional synchronous circuits.
The Graph Motif problem parameterized by the structure of the input graph
Venue: arXiv cs.DS 2017
Year: 2017

The Graph Motif problem was introduced in 2006 in the context of biological networks. It consists of deciding whether or not a multiset of colors occurs in a connected subgraph of a vertex-colored graph. Graph Motif has been mostly analyzed from the standpoint of parameterized complexity. The main parameters which came into consideration were the size of the multiset and the number of colors. Though, in the many applications of Graph Motif, the input graph originates from real-life and has structure. Motivated by this prosaic observation, we systematically study its complexity relatively to graph structural parameters. For a wide range of parameters, we give new or improved FPT algorithms, or show that the problem remains intractable. For the FPT cases, we also give some kernelization lower bounds as well as some ETH-based lower bounds on the worst case running time. Interestingly, we establish that Graph Motif is W[1]-hard (while in W[P]) for parameter max leaf number, which is, to the best of our knowledge, the first problem to behave this way.
Minimal Reachability Problems
Venue: arXiv cs.SY 2017
Year: 2017

In this paper, we address a collection of state space reachability problems, for linear time-invariant systems, using a minimal number of actuators. In particular, we design a zero-one diagonal input matrix B, with a minimal number of non-zero entries, so that a specified state vector is reachable from a given initial state. Moreover, we design a B so that a system can be steered either into a given subspace, or sufficiently close to a desired state. This work extends the recent results of Olshevsky and Pequito, where a zero-one diagonal or column matrix B is constructed so that the involved system is controllable. Specifically, we prove that the first two of our aforementioned problems are NP-hard; these results hold for a zero-one column matrix B as well. Then, we provide efficient polynomial time algorithms for their general solution, along with their worst case approximation guarantees. Finally, we illustrate their performance over large random networks.
Comparing Graphs via Persistence Distortion
Venue: arXiv cs.CG 2017
Year: 2017

Metric graphs are ubiquitous in science and engineering. For example, many data are drawn from hidden spaces that are graph-like, such as the cosmic web. A metric graph offers one of the simplest yet still meaningful ways to represent the non-linear structure hidden behind the data. In this paper, we propose a new distance between two finite metric graphs, called the persistence-distortion distance, which draws upon a topological idea. This topological perspective along with the metric space viewpoint provide a new angle to the graph matching problem. Our persistence-distortion distance has two properties not shared by previous methods: First, it is stable against the perturbations of the input graph metrics. Second, it is a continuous distance measure, in the sense that it is defined on an alignment of the underlying spaces of input graphs, instead of merely their nodes. This makes our persistence-distortion distance robust against, for example, different discretizations of the same underlying graph. Despite considering the input graphs as continuous spaces, that is, taking all points into account, we show that we can compute the persistence-distortion distance in polynomial time. The time complexity for the discrete case where only graph nodes are considered is much faster. We also provide some preliminary experimental results to demonstrate the use of the new distance measure.
Equivalence of Deterministic Top-Down Tree-to-String Transducers is Decidable
Venue: arXiv cs.FL 2017
Year: 2017

We show that equivalence of deterministic top-down tree-to-string transducers is decidable, thus solving a long standing open problem in formal language theory. We also present efficient algorithms for subclasses: polynomial time for total transducers with unary output alphabet (over a given top-down regular domain language), and co-randomized polynomial time for linear transducers; these results are obtained using techniques from multi-linear algebra. For our main result, we prove that equivalence can be certified by means of inductive invariants using polynomial ideals. This allows us to construct two semi-algorithms, one searching for a proof of equivalence, one for a witness of non-equivalence. Furthermore, we extend our result to deterministic top-down tree-to-string transducers which produce output not in a free monoid but in a free group.
Adaptive Diffusion Schemes for Heterogeneous Networks
Venue: arXiv cs.SY 2017
Year: 2017

In this paper, we deal with distributed estimation problems in diffusion networks with heterogeneous nodes, i.e., nodes that either implement different adaptive rules or differ in some other aspect such as the filter structure or length, or step size. Although such heterogeneous networks have been considered from the first works on diffusion networks, obtaining practical and robust schemes to adaptively adjust the combiners in different scenarios is still an open problem. In this paper, we study a diffusion strategy specially designed and suited to heterogeneous networks. Our approach is based on two key ingredients: 1) the adaptation and combination phases are completely decoupled, so that network nodes keep purely local estimations at all times; and 2) combiners are adapted to minimize estimates of the network mean-square-error. Our scheme is compared with the standard Adapt-then-Combine scheme and theoretically analyzed using energy conservation arguments. Several experiments involving networks with heterogeneous nodes show that the proposed decoupled Adapt-then-Combine approach with adaptive combiners outperforms other state-of-the-art techniques, becoming a competitive approach in these scenarios.
A Linear Time Algorithm for the $3$-neighbour Traveling Salesman Problem on Halin graphs and extensions
Venue: arXiv cs.DM 2017
Year: 2017

The Quadratic Travelling Salesman Problem (QTSP) is to find a least cost Hamilton cycle in an edge-weighted graph, where costs are defined on all pairs of edges contained in the Hamilton cycle. This is a more general version than the commonly studied QTSP which only considers pairs of adjacent edges. We define a restricted version of QTSP, the $k$-neighbour TSP (TSP($k$)), and give a linear time algorithm to solve TSP($k$) on a Halin graph for $k\leq 3$. This algorithm can be extended to solve TSP($k$) on any fully reducible class of graphs for any fixed $k$ in polynomial time. This result generalizes corresponding results for the standard TSP. TSP($k$) can be used to model various machine scheduling problems as well as an optimal routing problem for unmanned aerial vehicles (UAVs).
Evaluating Cartogram Effectiveness
Venue: arXiv cs.HC 2017
Year: 2017

Cartograms are maps in which areas of geographic regions (countries, states) appear in proportion to some variable of interest (population, income). Cartograms are popular visualizations for geo-referenced data that have been used for over a century and that make it possible to gain insight into patterns and trends in the world around us. Despite the popularity of cartograms and the large number of cartogram types, there are few studies evaluating the effectiveness of cartograms in conveying information. Based on a recent task taxonomy for cartograms, we evaluate four major different types of cartograms: contiguous, non-contiguous, rectangular, and Dorling cartograms. Specifically, we evaluate the effectiveness of these cartograms by quantitative performance analysis, as well as by subjective preferences. We analyze the results of our study in the context of some prevailing assumptions in the literature of cartography and cognitive science. Finally, we make recommendations for the use of different types of cartograms for different tasks and settings.
Bibliometric author evaluation through linear regression on the coauthor network
Venue: arXiv cs.DL 2017
Year: 2017

The rising trend of coauthored academic works obscures the credit assignment that is the basis for decisions of funding and career advancements. In this paper, a simple model based on the assumption of an unvarying "author ability" is introduced. With this assumption, the weight of author contributions to a body of coauthored work can be statistically estimated. The method is tested on a set of some more than five-hundred authors in a coauthor network from the CiteSeerX database. The ranking obtained agrees fairly well with that given by total fractional citation counts for an author, but noticeable differences exist.
A new characterization of complete Heyting and co-Heyting algebras
Venue: arXiv cs.LO 2017
Year: 2017

We give a new order-theoretic characterization of a complete Heyting and co-Heyting algebra $C$. This result provides an unexpected relationship with the field of Nash equilibria, being based on the so-called Veinott ordering relation on subcomplete sublattices of $C$, which is crucially used in Topkis' theorem for studying the order-theoretic stucture of Nash equilibria of supermodular games.
Deleting edges to restrict the size of an epidemic
Venue: arXiv cs.DS 2017
Year: 2017

Motivated by applications in network epidemiology, we consider the problem of determining whether it is possible to delete at most $k$ edges from a given input graph (of small treewidth) so that the resulting graph avoids a set $\mathcal{F}$ of forbidden subgraphs; of particular interest is the problem of determining whether it is possible to delete at most $k$ edges so that the resulting graph has no connected component of more than $h$ vertices, as this bounds the worst-case size of an epidemic. While even this special case of the problem is NP-complete in general (even when $h=3$), we provide evidence that many of the real-world networks of interest are likely to have small treewidth, and we describe an algorithm which solves the general problem in time \genruntime ~on an input graph having $n$ vertices and whose treewidth is bounded by a fixed constant $w$, if each of the subgraphs we wish to avoid has at most $r$ vertices. For the special case in which we wish only to ensure that no component has more than $h$ vertices, we improve on this to give an algorithm running in time $O((wh)^{2w}n)$, which we have implemented and tested on real datasets based on cattle movements.
Broadcast Channels with Privacy Leakage Constraints
Venue: arXiv cs.IT 2017
Year: 2017

The broadcast channel (BC) with one common and two private messages with leakage constraints is studied, where leakage rate refers to the normalized mutual information between a message and a channel symbol string. Each private message is destined for a different user and the leakage rate to the other receiver must satisfy a constraint. This model captures several scenarios concerning secrecy, i.e., when both, either or neither of the private messages are secret. Inner and outer bounds on the leakage-capacity region are derived when the eavesdropper knows the codebook. The inner bound relies on a Marton-like code construction and the likelihood encoder. A Uniform Approximation Lemma is established that states that the marginal distribution induced by the encoder on each of the bins in the Marton codebook is approximately uniform. Without leakage constraints the inner bound recovers Marton's region and the outer bound reduces to the UVW-outer bound. The bounds match for semi-deterministic (SD) and physically degraded (PD) BCs, as well as for BCs with a degraded message set. The leakage-capacity regions of the SD-BC and the BC with a degraded message set recover past results for different secrecy scenarios. A Blackwell BC example illustrates the results and shows how its leakage-capacity region changes from the capacity region without secrecy to the secrecy-capacity regions for different secrecy scenarios.