OpenRaiser/Intern-Atlas huggingface dataset:
The Dirty MIMO Multiple-Access Channel
Venue: arXiv cs.IT 2017
Year: 2017

In the scalar dirty multiple-access channel, in addition to Gaussian noise, two additive interference signals are present, each known non-causally to a single transmitter. It was shown by Philosof et al. that for strong interferences, an i.i.d. ensemble of codes does not achieve the capacity region. Rather, a structured-codes approach was presented, that was shown to be optimal in the limit of high signal-to-noise ratios, where the sum-capacity is dictated by the minimal ("bottleneck") channel gain. In this paper, we consider the multiple-input multiple-output (MIMO) variant of this setting. In order to incorporate structured codes in this case, one can utilize matrix decompositions that transform the channel into effective parallel scalar dirty multiple-access channels. This approach however suffers from a "bottleneck" effect for each effective scalar channel and therefore the achievable rates strongly depend on the chosen decomposition. It is shown that a recently proposed decomposition, where the diagonals of the effective channel matrices are equal up to a scaling factor, is optimal at high signal-to-noise ratios, under an equal rank assumption. This approach is then extended to any number of transmitters. Finally, an application to physical-layer network coding for the MIMO two-way relay channel is presented.
Bounds on Variance for Unimodal Distributions
Venue: arXiv cs.IT 2017
Year: 2017

We show a direct relationship between the variance and the differential entropy for subclasses of symmetric and asymmetric unimodal distributions by providing an upper bound on variance in terms of entropy power. Combining this bound with the well-known entropy power lower bound on variance, we prove that the variance of the appropriate subclasses of unimodal distributions can be bounded below and above by the scaled entropy power. As differential entropy decreases, the variance is sandwiched between two exponentially decreasing functions in the differential entropy. This establishes that for the subclasses of unimodal distributions, the differential entropy can be used as a surrogate for concentration of the distribution.
Structure theory of flip graphs with applications to Weak Symmetry Breaking
Venue: arXiv cs.DC 2017
Year: 2017

This paper is devoted to advancing the theoretical understanding of the iterated immediate snapshot (IIS) complexity of the Weak Symmetry Breaking task (WSB). Our rather unexpected main theorem states that there exist infinitely many values of n, such that WSB for n~processes is solvable by a certain explicitly constructed 3-round IIS protocol. In particular, the minimal number of rounds, which an IIS protocol needs in order to solve the WSB task, does not go to infinity, when the number of processes goes to infinity. Our methods can also be used to generate such values of n. We phrase our proofs in combinatorial language, while avoiding using topology. To this end, we study a~certain class of graphs, which we call flip graphs. These graphs encode adjacency structure in certain subcomplexes of iterated standard chromatic subdivisions of a simplex. While keeping the geometric background in mind for an additional intuition, we develop the structure theory of matchings in flip graphs in a purely combinatorial way. Our bound for the IIS complexity is then a corollary of this general theory. As an afterthought of our result, we suggest to change the overall paradigm. Specifically, we think, that the bounds on the IIS complexity of solving WSB for n processes should be formulated in terms of the size of the solutions of the associated Diophantine equation, rather than in terms of the value n itself.
A correction on Shiloach's algorithm for minimum linear arrangement of trees
Venue: arXiv cs.DS 2017
Year: 2017

More than 30 years ago, Shiloach published an algorithm to solve the minimum linear arrangement problem for undirected trees. Here we fix a small error in the original version of the algorithm and discuss its effect on subsequent literature. We also improve some aspects of the notation.
Optimised determinisation and completion of finite tree automata
Venue: arXiv cs.FL 2017
Year: 2017

Determinisation and completion of finite tree automata are important operations with applications in program analysis and verification. However, the complexity of the classical procedures for determinisation and completion is high. They are not practical procedures for manipulating tree automata beyond very small ones. In this paper we develop an algorithm for determinisation and completion of finite tree automata, whose worst-case complexity remains unchanged, but which performs far better than existing algorithms in practice. The critical aspect of the algorithm is that the transitions of the determinised (and possibly completed) automaton are generated in a potentially very compact form called product form, which can reduce the size of the representation dramatically. Furthermore, the representation can often be used directly when manipulating the determinised automaton. The paper contains an experimental evaluation of the algorithm on a large set of tree automata examples.
Information exchange on an academic social networking site: A multidiscipline comparison on researchgate Q&A
Venue: arXiv cs.SI 2017
Year: 2017

The increasing popularity of academic social networking sites (ASNSs) requires studies on the usage of ASNSs among scholars and evaluations of the effectiveness of these ASNSs. However, it is unclear whether current ASNSs have fulfilled their design goal, as scholars' actual online interactions on these platforms remain unexplored. To fill the gap, this article presents a study based on data collected from ResearchGate. Adopting a mixed-method design by conducting qualitative content analysis and statistical analysis on 1,128 posts collected from ResearchGate Q&A, we examine how scholars exchange information and resources, and how their practices vary across three distinct disciplines: library and information services, history of art, and astrophysics. Our results show that the effect of a questioner's intention (i.e., seeking information or discussion) is greater than disciplinary factors in some circumstances. Across the three disciplines, responses to questions provide various resources, including experts' contact details, citations, links to Wikipedia, images, and so on. We further discuss several implications of the understanding of scholarly information exchange and the design of better academic social networking interfaces, which should stimulate scholarly interactions by minimizing confusion, improving the clarity of questions, and promoting scholarly content management.
Membership in moment polytopes is in NP and coNP
Venue: arXiv cs.CC 2017
Year: 2017

We show that the problem of deciding membership in the moment polytope associated with a finite-dimensional unitary representation of a compact, connected Lie group is in NP and coNP. This is the first non-trivial result on the computational complexity of this problem, which naively amounts to a quadratically-constrained program. Our result applies in particular to the Kronecker polytopes, and therefore to the problem of deciding positivity of the stretched Kronecker coefficients. In contrast, it has recently been shown that deciding positivity of a single Kronecker coefficient is NP-hard in general [Ikenmeyer, Mulmuley and Walter, arXiv:1507.02955]. We discuss the consequences of our work in the context of complexity theory and the quantum marginal problem.
Sequential Optimization for Efficient High-Quality Object Proposal Generation
Venue: arXiv cs.CV 2017
Year: 2017

We are motivated by the need for a generic object proposal generation algorithm which achieves good balance between object detection recall, proposal localization quality and computational efficiency. We propose a novel object proposal algorithm, BING++, which inherits the virtue of good computational efficiency of BING but significantly improves its proposal localization quality. At high level we formulate the problem of object proposal generation from a novel probabilistic perspective, based on which our BING++ manages to improve the localization quality by employing edges and segments to estimate object boundaries and update the proposals sequentially. We propose learning the parameters efficiently by searching for approximate solutions in a quantized parameter space for complexity reduction. We demonstrate the generalization of BING++ with the same fixed parameters across different object classes and datasets. Empirically our BING++ can run at half speed of BING on CPU, but significantly improve the localization quality by 18.5% and 16.7% on both VOC2007 and Microhsoft COCO datasets, respectively. Compared with other state-of-the-art approaches, BING++ can achieve comparable performance, but run significantly faster.
Analysis of Massive MIMO-Enabled Downlink Wireless Backhauling for Full-Duplex Small Cells
Venue: arXiv cs.IT 2017
Year: 2017

Using tools from stochastic geometry, we develop a framework to model the downlink rate coverage probability of a user in a given small cell network (SCN) with massive MIMO-enabled wireless backhauls. The considered SCN is composed of a mixture of small cells that are configured in either in-band or out-of-band backhaul modes with a certain probability. The performance of the user in the considered hierarchical network is limited by several sources of interference such as the backhaul interference, small cell base station (SBS)-to-SBS interference and the SI. Moreover, due to the channel hardening effect in massive MIMO, the backhaul links experience long term channel effects only, whereas the access links experience both the long term and short term channel effects. Consequently, the developed framework is flexible to characterize different sources of interference while capturing the heterogeneity of the access and backhaul channels. In specific scenarios, the framework enables deriving closed-form coverage probability expressions. Under perfect backhaul coverage, the simplified expressions are utilized to optimize the proportion of in-band and out-of-band small cells in the SCN in closed-form. Finally, few remedial solutions are proposed that can potentially mitigate the backhaul interference and in turn improve the performance of in-band FD wireless backhauling. Numerical results investigate the scenarios in which in-band wireless backhauling is useful and demonstrate that maintaining a correct proportion of in-band and out-of-band FD small cells is crucial in wireless backhauled SCNs.
Distributed Event-based State Estimation
Venue: arXiv cs.SY 2017
Year: 2017

An event-based state estimation approach for reducing communication in a networked control system is proposed. Multiple distributed sensor-actuator-agents observe a dynamic process and sporadically exchange their measurements and inputs over a bus network. Based on these data, each agent estimates the full state of the dynamic system, which may exhibit arbitrary inter-agent couplings. Local event-based protocols ensure that data is transmitted only when necessary to meet a desired estimation accuracy. This event-based scheme is shown to mimic a centralized Luenberger observer design up to guaranteed bounds, and stability is proven in the sense of bounded estimation errors for bounded disturbances. The stability result extends to the distributed control system that results when the local state estimates are used for distributed feedback control. Simulation results highlight the benefit of the event-based approach over classical periodic ones in reducing communication requirements.
On the interplay of network structure and gradient convergence in deep learning
Venue: arXiv cs.LG 2017
Year: 2017

The regularization and output consistency behavior of dropout and layer-wise pretraining for learning deep networks have been fairly well studied. However, our understanding of how the asymptotic convergence of backpropagation in deep architectures is related to the structural properties of the network and other design choices (like denoising and dropout rate) is less clear at this time. An interesting question one may ask is whether the network architecture and input data statistics may guide the choices of learning parameters and vice versa. In this work, we explore the association between such structural, distributional and learnability aspects vis-à-vis their interaction with parameter convergence rates. We present a framework to address these questions based on convergence of backpropagation for general nonconvex objectives using first-order information. This analysis suggests an interesting relationship between feature denoising and dropout. Building upon these results, we obtain a setup that provides systematic guidance regarding the choice of learning parameters and network sizes that achieve a certain level of convergence (in the optimization sense) often mediated by statistical attributes of the inputs. Our results are supported by a set of experimental evaluations as well as independent empirical observations reported by other groups.
Comparative Design, Scaling, and Control of Appendages for Inertial Reorientation
Venue: arXiv cs.RO 2017
Year: 2017

This paper develops a comparative framework for the design of actuated inertial appendages for planar, aerial reorientation. We define the Inertial Reorientation template, the simplest model of this behavior, and leverage its linear dynamics to reveal the design constraints linking a task with the body designs capable of completing it. As practicable inertial appendage designs lead to morphology that is generally more complex, we advance a notion of "anchoring" whereby a judicious choice of physical design in concert with an appropriate control policy yields a system whose closed loop dynamics are sufficiently captured by the template as to permit all further design to take place in its far simpler parameter space. This approach is effective and accurate over the diverse design spaces afforded by existing platforms, enabling performance comparison through the shared task space. We analyze examples from the literature and find advantages to each body type, but conclude that tails provide the highest potential performance for reasonable designs. Thus motivated, we build a physical example by retrofitting a tail to a RHex robot and present empirical evidence of its efficacy.
Efficient Sum of Outer Products Dictionary Learning (SOUP-DIL) and Its Application to Inverse Problems
Venue: arXiv cs.LG 2017
Year: 2017

The sparsity of signals in a transform domain or dictionary has been exploited in applications such as compression, denoising and inverse problems. More recently, data-driven adaptation of synthesis dictionaries has shown promise compared to analytical dictionary models. However, dictionary learning problems are typically non-convex and NP-hard, and the usual alternating minimization approaches for these problems are often computationally expensive, with the computations dominated by the NP-hard synthesis sparse coding step. This paper exploits the ideas that drive algorithms such as K-SVD, and investigates in detail efficient methods for aggregate sparsity penalized dictionary learning by first approximating the data with a sum of sparse rank-one matrices (outer products) and then using a block coordinate descent approach to estimate the unknowns. The resulting block coordinate descent algorithms involve efficient closed-form solutions. Furthermore, we consider the problem of dictionary-blind image reconstruction, and propose novel and efficient algorithms for adaptive image reconstruction using block coordinate descent and sum of outer products methodologies. We provide a convergence study of the algorithms for dictionary learning and dictionary-blind image reconstruction. Our numerical experiments show the promising performance and speed-ups provided by the proposed methods over previous schemes in sparse data representation and compressed sensing-based image reconstruction.
Longest Gapped Repeats and Palindromes
Venue: arXiv cs.DS 2017
Year: 2017

A gapped repeat (respectively, palindrome) occurring in a word $w$ is a factor $uvu$ (respectively, $u^Rvu$) of $w$. In such a repeat (palindrome) $u$ is called the arm of the repeat (respectively, palindrome), while $v$ is called the gap. We show how to compute efficiently, for every position $i$ of the word $w$, the longest gapped repeat and palindrome occurring at that position, provided that the length of the gap is subject to various types of restrictions. That is, that for each position $i$ we compute the longest prefix $u$ of $w[i..n]$ such that $uv$ (respectively, $u^Rv$) is a suffix of $w[1..i-1]$ (defining thus a gapped repeat $uvu$ -- respectively, palindrome $u^Rvu$), and the length of $v$ is subject to the aforementioned restrictions.
Does Gaussian Approximation Work Well for The Long-Length Polar Code Construction?
Venue: arXiv cs.IT 2017
Year: 2017

Gaussian approximation (GA) is widely used to construct polar codes. However when the code length is long, the subchannel selection inaccuracy due to the calculation error of conventional approximate GA (AGA), which uses a two-segment approximation function, results in a catastrophic performance loss. In this paper, new principles to design the GA approximation functions for polar codes are proposed. First, we introduce the concepts of polarization violation set (PVS) and polarization reversal set (PRS) to explain the essential reasons that the conventional AGA scheme cannot work well for the long-length polar code construction. In fact, these two sets will lead to the rank error of subsequent subchannels, which means the orders of subchannels are misaligned, which is a severe problem for polar code construction. Second, we propose a new metric, named cumulative-logarithmic error (CLE), to quantitatively evaluate the remainder approximation error of AGA in logarithm. We derive the upper bound of CLE to simplify its calculation. Finally, guided by PVS, PRS and CLE bound analysis, we propose new construction rules based on a multi-segment approximation function, which obviously improve the calculation accuracy of AGA so as to ensure the excellent performance of polar codes especially for the long code lengths. Numerical and simulation results indicate that the proposed AGA schemes are critical to construct the high-performance polar codes.
Resource Allocation and Outage Analysis for An Adaptive Cognitive Two-Way Relay Network
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, an adaptive two-way relay cooperation scheme is studied for multiple-relay cognitive radio networks to improve the performance of secondary transmissions. The power allocation and relay selection schemes are derived to minimize the secondary outage probability where only statistical channel information is needed. Exact closed-form expressions for secondary outage probability are derived under a constraint on the quality of service of primary transmissions in terms of the required primary outage probability. To better understand the impact of primary user interference on secondary transmissions, we further investigate the asymptotic behaviors of the secondary relay network including power allocation and outage probability, when the primary signal-to-noise ratio goes to infinity. Simulation results are provided to illustrate the performance of the proposed schemes.
Node-based Service-Balanced Scheduling for Provably Guaranteed Throughput and Evacuation Time Performance
Venue: arXiv cs.NI 2017
Year: 2017

This paper focuses on the design of provably efficient online link scheduling algorithms for multi-hop wireless networks. We consider single-hop traffic and the one-hop interference model. The objective is twofold: 1) maximizing the throughput when the flow sources continuously inject packets into the network, and 2) minimizing the evacuation time when there are no future packet arrivals. The prior work mostly employs the link-based approach, which leads to throughput-efficient algorithms but often does not guarantee satisfactory evacuation time performance. In this paper, we propose a novel Node-based Service-Balanced (NSB) online scheduling algorithm. NSB aims to give scheduling opportunities to heavily congested nodes in a balanced manner, by maximizing the total weight of the scheduled nodes in each scheduling cycle, where the weight of a node is determined by its workload and whether the node was scheduled in the previous scheduling cycle(s). We rigorously prove that NSB guarantees to achieve an efficiency ratio no worse (or no smaller) than 2/3 for the throughput and an approximation ratio no worse (or no greater) than 3/2 for the evacuation time. It is remarkable that NSB is both throughput-optimal and evacuation-time-optimal if the underlying network graph is bipartite. Further, we develop a lower-complexity NSB algorithm, called LC-NSB, which provides the same performance guarantees as NSB. Finally, we conduct numerical experiments to elucidate our theoretical results.
Graphs, Disjoint Matchings and Some Inequalities
Venue: arXiv cs.DM 2017
Year: 2017

For $k \geq 1$ and a graph $G$ let $ν_k(G)$ denote the size of a maximum $k$-edge-colorable subgraph of $G$. Mkrtchyan, Petrosyan and Vardanyan proved that $ν_2(G)\geq \frac45\cdot |V(G)|$, $ν_3(G)\geq \frac76\cdot |V(G)|$ for any cubic graph $G$ ~\cite{samvel:2010}. They were also able to show that if $G$ is a cubic graph, then $ν_2(G)+ν_3(G)\geq 2\cdot |V(G)|$ ~\cite{samvel:2014} and $ν_2(G) \leq \frac{|V(G)| + 2\cdot ν_3(G)}{4}$ ~\cite{samvel:2010}. In the first part of the present work, we show that the last two inequalities imply the first two of them. Moreover, we show that $ν_2(G) \geq α\cdot \frac{|V(G)| + 2\cdot ν_3(G)}{4} $, where $α=\frac{16}{17}$, if $G$ is a cubic graph, $α=\frac{20}{21}$, if $G$ is a cubic graph containing a perfect matching, $α=\frac{44}{45}$, if $G$ is a bridgeless cubic graph. We also investigate the parameters $ν_2(G)$ and $ν_3(G)$ in the class of claw-free cubic graphs. We improve the lower bounds for $ν_2(G)$ and $ν_3(G)$ for claw-free bridgeless cubic graphs to $ν_2(G)\geq \frac{35}{36}\cdot |V(G)|$ ($n \geq 48$), $ν_3(G)\geq \frac{43}{45}\cdot |E(G)|$. On the basis of these inequalities we are able to improve the coefficient $α$ for bridgeless claw-free cubic graphs. In the second part of the work, we prove lower bounds for $ν_k(G)$ in terms of $\frac{ν_{k-1}(G)+ν_{k+1}(G)}{2}$ for $k\geq 2$ and graphs $G$ containing at most $1$ cycle. We also present the corresponding conjectures for bipartite and nearly bipartite graphs.
Efficient and Provable Multi-Query Optimization
Venue: arXiv cs.DB 2017
Year: 2017

Complex queries for massive data analysis jobs have become increasingly commonplace. Many such queries contain com- mon subexpressions, either within a single query or among multiple queries submitted as a batch. Conventional query optimizers do not exploit these subexpressions and produce sub-optimal plans. The problem of multi-query optimization (MQO) is to generate an optimal combined evaluation plan by computing common subexpressions once and reusing them. Exhaustive algorithms for MQO explore an O(n^n) search space. Thus, this problem has primarily been tackled using various heuristic algorithms, without providing any theoretical guarantees on the quality of their solution. In this paper, instead of the conventional cost minimization problem, we treat the problem as maximizing a linear transformation of the cost function. We propose a greedy algorithm for this transformed formulation of the problem, which under weak, intuitive assumptions, provides an approximation factor guarantee for this formulation. We go on to show that this factor is optimal, unless P = NP. Another noteworthy point about our algorithm is that it can be easily incorporated into existing transformation-based optimizers. We finally propose optimizations which can be used to improve the efficiency of our algorithm.