OpenRaiser/Intern-Atlas huggingface dataset:
The Jacobi MIMO Channel
Venue: arXiv cs.IT 2012
Year: 2012

This paper presents a new fading model for MIMO channels, the Jacobi fading model. It asserts that $H$, the transfer matrix which couples the $m_t$ inputs into $m_r$ outputs, is a sub-matrix of an $m\times m$ random (Haar-distributed) unitary matrix. The (squared) singular values of $H$ follow the law of the classical Jacobi ensemble of random matrices; hence the name of the channel. One motivation to define such a channel comes from multimode/multicore optical fiber communication. It turns out that this model can be qualitatively different than the Rayleigh model, leading to interesting practical and theoretical results. This work first evaluates the ergodic capacity of the channel. Then, it considers the non-ergodic case, where it analyzes the outage probability and the diversity-multiplexing tradeoff. In the case where $k=m_t+m_r-m > 0$ it is shown that at least $k$ degrees of freedom are guaranteed not to fade for any channel realization, enabling a zero outage probability or infinite diversity order at the corresponding rates. A simple scheme utilizing (a possibly outdated) channel state feedback is provided, attaining the no-outage guarantee. Finally, noting that as $m$ increases, the Jacobi model approaches the Rayleigh model, the paper discusses the applicability of the model in other communication scenaria.
Artificial Inflation: The True Story of Trends in Sina Weibo
Venue: arXiv cs.CY 2012
Year: 2012

There has been a tremendous rise in the growth of online social networks all over the world in recent years. This has facilitated users to generate a large amount of real-time content at an incessant rate, all competing with each other to attract enough attention and become trends. While Western online social networks such as Twitter have been well studied, characteristics of the popular Chinese microblogging network Sina Weibo have not been. In this paper, we analyze in detail the temporal aspect of trends and trend-setters in Sina Weibo, constrasting it with earlier observations on Twitter. First, we look at the formation, persistence and decay of trends and examine the key topics that trend in Sina Weibo. One of our key findings is that retweets are much more common in Sina Weibo and contribute a lot to creating trends. When we look closer, we observe that a large percentage of trends in Sina Weibo are due to the continuous retweets of a small amount of fraudulent accounts. These fake accounts are set up to artificially inflate certain posts causing them to shoot up into Sina Weibo's trending list, which are in turn displayed as the most popular topics to users.
Analog Network Coding in General SNR Regime
Venue: arXiv cs.IT 2012
Year: 2012

The problem of maximum rate achievable with analog network coding for a unicast communication over a layered wireless relay network with directed links is considered. A relay node performing analog network coding scales and forwards the signals received at its input. Recently this problem has been considered under two assumptions: (A) each relay node scales its received signal to the upper bound of its transmit power constraint, (B) the relay nodes in specific subsets of the network operate in the high-SNR regime. We establish that assumption (A), in general, leads to suboptimal end-to-end rate. We also characterize the performance of analog network coding in class of symmetric layered networks without assumption (B). The key contribution of this work is a lemma that states that a globally optimal set of scaling factors for the nodes in a layered relay network that maximizes the end-to-end rate can be computed layer-by-layer. Specifically, a rate-optimal set of scaling factors for the nodes in a layer is the one that maximizes the sum-rate of the nodes in the next layer. This critical insight allows us to characterize analog network coding performance in network scenarios beyond those that can be analyzed using the existing approaches. We illustrate this by computing the maximum rate achievable with analog network coding in one particular layered network, in various communication scenarios.
A Cooperative Bayesian Nonparametric Framework for Primary User Activity Monitoring in Cognitive Radio Network
Venue: arXiv cs.IT 2012
Year: 2012

This paper introduces a novel approach that enables a number of cognitive radio devices that are observing the availability pattern of a number of primary users(PUs), to cooperate and use \emph{Bayesian nonparametric} techniques to estimate the distributions of the PUs' activity pattern, assumed to be completely unknown. In the proposed model, each cognitive node may have its own individual view on each PU's distribution, and, hence, seeks to find partners having a correlated perception. To address this problem, a coalitional game is formulated between the cognitive devices and an algorithm for cooperative coalition formation is proposed. It is shown that the proposed coalition formation algorithm allows the cognitive nodes that are experiencing a similar behavior from some PUs to self-organize into disjoint, independent coalitions. Inside each coalition, the cooperative cognitive nodes use a combination of Bayesian nonparametric models such as the Dirichlet process and statistical goodness of fit techniques in order to improve the accuracy of the estimated PUs' activity distributions. Simulation results show that the proposed algorithm significantly improves the estimates of the PUs' distributions and yields a performance advantage, in terms of reduction of the average achieved Kullback-Leibler distance between the real and the estimated distributions, reaching up to 36.5% relative the non-cooperative estimates. The results also show that the proposed algorithm enables the cognitive nodes to adapt their cooperative decisions when the actual PUs' distributions change due to, for example, PU mobility.
Resolving Implementation Ambiguity and Improving SURF
Venue: arXiv cs.CV 2012
Year: 2012

Speeded Up Robust Features (SURF) has emerged as one of the more popular feature descriptors and detectors in recent years. Performance and algorithmic details vary widely between implementations due to SURF's complexity and ambiguities found in its description. To resolve these ambiguities, a set of general techniques for feature stability is defined based on the smoothness rule. Additional improvements to SURF are proposed for speed and stability. To illustrate the importance of these implementation details, a performance study of popular SURF implementations is done. By utilizing all the suggested improvements, it is possible to create a SURF implementation that is several times faster and more stable.
Defeating the Kalka--Teicher--Tsaban linear algebra attack on the Algebraic Eraser
Venue: arXiv cs.CR 2012
Year: 2012

The Algebraic Eraser (AE) is a public key protocol for sharing information over an insecure channel using commutative and noncommutative groups; a concrete realization is given by Colored Burau Key Agreement Protocol (CBKAP). In this paper, we describe how to choose data in CBKAP to thwart an attack by Kalka--Teicher--Tsaban.
Classification of Flames in Computer Mediated Communications
Venue: arXiv cs.SI 2012
Year: 2012

Computer Mediated Communication (CMC) has brought about a revolution in the way the world communicates with each other. With the increasing number of people, interacting through the internet and the rise of new platforms and technologies has brought together the people from different social, cultural and geographical backgrounds to present their thoughts, ideas and opinions on topics of their interest. CMC has, in some cases, gave users more freedom to express themselves as compared to Face-to-face communication. This has also led to rise in the use of hostile and aggressive language and terminologies uninhibitedly. Since such use of language is detrimental to the discussion process and affects the audience and individuals negatively, efforts are being taken to control them. The research sees the need to understand the concept of flaming and hence attempts to classify them in order to give a better understanding of it. The classification is done on the basis of type of flame content being presented and the Style in which they are presented.
From heaps of matches to the limits of computability
Venue: arXiv cs.CC 2012
Year: 2012

We study so-called invariant games played with a fixed number $d$ of heaps of matches. A game is described by a finite list $\mathcal{M}$ of integer vectors of length $d$ specifying the legal moves. A move consists in changing the current game-state by adding one of the vectors in $\mathcal{M}$, provided all elements of the resulting vector are nonnegative. For instance, in a two-heap game, the vector $(1,-2)$ would mean adding one match to the first heap and removing two matches from the second heap. If $(1,-2) \in \mathcal{M}$, such a move would be permitted provided there are at least two matches in the second heap. Two players take turns, and a player unable to make a move loses. We show that these games embrace computational universality, and that therefore a number of basic questions about them are algorithmically undecidable. In particular, we prove that there is no algorithm that takes two games $\mathcal{M}$ and $\mathcal{M}'$ (with the same number of heaps) as input, and determines whether or not they are equivalent in the sense that every starting-position which is a first player win in one of the games is a first player win in the other.
Asymptotically Good Codes Over Non-Abelian Groups
Venue: arXiv cs.IT 2012
Year: 2012

It has been shown that good structured codes over non-Abelian groups do exist. Specifically, we construct codes over the smallest non-Abelian group $\mathds{D}_6$ and show that the performance of these codes is superior to the performance of Abelian group codes of the same alphabet size. This promises the possibility of using non-Abelian codes for multi-terminal settings where the structure of the code can be exploited to gain performance.
Nested Lattice Codes for Arbitrary Continuous Sources and Channels
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we show that nested lattice codes achieve the capacity of arbitrary channels with or without non-casual state information at the transmitter. We also show that nested lattice codes are optimal for source coding with or without non-causal side information at the receiver for arbitrary continuous sources.
List-decoding of Subspace Codes and Rank-Metric Codes up to Singleton Bound
Venue: arXiv cs.IT 2012
Year: 2012

Subspace codes and rank-metric codes can be used to correct errors and erasures in network, with linear network coding. Subspace codes were introduced by Koetter and Kschischang to correct errors and erasures in networks where topology is unknown (the noncoherent case). In a previous work, we have developed a family of subspace codes, based upon the Koetter-Kschichang construction, which are efficiently list decodable. Using these codes, we achieved a better decoding radius than Koetter-Kschischiang codes at low rates. Herein, we introduce a new family of subspace codes based upon a different approach which leads to a linear-algebraic list-decoding algorithm. The resulting error correction radius can be expressed as follows: for any integer $s$, our list-decoder using $s+1$-interpolation polynomials guarantees successful recovery of the message subspace provided the normalized dimension of errors is at most $s(1-sR)$. The same list-decoding algorithm can be used to correct erasures as well as errors. The size of output list is at most $Q^{s-1}$, where $Q$ is the size of the field that message symbols are chosen from. Rank-metric codes are suitable for error correction in the case where the network topology and the underlying network code are known (the coherent case). Gabidulin codes are a well-known class of algebraic rank-metric codes that meet the Singleton bound on the minimum rank metric of a code. In this paper, we introduce a folded version of Gabidulin codes analogous to the folded Reed-Solomon codes of Guruswami and Rudra along with a list-decoding algorithm for such codes. Our list-decoding algorithm makes it possible to recover the message provided that the normalized rank of error is at most $1-R-ε$, for any $ε> 0$. Notably this achieves the information theoretic bound on the decoding radius of a rank-metric code.
The Impact of Secure OSs on Internet Security: What Cyber-Insurers Need to Know
Venue: arXiv cs.CR 2012
Year: 2012

In recent years, researchers have proposed \emph{cyber-insurance} as a suitable risk-management technique for enhancing security in Internet-like distributed systems. However, amongst other factors, information asymmetry between the insurer and the insured, and the inter-dependent and correlated nature of cyber risks have contributed in a big way to the failure of cyber-insurance markets. Security experts have argued in favor of operating system (OS) platform switching (ex., from Windows to Unix-based OSs) or secure OS adoption as being one of the techniques that can potentially mitigate the problems posing a challenge to successful cyber-insurance markets. In this regard we model OS platform switching dynamics using a \emph{social gossip} mechanism and study three important questions related to the nature of the dynamics, for Internet-like distributed systems: (i) which type of networks should cyber-insurers target for insuring?, (ii) what are the bounds on the asymptotic performance level of a network, where the performance parameter is an average function of the long-run individual user willingness to adopt secure OSs?, and (iii) how can cyber-insurers use the topological information of their clients to incentivize/reward them during offering contracts? Our analysis is important to a profit-minded cyber-insurer, who wants to target the right network, design optimal contracts to resolve information asymmetry problems, and at the same time promote the increase of overall network security through increasing secure OS adoption amongst users.
Denotation of syntax and metaprogramming in contextual modal type theory (CMTT)
Venue: arXiv cs.LO 2012
Year: 2012

The modal logic S4 can be used via a Curry-Howard style correspondence to obtain a lambda-calculus. Modal (boxed) types are intuitively interpreted as `closed syntax of the calculus'. This lambda-calculus is called modal type theory --- this is the basic case of a more general contextual modal type theory, or CMTT. CMTT has never been given a denotational semantics in which modal types are given denotation as closed syntax. We show how this can indeed be done, with a twist. We also use the denotation to prove some properties of the system.
Coordinating Complementary Waveforms for Sidelobe Suppression
Venue: arXiv cs.IT 2012
Year: 2012

We present a general method for constructing radar transmit pulse trains and receive filters for which the radar point-spread function in delay and Doppler, given by the cross-ambiguity function of the transmit pulse train and the pulse train used in the receive filter, is essentially free of range sidelobes inside a Doppler interval around the zero-Doppler axis. The transmit pulse train is constructed by coordinating the transmission of a pair of Golay complementary waveforms across time according to zeros and ones in a binary sequence P. The pulse train used to filter the received signal is constructed in a similar way, in terms of sequencing the Golay waveforms, but each waveform in the pulse train is weighted by an element from another sequence Q. We show that a spectrum jointly determined by P and Q sequences controls the size of the range sidelobes of the cross-ambiguity function and by properly choosing P and Q we can clear out the range sidelobes inside a Doppler interval around the zero- Doppler axis. The joint design of P and Q enables a tradeoff between the order of the spectral null for range sidelobe suppression and the signal-to-noise ratio at the receiver output. We establish this trade-off and derive a necessary and sufficient condition for the construction of P and Q sequences that produce a null of a desired order.
Alternating Markov Chains for Distribution Estimation in the Presence of Errors
Venue: arXiv cs.IT 2012
Year: 2012

We consider a class of small-sample distribution estimators over noisy channels. Our estimators are designed for repetition channels, and rely on properties of the runs of the observed sequences. These runs are modeled via a special type of Markov chains, termed alternating Markov chains. We show that alternating chains have redundancy that scales sub-linearly with the lengths of the sequences, and describe how to use a distribution estimator for alternating chains for the purpose of distribution estimation over repetition channels.
Action Dependent Strictly Causal State Communication
Venue: arXiv cs.IT 2012
Year: 2012

The problem of communication and state estimation is considered in the context of channels with actiondependent states. Given the message to be communicated, the transmitter chooses an action sequence that affects the formation of the channel states, and then creates the channel input sequence based on the state sequence. The decoder estimates the channel to some distortion as well as decodes the message. The capacity-distortion tradeoff of such a channel is characterized for the case when the state information is available strictly causally at the channel encoder. The problem setting extends the action dependent framework of [1] and as a special case recovers the results of few previously considered joint communication and estimation scenarios in [2], [3], [4]. The scenario when the action is also allowed to depend on the past observed states (adaptive action) is also considered. It is shown that such adaptive action yields an improved capacity-distortion function.
Dithered quantizers with negligible in-band dither power
Venue: arXiv cs.IT 2012
Year: 2012

Subtractive dithered quantizers are examined to minimize the signal-band dither power. The design of finite impulse response(FIR) filters that shape most of the dither-power out of the signal band while maintaining the benefits of dithering are dealt with in detail. Simulation results for low-medium resolution quantizers are presented to highlight the overall design consideration.
Packing interval graphs with vertex-disjoint triangles
Venue: arXiv cs.DS 2012
Year: 2012

We show that there exists a polynomial algorithm to pack interval graphs with vertex-disjoint triangles.
Regenerating Codes for Errors and Erasures in Distributed Storage
Venue: arXiv cs.IT 2012
Year: 2012

Regenerating codes are a class of codes proposed for providing reliability of data and efficient repair of failed nodes in distributed storage systems. In this paper, we address the fundamental problem of handling errors and erasures during the data-reconstruction and node-repair operations. We provide explicit regenerating codes that are resilient to errors and erasures, and show that these codes are optimal with respect to storage and bandwidth requirements. As a special case, we also establish the capacity of a class of distributed storage systems in the presence of malicious adversaries. While our code constructions are based on previously constructed Product-Matrix codes, we also provide necessary and sufficient conditions for introducing resilience in any regenerating code.
On Stability Problems of Omega and 3-Disjoint Paths Omega Multi-stage Interconnection Networks
Venue: arXiv cs.DC 2012
Year: 2012

The research paper emphasizes that the Stable Matching problems are the same as the problems of stable configurations of Multi-stage Interconnection Networks (MIN). We have discusses the Stability Problems of Existing Regular Omega Multi-stage Interconnection Network (OMIN) and Proposed 3-Disjoint Paths Omega Multi-stage Interconnection Network (3DON) using the approaches and solutions provided by the Stable Matching Problem. Specifically, Stable Marriage Problem is used as an example of Stable Matching. On application of the concept of the Stable Marriage over the MINs states that OMIN is highly stable in comparison to 3DON.
Robust 1-bit compressed sensing and sparse logistic regression: A convex programming approach
Venue: arXiv cs.IT 2012
Year: 2012

This paper develops theoretical results regarding noisy 1-bit compressed sensing and sparse binomial regression. We show that a single convex program gives an accurate estimate of the signal, or coefficient vector, for both of these models. We demonstrate that an s-sparse signal in R^n can be accurately estimated from m = O(slog(n/s)) single-bit measurements using a simple convex program. This remains true even if each measurement bit is flipped with probability nearly 1/2. Worst-case (adversarial) noise can also be accounted for, and uniform results that hold for all sparse inputs are derived as well. In the terminology of sparse logistic regression, we show that O(slog(n/s)) Bernoulli trials are sufficient to estimate a coefficient vector in R^n which is approximately s-sparse. Moreover, the same convex program works for virtually all generalized linear models, in which the link function may be unknown. To our knowledge, these are the first results that tie together the theory of sparse logistic regression to 1-bit compressed sensing. Our results apply to general signal structures aside from sparsity; one only needs to know the size of the set K where signals reside. The size is given by the mean width of K, a computable quantity whose square serves as a robust extension of the dimension.
Asymptotically Optimal Algorithms for Pickup and Delivery Problems with Application to Large-Scale Transportation Systems
Venue: arXiv cs.SY 2012
Year: 2012

The Stacker Crane Problem is NP-Hard and the best known approximation algorithm only provides a 9/5 approximation ratio. The objective of this paper is threefold. First, by embedding the problem within a stochastic framework, we present a novel algorithm for the SCP that: (i) is asymptotically optimal, i.e., it produces, almost surely, a solution approaching the optimal one as the number of pickups/deliveries goes to infinity; and (ii) has computational complexity $O(n^{2+\eps})$, where $n$ is the number of pickup/delivery pairs and $\eps$ is an arbitrarily small positive constant. Second, we asymptotically characterize the length of the optimal SCP tour. Finally, we study a dynamic version of the SCP, whereby pickup and delivery requests arrive according to a Poisson process, and which serves as a model for large-scale demand-responsive transport (DRT) systems. For such a dynamic counterpart of the SCP, we derive a necessary and sufficient condition for the existence of stable vehicle routing policies, which depends only on the workspace geometry, the stochastic distributions of pickup and delivery points, the arrival rate of requests, and the number of vehicles. Our results leverage a novel connection between the Euclidean Bipartite Matching Problem and the theory of random permutations, and, for the dynamic setting, exhibit novel features that are absent in traditional spatially-distributed queueing systems.