OpenRaiser/Intern-Atlas huggingface dataset:
Influence of Speech Codecs Selection on Transcoding Steganography
Venue: arXiv cs.CR 2012
Year: 2012

The typical approach to steganography is to compress the covert data in order to limit its size, which is reasonable in the context of a limited steganographic bandwidth. TranSteg (Trancoding Steganography) is a new IP telephony steganographic method that was recently proposed that offers high steganographic bandwidth while retaining good voice quality. In TranSteg, compression of the overt data is used to make space for the steganogram. In this paper we focus on analyzing the influence of the selection of speech codecs on hidden transmission performance, that is, which codecs would be the most advantageous ones for TranSteg. Therefore, by considering the codecs which are currently most popular for IP telephony we aim to find out which codecs should be chosen for transcoding to minimize the negative influence on voice quality while maximizing the obtained steganographic bandwidth.
Models of Manipulation on Aggregation of Binary Evaluations
Venue: arXiv cs.GT 2012
Year: 2012

We study a general aggregation problem in which a society has to determine its position on each of several issues, based on the positions of the members of the society on those issues. There is a prescribed set of feasible evaluations, i.e., permissible combinations of positions on the issues. Among other things, this framework admits the modeling of preference aggregation, judgment aggregation, classification, clustering and facility location. An important notion in aggregation of evaluations is strategy-proofness. In the general framework we discuss here, several definitions of strategy-proofness may be considered. We present here 3 natural \textit{general} definitions of strategy-proofness and analyze the possibility of designing an annonymous, strategy-proof aggregation rule under these definitions.
Conditional and unconditional information inequalities: an algebraic example
Venue: arXiv cs.IT 2012
Year: 2012

We provide a simple example showing that some conditional information inequalities (even in a weak form) cannot be derived from unconditional inequalities.
A Note on Disk Drag Dynamics
Venue: arXiv cs.PF 2012
Year: 2012

The electrical power consumed by typical magnetic hard disk drives (HDD) not only increases linearly with the number of spindles but, more significantly, it increases as very fast power-laws of speed (RPM) and diameter. Since the theoretical basis for this relationship is neither well-known nor readily accessible in the literature, we show how these exponents arise from aerodynamic disk drag and discuss their import for green storage capacity planning.
Relation Strength-Aware Clustering of Heterogeneous Information Networks with Incomplete Attributes
Venue: arXiv cs.DB 2012
Year: 2012

With the rapid development of online social media, online shopping sites and cyber-physical systems, heterogeneous information networks have become increasingly popular and content-rich over time. In many cases, such networks contain multiple types of objects and links, as well as different kinds of attributes. The clustering of these objects can provide useful insights in many applications. However, the clustering of such networks can be challenging since (a) the attribute values of objects are often incomplete, which implies that an object may carry only partial attributes or even no attributes to correctly label itself; and (b) the links of different types may carry different kinds of semantic meanings, and it is a difficult task to determine the nature of their relative importance in helping the clustering for a given purpose. In this paper, we address these challenges by proposing a model-based clustering algorithm. We design a probabilistic model which clusters the objects of different types into a common hidden space, by using a user-specified set of attributes, as well as the links from different relations. The strengths of different types of links are automatically learned, and are determined by the given purpose of clustering. An iterative algorithm is designed for solving the clustering problem, in which the strengths of different types of links and the quality of clustering results mutually enhance each other. Our experimental results on real and synthetic data sets demonstrate the effectiveness and efficiency of the algorithm.
Length 3 Edge-Disjoint Paths and Partial Orientation
Venue: arXiv cs.CC 2012
Year: 2012

In 2003, it was claimed that the following problem was solvable in polynomial time: do there exist k edge-disjoint paths of length exactly 3 between vertices s and t in a given graph? The proof was flawed, and we show that this problem is NP-hard even if we disallow multiple edges. We use a reduction from Partial Orientation, a problem recently shown by Pálvölgyi to be NP-hard.
Learning Performance of Prediction Markets with Kelly Bettors
Venue: arXiv cs.AI 2012
Year: 2012

In evaluating prediction markets (and other crowd-prediction mechanisms), investigators have repeatedly observed a so-called "wisdom of crowds" effect, which roughly says that the average of participants performs much better than the average participant. The market price---an average or at least aggregate of traders' beliefs---offers a better estimate than most any individual trader's opinion. In this paper, we ask a stronger question: how does the market price compare to the best trader's belief, not just the average trader. We measure the market's worst-case log regret, a notion common in machine learning theory. To arrive at a meaningful answer, we need to assume something about how traders behave. We suppose that every trader optimizes according to the Kelly criteria, a strategy that provably maximizes the compound growth of wealth over an (infinite) sequence of market interactions. We show several consequences. First, the market prediction is a wealth-weighted average of the individual participants' beliefs. Second, the market learns at the optimal rate, the market price reacts exactly as if updating according to Bayes' Law, and the market prediction has low worst-case log regret to the best individual participant. We simulate a sequence of markets where an underlying true probability exists, showing that the market converges to the true objective frequency as if updating a Beta distribution, as the theory predicts. If agents adopt a fractional Kelly criteria, a common practical variant, we show that agents behave like full-Kelly agents with beliefs weighted between their own and the market's, and that the market price converges to a time-discounted frequency. Our analysis provides a new justification for fractional Kelly betting, a strategy widely used in practice for ad-hoc reasons. Finally, we propose a method for an agent to learn her own optimal Kelly fraction.
Lower Bounds for Local Approximation
Venue: arXiv cs.DC 2012
Year: 2012

In the study of deterministic distributed algorithms it is commonly assumed that each node has a unique $O(\log n)$-bit identifier. We prove that for a general class of graph problems, local algorithms (constant-time distributed algorithms) do not need such identifiers: a port numbering and orientation is sufficient. Our result holds for so-called simple PO-checkable graph optimisation problems; this includes many classical packing and covering problems such as vertex covers, edge covers, matchings, independent sets, dominating sets, and edge dominating sets. We focus on the case of bounded-degree graphs and show that if a local algorithm finds a constant-factor approximation of a simple PO-checkable graph problem with the help of unique identifiers, then the same approximation ratio can be achieved on anonymous networks. As a corollary of our result and by prior work, we derive a tight lower bound on the local approximability of the minimum edge dominating set problem. Our main technical tool is an algebraic construction of homogeneously ordered graphs: We say that a graph is $(α,r)$-homogeneous if its nodes are linearly ordered so that an $α$ fraction of nodes have pairwise isomorphic radius-$r$ neighbourhoods. We show that there exists a finite $(α,r)$-homogeneous $2k$-regular graph of girth at least $g$ for any $α< 1$ and any $r$, $k$, and $g$.
A Factor Graph Approach to Clock Offset Estimation in Wireless Sensor Networks
Venue: arXiv cs.IT 2012
Year: 2012

The problem of clock offset estimation in a two way timing message exchange regime is considered when the likelihood function of the observation time stamps is Gaussian, exponential or log-normally distributed. A parametrized solution to the maximum likelihood (ML) estimation of clock offset, based on convex optimization, is presented, which differs from the earlier approaches where the likelihood function is maximized graphically. In order to capture the imperfections in node oscillators, which may render a time-varying nature to the clock offset, a novel Bayesian approach to the clock offset estimation is proposed by using a factor graph representation of the posterior density. Message passing using the max-product algorithm yields a closed form expression for the Bayesian inference problem. Several lower bounds on the variance of an estimator are derived for arbitrary exponential family distributed likelihood functions which, while serving as stepping stones to benchmark the performance of the proposed clock offset estimators, can be useful in their own right in classical as well Bayesian parameter estimation theory. To corroborate the theoretical findings, extensive simulation results are discussed for classical as well as Bayesian estimators in various scenarios. It is observed that the performance of the proposed estimators is fairly close to the fundamental limits established by the lower bounds.
On the Capacity of Interference Channel with Causal and Non-causal Generalized Feedback at the Cognitive Transmitter
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, taking into account the effect of link delays, we investigate the capacity region of the Cognitive Interference Channel (C-IFC), where cognition can be obtained from either causal or non-causal generalized feedback. For this purpose, we introduce the Causal Cognitive Interference Channel With Delay (CC-IFC-WD) in which the cognitive user's transmission can depend on $L$ future received symbols as well as the past ones. We show that the CC-IFC-WD model is equivalent to a classical Causal C-IFC (CC-IFC) with link delays. Moreover, CC-IFC-WD extends both genie-aided and causal cognitive radio channels and bridges the gap between them. First, we derive an outer bound on the capacity region for the arbitrary value of $L$ and specialize this general outer bound to the strong interference case. Then, under strong interference conditions, we tighten the outer bound. To derive the achievable rate regions, we concentrate on three special cases: 1) Classical CC-IFC (L=0), 2) CC-IFC without delay (L=1), and 3) CC-IFC with unlimited look-ahead in which the cognitive user non-causally knows its entire received sequence. In each case, we obtain a new inner bound on the capacity region. Moreover, we show that the coding strategy which we use to derive an achievable rate region for the classical CC-IFC achieves the capacity for the classes of degraded and semi-deterministic classical CC-IFC under strong interference conditions. Furthermore, we extend our achievable rate regions to the Gaussian case. Providing some numerical examples for Gaussian CC-IFC-WD, we compare the performances of the different strategies and investigate the rate gain of the cognitive link for different delay values.
The Pulse of News in Social Media: Forecasting Popularity
Venue: arXiv cs.CY 2012
Year: 2012

News articles are extremely time sensitive by nature. There is also intense competition among news items to propagate as widely as possible. Hence, the task of predicting the popularity of news items on the social web is both interesting and challenging. Prior research has dealt with predicting eventual online popularity based on early popularity. It is most desirable, however, to predict the popularity of items prior to their release, fostering the possibility of appropriate decision making to modify an article and the manner of its publication. In this paper, we construct a multi-dimensional feature space derived from properties of an article and evaluate the efficacy of these features to serve as predictors of online popularity. We examine both regression and classification algorithms and demonstrate that despite randomness in human behavior, it is possible to predict ranges of popularity on twitter with an overall 84% accuracy. Our study also serves to illustrate the differences between traditionally prominent sources and those immensely popular on the social web.
Algebraic List-decoding of Subspace Codes
Venue: arXiv cs.IT 2012
Year: 2012

Subspace codes were introduced in order to correct errors and erasures for randomized network coding, in the case where network topology is unknown (the noncoherent case). Subspace codes are indeed collections of subspaces of a certain vector space over a finite field. The Koetter-Kschischang construction of subspace codes are similar to Reed-Solomon codes in that codewords are obtained by evaluating certain (linearized) polynomials. In this paper, we consider the problem of list-decoding the Koetter-Kschischang subspace codes. In a sense, we are able to achieve for these codes what Sudan was able to achieve for Reed-Solomon codes. In order to do so, we have to modify and generalize the original Koetter-Kschischang construction in many important respects. The end result is this: for any integer $L$, our list-$L$ decoder guarantees successful recovery of the message subspace provided that the normalized dimension of the error is at most $ L - \frac{L(L+1)}{2}R $ where $R$ is the normalized packet rate. Just as in the case of Sudan's list-decoding algorithm, this exceeds the previously best known error-correction radius $1-R$, demonstrated by Koetter and Kschischang, for low rates $R$.
Channel Identification and its Impact on Quantum LDPC Code Performance
Venue: arXiv cs.IT 2012
Year: 2012

In this work we probe the impact of channel estimation on the performance of quantum LDPC codes. Our channel estimation is based on an optimal estimate of the relevant decoherence parameter via its quantum Fisher information. Using state-of-the art quantum LDPC codes designed for the quantum depolarization channel, and utilizing various quantum probes with different entanglement properties, we show how the performance of such codes can deteriorate by an order of magnitude when optimal channel identification is fed into a belief propagation decoding algorithm. Our work highlights the importance in quantum communications of a viable channel identification campaign prior to decoding, and highlights the trade-off between entanglement consumption and quantum LDPC code performance.
A note on probe cographs
Venue: arXiv cs.DS 2012
Year: 2012

Let G be a graph and let N_1, ..., N_k be k independent sets in G. The graph G is a k-probe cograph if G can be embedded into a cograph by adding edges between vertices that are contained in the same independent set. We show that there exists an O(k n^5) algorithm to check if a graph G is a k-probe cograph.
Blind Null-Space Learning for MIMO Underlay Cognitive Radio Networks
Venue: arXiv cs.IT 2012
Year: 2012

This paper proposes a blind technique for MIMO cognitive radio Secondary Users (SU) to transmit in the same band simultaneously with a Primary User (PU) under a maximum interference constraint. In the proposed technique, the SU is able to meet the interference constraint of the PU without explicitly estimating the interference channel matrix to the PU and without burdening the PU with any interaction with the SU. The only condition required of the PU is that for a short time interval it uses a power control scheme such that its transmitted power is a monotonic function of the interference inflicted by the SU. During this time interval, the SU iteratively modifies the spatial orientation of its transmitted signal and measures the effect of this modification on the PU's total transmit power. The entire process is based on energy measurements which is very desirable from an implementation point of view.
On the Fixation Probability of Superstars
Venue: arXiv cs.CE 2012
Year: 2012

The Moran process models the spread of genetic mutations through a population. A mutant with relative fitness $r$ is introduced into a population and the system evolves, either reaching fixation (in which every individual is a mutant) or extinction (in which none is). In a widely cited paper (Nature, 2005), Lieberman, Hauert and Nowak generalize the model to populations on the vertices of graphs. They describe a class of graphs (called "superstars"), with a parameter $k$. Superstars are designed to have an increasing fixation probability as $k$ increases. They state that the probability of fixation tends to $1-r^{-k}$ as graphs get larger but we show that this claim is untrue as stated. Specifically, for $k=5$, we show that the true fixation probability (in the limit, as graphs get larger) is at most $1-1/j(r)$ where $j(r)=Θ(r^4)$, contrary to the claimed result. We do believe that the qualitative claim of Lieberman et al.\ --- that the fixation probability of superstars tends to 1 as $k$ increases --- is correct, and that it can probably be proved along the lines of their sketch. We were able to run larger computer simulations than the ones presented in their paper. However, simulations on graphs of around 40,000 vertices do not support their claim. Perhaps these graphs are too small to exhibit the limiting behaviour.
On Optimality of Myopic Sensing Policy with Imperfect Sensing in Multi-channel Opportunistic Access
Venue: arXiv cs.NI 2012
Year: 2012

We consider the channel access problem under imperfect sensing of channel state in a multi-channel opportunistic communication system, where the state of each channel evolves as an independent and identically distributed Markov process. The considered problem can be cast into a restless multi-armed bandit (RMAB) problem that is of fundamental importance in decision theory. It is well-known that solving the RMAB problem is PSPACE-hard, with the optimal policy usually intractable due to the exponential computation complexity. A natural alternative is to consider the easily implementable myopic policy that maximizes the immediate reward but ignores the impact of the current strategy on the future reward. In this paper, we perform an analytical study on the optimality of the myopic policy under imperfect sensing for the considered RMAB problem. Specifically, for a family of generic and practically important utility functions, we establish the closed-form conditions under which the myopic policy is guaranteed to be optimal even under imperfect sensing. Despite our focus on the opportunistic channel access, the obtained results are generic in nature and are widely applicable in a wide range of engineering domains.
Observability, Controllability and Local Reducibility of Linear Codes on Graphs
Venue: arXiv cs.IT 2012
Year: 2012

This paper is concerned with the local reducibility properties of linear realizations of codes on finite graphs. Trimness and properness are dual properties of constraint codes. A linear realization is locally reducible if any constraint code is not both trim and proper. On a finite cycle-free graph, a linear realization is minimal if and only if every constraint code is both trim and proper. A linear realization is called observable if it is one-to-one, and controllable if all constraints are independent. Observability and controllability are dual properties. An unobservable or uncontrollable realization is locally reducible. A parity-check realization is uncontrollable if and only if it has redundant parity checks. A tail-biting trellis realization is uncontrollable if and only if its trajectories partition into disconnected subrealizations. General graphical realizations do not share this property.
Min-max fair coordinated beamforming in cellular systems via large systems analysis
Venue: arXiv cs.IT 2012
Year: 2012

This paper considers base station (BS) cooperation in the form of coordinated beamforming, focusing on min-max fairness in the power usage subject to target SINR constraints. We show that the optimal beamforming strategies have an interesting nested zero-forcing structure. In the asymptotic regime where the number of antennas at each BS and the number of users in each cell both grow large with their ratio tending to a finite constant, the dimensionality of the optimization is greatly reduced, and only knowledge of statistics is required to solve it. The optimal solution is characterized in general, and an algorithm is proposed that converges to the optimal transmit parameters, for feasible SINR targets. For the two cell case, a simple single parameter characterization is obtained. These asymptotic results provide insights into the average performance, as well as simple but efficient beamforming strategies for the finite system case. In particular, the optimal beamforming strategy from the large systems analysis only requires the base stations to have local instantaneous channel state information; the remaining parameters of the beamformer can be calculated using channel statistics which can easily be shared amongst the base stations.
On Parameterized Gallager's First Bounds for Binary Linear Codes over AWGN Channels
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, nested Gallager regions with a single parameter is introduced to exploit Gallager's first bounding technique (GFBT). We present a necessary and sufficient condition on the optimal parameter. We also present a sufficient condition (with a simple geometrical explanation) under which the optimal parameter does not depend on the signal-to-noise ratio (SNR). With this general framework, three existing upper bounds are revisited, including the tangential bound (TB) of Berlekamp, the sphere bound (SB) of Herzberg and Poltyrev, and the tangential-sphere bound (TSB) of Poltyrev. This paper also reveals that the SB of Herzberg and Poltyrev is equivalent to the SB of Kasami et al., which was rarely cited in literature.
Disjoint Paths Multi-stage Interconnection Networks Stability Problem
Venue: arXiv cs.DC 2012
Year: 2012

This research paper emphasizes that the Stable Matching problems are the same as the problems of stable configurations of Multi-stage Interconnection Networks (MIN). The authors have solved the Stability Problem of Existing Regular Gamma Multi-stage Interconnection Network (GMIN), 3-Disjoint Gamma Multi-stage Interconnection Network (3DGMIN) and 3-Disjoint Path Cyclic Gamma Multi-stage Interconnection Network (3DCGMIN) using the approaches and solutions provided by the Stable Matching Problem. Specifically Stable Marriage Problem is used as an example of Stable Matching. For MINs to prove Stable two existing algorithms are used:-the first algorithm generates the MINs Preferences List in time and second algorithm produces a set of most Optimal Pairs of the Switching Elements (SEs) (derived from the MINs Preferences List) in time. Moreover, the paper also solves the problem of Ties that occurs between the Optimal Pairs. The results are promising as the comparison of the MINs based on their stability shows that the ASEN, ABN, CLN, GMIN, 3DCGMIN are highly stable in comparison to HZTN, QTN, DGMIN. However, on comparing the irregular and regular MINs in totality upon their stability the regular MINs comes out to be more stable than the irregular MINs.
Case Tool: Fast Interconnections with New 3-Disjoint Paths MIN Simulation Module
Venue: arXiv cs.DC 2012
Year: 2012

Multi-stage interconnection networks (MIN) can be designed to achieve fault tolerance and collision solving by providing a set of disjoint paths. In this paper, we are discussing the new simulator added to the tool designed for developing fault tolerant MINs. The designed tool is one of its own kind and will help the user in developing 2 and 3-disjoint path networks. The java technology has been used to design the tool and have been tested on different software platform.