OpenRaiser/Intern-Atlas huggingface dataset:
The Streaming-DMT of Fading Channels
Venue: arXiv cs.IT 2014
Year: 2014

We consider the sequential transmission of a stream of messages over a block-fading multi-input-multi-output (MIMO) channel. A new message arrives at the beginning of each coherence block, and the decoder is required to output each message sequentially, after a delay of $T$ coherence blocks. In the special case when $T=1$, the setup reduces to the quasi-static fading channel. We establish the optimal diversity-multiplexing tradeoff (DMT) in the high signal-to-noise-ratio (SNR) regime, and show that it equals $T$ times the DMT of the quasi-static channel. The converse is based on utilizing the delay constraint to amplify a local outage event associated with a message, globally across all the coherence blocks. This approach appears to be new. We propose two coding schemes that achieve the optimal DMT. The first scheme involves interleaving of messages, such that each message is transmitted across $T$ consecutive coherence blocks. This scheme requires the knowledge of the delay constraint at both the encoder and decoder. Our second coding scheme involves a sequential tree code and is delay-universal i.e., the knowledge of the decoding delay is not required by the encoder. However, in this scheme we require the coherence block-length to increase as $\log\mathrm{({SNR})}$, in order to attain the optimal DMT. Finally, we discuss the case when multiple messages arrive at uniform intervals {\em within} each coherence period. Through a simple example we exhibit the sub-optimality of interleaving, and propose another scheme that achieves the optimal DMT.
Crowd Labeling: a survey
Venue: arXiv cs.AI 2014
Year: 2014

Recently, there has been a burst in the number of research projects on human computation via crowdsourcing. Multiple choice (or labeling) questions could be referred to as a common type of problem which is solved by this approach. As an application, crowd labeling is applied to find true labels for large machine learning datasets. Since crowds are not necessarily experts, the labels they provide are rather noisy and erroneous. This challenge is usually resolved by collecting multiple labels for each sample, and then aggregating them to estimate the true label. Although the mechanism leads to high-quality labels, it is not actually cost-effective. As a result, efforts are currently made to maximize the accuracy in estimating true labels, while fixing the number of acquired labels. This paper surveys methods to aggregate redundant crowd labels in order to estimate unknown true labels. It presents a unified statistical latent model where the differences among popular methods in the field correspond to different choices for the parameters of the model. Afterwards, algorithms to make inference on these models will be surveyed. Moreover, adaptive methods which iteratively collect labels based on the previously collected labels and estimated models will be discussed. In addition, this paper compares the distinguished methods, and provides guidelines for future work required to address the current open issues.
Deep Learning for Detecting Robotic Grasps
Venue: arXiv cs.LG 2014
Year: 2014

We consider the problem of detecting robotic grasps in an RGB-D view of a scene containing objects. In this work, we apply a deep learning approach to solve this problem, which avoids time-consuming hand-design of features. This presents two main challenges. First, we need to evaluate a huge number of candidate grasps. In order to make detection fast, as well as robust, we present a two-step cascaded structure with two deep networks, where the top detections from the first are re-evaluated by the second. The first network has fewer features, is faster to run, and can effectively prune out unlikely candidate grasps. The second, with more features, is slower but has to run only on the top few detections. Second, we need to handle multimodal inputs well, for which we present a method to apply structured regularization on the weights based on multimodal group regularization. We demonstrate that our method outperforms the previous state-of-the-art methods in robotic grasp detection, and can be used to successfully execute grasps on two different robotic platforms.
Capacity Results for Binary Fading Interference Channels with Delayed CSIT
Venue: arXiv cs.IT 2014
Year: 2014

To study the effect of lack of up-to-date channel state information at the transmitters (CSIT), we consider two-user binary fading interference channels with Delayed-CSIT. We characterize the capacity region for such channels under homogeneous assumption where channel gains have identical and independent distributions across time and space, eliminating the possibility of exploiting time/space correlation. We introduce and discuss several novel coding opportunities created by outdated CSIT that can enlarge the achievable rate region. The capacity-achieving scheme relies on accurate combination, concatenation, and merging of these opportunities, depending on the channel statistics. The outer-bounds are based on an extremal inequality we develop for a binary broadcast channel with Delayed-CSIT. We further extend the results and characterize the capacity region when output feedback links are available from the receivers to the transmitters in addition to the delayed knowledge of the channel state information. We also discuss the extension of our results to the non-homogeneous setting.
Stationary and Transition Probabilities in Slow Mixing, Long Memory Markov Processes
Venue: arXiv cs.IT 2014
Year: 2014

We observe a length-$n$ sample generated by an unknown,stationary ergodic Markov process (\emph{model}) over a finite alphabet $\mathcal{A}$. Given any string $\bf{w}$ of symbols from $\mathcal{A}$ we want estimates of the conditional probability distribution of symbols following $\bf{w}$, as well as the stationary probability of $\bf{w}$. Two distinct problems that complicate estimation in this setting are (i) long memory, and (ii) \emph{slow mixing} which could happen even with only one bit of memory. Any consistent estimator in this setting can only converge pointwise over the class of all ergodic Markov models. Namely, given any estimator and any sample size $n$, the underlying model could be such that the estimator performs poorly on a sample of size $n$ with high probability. But can we look at a length-$n$ sample and identify \emph{if} an estimate is likely to be accurate? Since the memory is unknown \emph{a-priori}, a natural approach is to estimate a potentially coarser model with memory $k_n=\mathcal{O}(\log n)$. As $n$ grows, pointwise consistent estimates that hold eventually almost surely (eas) are known so long as the scaling of $k_n$ is not superlogarithmic in $n$. Here, rather than eas convergence results, we want the best answers possible with a length-$n$ sample. Combining results in universal compression with Aldous' coupling arguments, we obtain sufficient conditions on the length-$n$ sample (even for slow mixing models) to identify when naive (i) estimates of the conditional probabilities and (ii) estimates related to the stationary probabilities are accurate; and also bound the deviations of the naive estimates from true values.
Interference Networks with No CSIT: Impact of Topology
Venue: arXiv cs.IT 2014
Year: 2014

We consider partially-connected $K$-user interference networks, where the transmitters have no knowledge about the channel gain values, but they are aware of network topology (or connectivity). We introduce several linear algebraic and graph theoretic concepts to derive new topology-based outer bounds and inner bounds on the symmetric degrees-of-freedom (DoF) of these networks. We evaluate our bounds for two classes of networks to demonstrate their tightness for most networks in these classes, quantify the gain of our inner bounds over benchmark interference management strategies, and illustrate the effect of network topology on these gains.
Two types of well followed users in the followership networks of Twitter
Venue: arXiv cs.SI 2014
Year: 2014

In the Twitter blogosphere, the number of followers is probably the most basic and succinct quantity for measuring popularity of users. However, the number of followers can be manipulated in various ways; we can even buy follows. Therefore, alternative popularity measures for Twitter users on the basis of, for example, users' tweets and retweets, have been developed. In the present work, we take a purely network approach to this fundamental question. First, we find that two relatively distinct types of users possessing a large number of followers exist, in particular for Japanese, Russian, and Korean users among the seven language groups that we examined. A first type of user follows a small number of other users. A second type of user follows approximately the same number of other users as the number of follows that the user receives. Then, we compare local (i.e., egocentric) followership networks around the two types of users with many followers. We show that the second type, which is presumably uninfluential users despite its large number of followers, is characterized by high link reciprocity, a large number of friends (i.e., those whom a user follows) for the followers, followers' high link reciprocity, large clustering coefficient, large fraction of the second type of users among the followers, and a small PageRank. Our network-based results support that the number of followers used alone is a misleading measure of user's popularity. We propose that the number of friends, which is simple to measure, also helps us to assess the popularity of Twitter users.
A Buffer-aided Successive Opportunistic Relay Selection Scheme with Power Adaptation and Inter-Relay Interference Cancellation for Cooperative Diversity Systems
Venue: arXiv cs.IT 2014
Year: 2014

In this paper we consider a simple cooperative network consisting of a source, a destination and a cluster of decode-and-forward half-duplex relays. At each time-slot, the source and (possibly) one of the relays transmit a packet to another relay and the destination, respectively, resulting in inter-relay interference (IRI). In this work, with the aid of buffers at the relays, we mitigate the detrimental effect of IRI through interference cancellation. More specifically, we propose the min-power scheme that minimizes the total energy expenditure per time slot under an IRI cancellation scheme. Apart from minimizing the energy expenditure, the min-power selection scheme, also provides better throughput and lower outage probability than existing works in the literature. It is the first time that interference cancellation is combined with buffer-aided relays and power adaptation to mitigate the IRI and minimize the energy expenditure. The new relay selection policy is analyzed in terms of outage probability and diversity, by modeling the evolution of the relay buffers as a Markov Chain (MC). We construct the state transition matrix of the MC, and hence obtain the steady state with which we can characterize the outage probability. The proposed scheme outperforms relevant state-of-the-art relay selection schemes in terms of throughput, diversity and energy efficiency, as demonstrated via examples.
Coding for Combined Block-Symbol Error Correction
Venue: arXiv cs.IT 2014
Year: 2014

We design low-complexity error correction coding schemes for channels that introduce different types of errors and erasures: on the one hand, the proposed schemes can successfully deal with symbol errors and erasures, and, on the other hand, they can also successfully handle phased burst errors and erasures.
Sequences with Minimal Time-Frequency Uncertainty
Venue: arXiv cs.IT 2014
Year: 2014

A central problem in signal processing and communications is to design signals that are compact both in time and frequency. Heisenberg's uncertainty principle states that a given function cannot be arbitrarily compact both in time and frequency, defining an "uncertainty" lower bound. Taking the variance as a measure of localization in time and frequency, Gaussian functions reach this bound for continuous-time signals. For sequences, however, this is not true; it is known that Heisenberg's bound is generally unachievable. For a chosen frequency variance, we formulate the search for "maximally compact sequences" as an exactly and efficiently solved convex optimization problem, thus providing a sharp uncertainty principle for sequences. Interestingly, the optimization formulation also reveals that maximally compact sequences are derived from Mathieu's harmonic cosine function of order zero. We further provide rational asymptotic expansions of this sharp uncertainty bound. We use the derived bounds as a benchmark to compare the compactness of well-known window functions with that of the optimal Mathieu's functions.
Deciding Conditional Termination
Venue: arXiv cs.LO 2014
Year: 2014

We address the problem of conditional termination, which is that of defining the set of initial configurations from which a given program always terminates. First we define the dual set, of initial configurations from which a non-terminating execution exists, as the greatest fixpoint of the function that maps a set of states into its pre-image with respect to the transition relation. This definition allows to compute the weakest non-termination precondition if at least one of the following holds: (i) the transition relation is deterministic, (ii) the descending Kleene sequence overapproximating the greatest fixpoint converges in finitely many steps, or (iii) the transition relation is well founded. We show that this is the case for two classes of relations, namely octagonal and finite monoid affine relations. Moreover, since the closed forms of these relations can be defined in Presburger arithmetic, we obtain the decidability of the termination problem for such loops.
Acquaintance Time of a Graph
Venue: arXiv cs.CC 2014
Year: 2014

We define the following parameter of connected graphs. For a given graph $G$ we place one agent in each vertex of $G$. Every pair of agents sharing a common edge is declared to be acquainted. In each round we choose some matching of $G$ (not necessarily a maximal matching), and for each edge in the matching the agents on this edge swap places. After the swap, again, every pair of agents sharing a common edge become acquainted, and the process continues. We define the \emph{acquaintance time} of a graph $G$, denoted by $AC(G)$, to be the minimal number of rounds required until every two agents are acquainted. We first study the acquaintance time for some natural families of graphs including the path, expanders, the binary tree, and the complete bipartite graph. We also show that for all positive integers $n$ and $k \leq n^{1.5}$ there exists an $n$-vertex graph $G$ such that $AC(G) =Θ(k)$. We also prove that for all $n$-vertex connected graphs $G$ we have $AC(G) = O\left(\frac{n^2}{\log(n)/\log\log(n)}\right)$, improving the $O(n^2)$ trivial upper bound achieved by sequentially letting each agent perform depth-first search along a spanning tree of $G$. Studying the computational complexity of this problem, we prove that for any constant $t \geq 1$ the problem of deciding that a given graph $G$ has $AC(G) \leq t$ or $AC(G) \geq 2t$ is $\mathcal{NP}$-complete. That is, $AC(G)$ is $\mathcal{NP}$-hard to approximate within multiplicative factor of 2, as well as within any additive constant factor. On the algorithmic side, we give a deterministic algorithm that given a graph $G$ with $AC(G)=1$ finds a ${\lceil n/c\rceil}$-rounds strategy for acquaintance in time $n^{c+O(1)}$. We also design a randomized polynomial time algorithm that given a graph $G$ with $AC(G)=1$ finds with high probability an $O(\log(n))$-rounds strategy for acquaintance.
Generic Strategies for Chemical Space Exploration
Venue: arXiv cs.FL 2014
Year: 2014

Computational approaches to exploring "chemical universes", i.e., very large sets, potentially infinite sets of compounds that can be constructed by a prescribed collection of reaction mechanisms, in practice suffer from a combinatorial explosion. It quickly becomes impossible to test, for all pairs of compounds in a rapidly growing network, whether they can react with each other. More sophisticated and efficient strategies are therefore required to construct very large chemical reaction networks. Undirected labeled graphs and graph rewriting are natural models of chemical compounds and chemical reactions. Borrowing the idea of partial evaluation from functional programming, we introduce partial applications of rewrite rules. Binding substrate to rules increases the number of rules but drastically prunes the substrate sets to which it might match, resulting in dramatically reduced resource requirements. At the same time, exploration strategies can be guided, e.g. based on restrictions on the product molecules to avoid the explicit enumeration of very unlikely compounds. To this end we introduce here a generic framework for the specification of exploration strategies in graph-rewriting systems. Using key examples of complex chemical networks from sugar chemistry and the realm of metabolic networks we demonstrate the feasibility of a high-level strategy framework. The ideas presented here can not only be used for a strategy-based chemical space exploration that has close correspondence of experimental results, but are much more general. In particular, the framework can be used to emulate higher-level transformation models such as illustrated in a small puzzle game.
Decentralized Event-Triggering for Control of Nonlinear Systems
Venue: arXiv cs.SY 2014
Year: 2014

This paper considers nonlinear systems with full state feedback, a central controller and distributed sensors not co-located with the central controller. We present a methodology for designing decentralized asynchronous event-triggers, which utilize only locally available information, for determining the time instants of transmission from the sensors to the central controller. The proposed design guarantees a positive lower bound for the inter-transmission times of each sensor, while ensuring asymptotic stability of the origin of the system with an arbitrary, but priorly fixed, compact region of attraction. In the special case of Linear Time Invariant (LTI) systems, global asymptotic stability is guaranteed and scale invariance of inter-transmission times is preserved. A modified design method is also proposed for nonlinear systems, with the addition of event-triggered communication from the controller to the sensors, that promises to significantly increase the average sensor inter-transmission times compared to the case where the controller does not transmit data to the sensors. The proposed designs are illustrated through simulations of a linear and a nonlinear example.
On the sum of $L1$ influences
Venue: arXiv cs.CC 2014
Year: 2014

For a function $f$ over the discrete cube, the total $L_1$ influence of $f$ is defined as $\sum_{i=1}^n \|\partial_i f\|_1$, where $\partial_i f$ denotes the discrete derivative of $f$ in the direction $i$. In this work, we show that the total $L_1$ influence of a $[-1,1]$-valued function $f$ can be upper bounded by a polynomial in the degree of $f$, resolving affirmatively an open problem of Aaronson and Ambainis (ITCS 2011). The main challenge here is that the $L_1$ influences do not admit an easy Fourier analytic representation. In our proof, we overcome this problem by introducing a new analytic quantity $\mathcal I_p(f)$, relating this new quantity to the total $L_1$ influence of $f$. This new quantity, which roughly corresponds to an average of the total $L_1$ influences of some ensemble of functions related to $f$, has the benefit of being much easier to analyze, allowing us to resolve the problem of Aaronson and Ambainis. We also give an application of the theorem to graph theory, and discuss the connection between the study of bounded functions over the cube and the quantum query complexity of partial functions where Aaronson and Ambainis encountered this question.
Universal Outlier Hypothesis Testing
Venue: arXiv cs.IT 2014
Year: 2014

Outlier hypothesis testing is studied in a universal setting. Multiple sequences of observations are collected, a small subset of which are outliers. A sequence is considered an outlier if the observations in that sequence are distributed according to an ``outlier'' distribution, distinct from the ``typical'' distribution governing the observations in all the other sequences. Nothing is known about the outlier and typical distributions except that they are distinct and have full supports. The goal is to design a universal test to best discern the outlier sequence(s). It is shown that the generalized likelihood test is universally exponentially consistent under various settings. The achievable error exponent is also characterized. In the other settings, it is also shown that there cannot exist any universally exponentially consistent test.
Directed closure measures for networks with reciprocity
Venue: arXiv cs.SI 2014
Year: 2014

The study of triangles in graphs is a standard tool in network analysis, leading to measures such as the \emph{transitivity}, i.e., the fraction of paths of length $2$ that participate in triangles. Real-world networks are often directed, and it can be difficult to "measure" this network structure meaningfully. We propose a collection of \emph{directed closure values} for measuring triangles in directed graphs in a way that is analogous to transitivity in an undirected graph. Our study of these values reveals much information about directed triadic closure. For instance, we immediately see that reciprocal edges have a high propensity to participate in triangles. We also observe striking similarities between the triadic closure patterns of different web and social networks. We perform mathematical and empirical analysis showing that directed configuration models that preserve reciprocity cannot capture the triadic closure patterns of real networks.
Towards a provably resilient scheme for graph-based watermarking
Venue: arXiv cs.MM 2014
Year: 2014

Digital watermarks have been considered a promising way to fight software piracy. Graph-based watermarking schemes encode authorship/ownership data as control-flow graph of dummy code. In 2012, Chroni and Nikolopoulos developed an ingenious such scheme which was claimed to withstand attacks in the form of a single edge removal. We extend the work of those authors in various aspects. First, we give a formal characterization of the class of graphs generated by their encoding function. Then, we formulate a linear-time algorithm which recovers from ill-intentioned removals of $k \leq 2$ edges, therefore proving their claim. Furthermore, we provide a simpler decoding function and an algorithm to restore watermarks with an arbitrary number of missing edges whenever at all possible. By disclosing and improving upon the resilience of Chroni and Nikolopoulos's watermark, our results reinforce the interest in regarding it as a possible solution to numerous applications.