OpenRaiser/Intern-Atlas huggingface dataset:
Suicide ideation of individuals in online social networks
Venue: arXiv cs.SI 2013
Year: 2013

Suicide explains the largest number of death tolls among Japanese adolescents in their twenties and thirties. Suicide is also a major cause of death for adolescents in many other countries. Although social isolation has been implicated to influence the tendency to suicidal behavior, the impact of social isolation on suicide in the context of explicit social networks of individuals is scarcely explored. To address this question, we examined a large data set obtained from a social networking service dominant in Japan. The social network is composed of a set of friendship ties between pairs of users created by mutual endorsement. We carried out the logistic regression to identify users' characteristics, both related and unrelated to social networks, which contribute to suicide ideation. We defined suicide ideation of a user as the membership to at least one active user-defined community related to suicide. We found that the number of communities to which a user belongs to, the intransitivity (i.e., paucity of triangles including the user), and the fraction of suicidal neighbors in the social network, contributed the most to suicide ideation in this order. Other characteristics including the age and gender contributed little to suicide ideation. We also found qualitatively the same results for depressive symptoms.
Zipf and non-Zipf Laws for Homogeneous Markov Chain
Venue: arXiv cs.IT 2013
Year: 2013

Let us consider a homogeneous Markov chain with discrete time and with a finite set of states $E_0,\ldots,E_n$ such that the state $E_0$ is absorbing, states $E_1,\ldots,E_n$ are nonrecurrent. The goal of this work is to study frequencies of trajectories in this chain, i.e., "words" composed of symbols $E_1,\ldots,E_n$ ending with the "space" $E_0$. Let us order words according to their probabilities; denote by $p(t)$ the probability of the $t$th word in this list. In this paper we prove that in a typical case the asymptotics of the function $p(t)$ has a power character, and define its exponent from the matrix of transition probabilities. If this matrix is block-diagonal, then with some specific values of transition probabilities the power asymptotics gets (logarithmic) addends. But if this matrix is rather sparse, then probabilities quickly decrease; namely, the rate of asymptotics is greater than that of the power one, but not greater than that of the exponential one. We also establish necessary and sufficient conditions for the exponential order of decrease and obtain a formula for determining the exponent from the transition probability matrix and the initial distribution vector.
Optimal rates for first-order stochastic convex optimization under Tsybakov noise condition
Venue: arXiv cs.LG 2013
Year: 2013

We focus on the problem of minimizing a convex function $f$ over a convex set $S$ given $T$ queries to a stochastic first order oracle. We argue that the complexity of convex minimization is only determined by the rate of growth of the function around its minimizer $x^*_{f,S}$, as quantified by a Tsybakov-like noise condition. Specifically, we prove that if $f$ grows at least as fast as $\|x-x^*_{f,S}\|^κ$ around its minimum, for some $κ> 1$, then the optimal rate of learning $f(x^*_{f,S})$ is $Θ(T^{-\fracκ{2κ-2}})$. The classic rate $Θ(1/\sqrt T)$ for convex functions and $Θ(1/T)$ for strongly convex functions are special cases of our result for $κ\rightarrow \infty$ and $κ=2$, and even faster rates are attained for $κ<2$. We also derive tight bounds for the complexity of learning $x_{f,S}^*$, where the optimal rate is $Θ(T^{-\frac{1}{2κ-2}})$. Interestingly, these precise rates for convex optimization also characterize the complexity of active learning and our results further strengthen the connections between the two fields, both of which rely on feedback-driven queries.
Reference Point Methods and Approximation in Multicriteria Optimization
Venue: arXiv cs.DS 2013
Year: 2013

Operations research applications often pose multicriteria problems. Mathematical research on multicriteria problems predominantly revolves around the set of Pareto optimal solutions, while in practice, methods that output a single solution are more widespread. In real-world multicriteria optimization, reference point methods are widely used and successful examples of such methods. A reference point solution is the solution closest to a given reference point in the objective space. We study the approximation of reference point solutions. In particular, we establish that approximating reference point solutions is polynomially equivalent to approximating the Pareto set. Complementing these results, we show for a number of general algorithmic techniques in single criteria optimization how they can be lifted to reference point optimization. In particular, we lift the link between dynamic programming and FPTAS, as well as oblivious LP-rounding techniques. The latter applies, e.g., to Set Cover and several machine scheduling problems.
Embedding the dual complex of hyper-rectangular partitions
Venue: arXiv cs.CG 2013
Year: 2013

A rectangular partition is the partition of an (axis-aligned) rectangle into interior-disjoint rectangles. We ask whether a rectangular partition permits a "nice" drawing of its dual, that is, a straight-line embedding of it such that each dual vertex is placed into the rectangle that it represents. We show that deciding whether such a drawing exists is NP-complete. Moreover, we consider the drawing where a vertex is placed in the center of the represented rectangle and consider sufficient conditions for this drawing to be nice. This question is studied both in the plane and for the higher-dimensional generalization of rectangular partitions.
Solving Stochastic Büchi Games on Infinite Arenas with a Finite Attractor
Venue: arXiv cs.LO 2013
Year: 2013

We consider games played on an infinite probabilistic arena where the first player aims at satisfying generalized Büchi objectives almost surely, i.e., with probability one. We provide a fixpoint characterization of the winning sets and associated winning strategies in the case where the arena satisfies the finite-attractor property. From this we directly deduce the decidability of these games on probabilistic lossy channel systems.
Transmit Optimization with Improper Gaussian Signaling for Interference Channels
Venue: arXiv cs.IT 2013
Year: 2013

This paper studies the achievable rates of Gaussian interference channels with additive white Gaussian noise (AWGN), when improper or circularly asymmetric complex Gaussian signaling is applied. For the Gaussian multiple-input multiple-output interference channel (MIMO-IC) with the interference treated as Gaussian noise, we show that the user's achievable rate can be expressed as a summation of the rate achievable by the conventional proper or circularly symmetric complex Gaussian signaling in terms of the users' transmit covariance matrices, and an additional term, which is a function of both the users' transmit covariance and pseudo-covariance matrices. The additional degrees of freedom in the pseudo-covariance matrix, which is conventionally set to be zero for the case of proper Gaussian signaling, provide an opportunity to further improve the achievable rates of Gaussian MIMO-ICs by employing improper Gaussian signaling. To this end, this paper proposes widely linear precoding, which efficiently maps proper information-bearing signals to improper transmitted signals at each transmitter for any given pair of transmit covariance and pseudo-covariance matrices. In particular, for the case of two-user Gaussian single-input single-output interference channel (SISO-IC), we propose a joint covariance and pseudo-covariance optimization algorithm with improper Gaussian signaling to achieve the Pareto-optimal rates. By utilizing the separable structure of the achievable rate expression, an alternative algorithm with separate covariance and pseudo-covariance optimization is also proposed, which guarantees the rate improvement over conventional proper Gaussian signaling.
On the Capacity of the Two-user Gaussian Causal Cognitive Interference Channel
Venue: arXiv cs.IT 2013
Year: 2013

This paper considers the two-user Gaussian Causal Cognitive Interference Channel (GCCIC), which consists of two source-destination pairs that share the same channel and where one full-duplex cognitive source can causally learn the message of the primary source through a noisy link. The GCCIC is an interference channel with unilateral source cooperation that better models practical cognitive radio networks than the commonly used model which assumes that one source has perfect non-causal knowledge of the other source's message. First the sum-capacity of the symmetric GCCIC is determined to within a constant gap. Then, the insights gained from the derivation of the symmetric sum-capacity are extended to characterize the whole capacity region to within a constant gap for more general cases. In particular, the capacity is determined (a) to within 2 bits for the fully connected GCCIC when, roughly speaking, the interference is not weak at both receivers, (b) to within 2 bits for the Z-channel, i.e., when there is no interference from the primary user, and (c) to within 2 bits for the S-channel, i.e., when there is no interference from the secondary user. The parameter regimes where the GCCIC is equivalent, in terms of generalized degrees-of-freedom, to the noncooperative interference channel (i.e., unilateral causal cooperation is not useful), to the non-causal cognitive interference channel (i.e., causal cooperation attains the ultimate limit of cognitive radio technology), and to bilateral source cooperation are identified. These comparisons shed lights into the parameter regimes and network topologies that in practice might provide an unbounded throughput gain compared to currently available (non cognitive) technologies.
Fast directional spatially localized spherical harmonic transform
Venue: arXiv cs.IT 2013
Year: 2013

We propose a transform for signals defined on the sphere that reveals their localized directional content in the spatio-spectral domain when used in conjunction with an asymmetric window function. We call this transform the directional spatially localized spherical harmonic transform (directional SLSHT) which extends the SLSHT from the literature whose usefulness is limited to symmetric windows. We present an inversion relation to synthesize the original signal from its directional-SLSHT distribution for an arbitrary window function. As an example of an asymmetric window, the most concentrated band-limited eigenfunction in an elliptical region on the sphere is proposed for directional spatio-spectral analysis and its effectiveness is illustrated on the synthetic and Mars topographic data-sets. Finally, since such typical data-sets on the sphere are of considerable size and the directional SLSHT is intrinsically computationally demanding depending on the band-limits of the signal and window, a fast algorithm for the efficient computation of the transform is developed. The floating point precision numerical accuracy of the fast algorithm is demonstrated and a full numerical complexity analysis is presented.
Conditional Information Inequalities for Entropic and Almost Entropic Points
Venue: arXiv cs.IT 2013
Year: 2013

We study conditional linear information inequalities, i.e., linear inequalities for Shannon entropy that hold for distributions whose entropies meet some linear constraints. We prove that some conditional information inequalities cannot be extended to any unconditional linear inequalities. Some of these conditional inequalities hold for almost entropic points, while others do not. We also discuss some counterparts of conditional information inequalities for Kolmogorov complexity.
Automated Dynamic Offset Applied to Cell Association
Venue: arXiv cs.GT 2013
Year: 2013

In this paper, we develop a hierarchical Bayesian game framework for automated dynamic offset selection. Users compete to maximize their throughput by picking the best locally serving radio access network (RAN) with respect to their own measurement, their demand and a partial statistical channel state information (CSI) of other users. In particular, we investigate the properties of a Stackelberg game, in which the base station is a player on its own. We derive analytically the utilities related to the channel quality perceived by users to obtain the equilibria. We study the Price of Anarchy (PoA) of such system, where the PoA is the ratio of the social welfare attained when a network planner chooses policies to maximize social welfare versus the social welfare attained in Nash/Stackeleberg equilibrium when users choose their policies strategically. We show by means of a Stackelberg formulation, how the operator, by sending appropriate information about the state of the channel, can configure a dynamic offset that optimizes its global utility while users maximize their individual utilities. The proposed hierarchical decision approach for wireless networks can reach a good trade-off between the global network performance at the equilibrium and the requested amount of signaling. Typically, it is shown that when the network goal is orthogonal to user's goal, this can lead the users to a misleading association problem.
Measuring the Complexity of Ultra-Large-Scale Adaptive Systems
Venue: arXiv cs.NE 2013
Year: 2013

Ultra-large scale (ULS) systems are becoming pervasive. They are inherently complex, which makes their design and control a challenge for traditional methods. Here we propose the design and analysis of ULS systems using measures of complexity, emergence, self-organization, and homeostasis based on information theory. These measures allow the evaluation of ULS systems and thus can be used to guide their design. We evaluate the proposal with a ULS computing system provided with adaptation mechanisms. We show the evolution of the system with stable and also changing workload, using different fitness functions. When the adaptive plan forces the system to converge to a predefined performance level, the nodes may result in highly unstable configurations, that correspond to a high variance in time of the measured complexity. Conversely, if the adaptive plan is less "aggressive", the system may be more stable, but the optimal performance may not be achieved.
Performance Analysis of Macrodiversity MIMO Systems with MMSE and ZF Receivers in Flat Rayleigh Fading
Venue: arXiv cs.IT 2013
Year: 2013

Consider a multiuser system where an arbitrary number of users communicate with a distributed receive array over independent Rayleigh fading paths. The receive array performs minimum mean squared error (MMSE) or zero forcing (ZF) combining and perfect channel state information is assumed at the receiver. This scenario is well-known and exact analysis is possible when the receive antennas are located in a single array. However, when the antennas are distributed, the individual links all have different average signal to noise ratio (SNRs) and this is a much more challenging problem. In this paper, we provide approximate distributions for the output SNR of a ZF receiver and the output signal to interference plus noise ratio (SINR) of an MMSE receiver. In addition, simple high SNR approximations are provided for the symbol error rate (SER) of both receivers assuming M-PSK or M-QAM modulations. These high SNR results provide array gain and diversity gain information as well as a remarkably simple functional link between performance and the link powers.
Incentive Mechanisms based on Minority Game in Heterogeneous DTNs
Venue: arXiv cs.GT 2013
Year: 2013

In this paper we design an incentive mechanism for heterogeneous Delay Tolerant Networks (DTNs). The proposed mechanism tackles a core problem of such systems: how to induce coordination of DTN relays in order to achieve a target performance figure, e.g., delivery probability or end-to-end delay, under a given constraint in term of network resources, e.g., number of active nodes or energy consumption. Also, we account for the realistic case when the cost for taking part in the forwarding process varies with the devices' technology or the users' habits. Finally, the scheme is truly applicable to DTNs since it works with no need for end-to-end connectivity. In this context, we first introduce the basic coordination mechanism leveraging the notion of a Minority Game. In this game, relays compete to be in the population minority and their utility is defined in combination with a rewarding mechanism. The rewards in turn configure as a control by which the network operator controls the desired operating point for the DTN. To this aim, we provide a full characterization of the equilibria of the game in the case of heterogeneous DTNs. Finally, a learning algorithm based on stochastic approximations provably drives the system to the equilibrium solution without requiring perfect state information at relay nodes or at the source node and without using end-to-end communications to implement the rewarding scheme. We provide extensive numerical results to validate the proposed scheme.
Learning Theory Approach to Minimum Error Entropy Criterion
Venue: arXiv cs.LG 2013
Year: 2013

We consider the minimum error entropy (MEE) criterion and an empirical risk minimization learning algorithm in a regression setting. A learning theory approach is presented for this MEE algorithm and explicit error bounds are provided in terms of the approximation ability and capacity of the involved hypothesis space when the MEE scaling parameter is large. Novel asymptotic analysis is conducted for the generalization error associated with Renyi's entropy and a Parzen window function, to overcome technical difficulties arisen from the essential differences between the classical least squares problems and the MEE setting. A semi-norm and the involved symmetrized least squares error are introduced, which is related to some ranking algorithms.
Sharp analysis of low-rank kernel matrix approximations
Venue: arXiv cs.LG 2013
Year: 2013

We consider supervised learning problems within the positive-definite kernel framework, such as kernel ridge regression, kernel logistic regression or the support vector machine. With kernels leading to infinite-dimensional feature spaces, a common practical limiting difficulty is the necessity of computing the kernel matrix, which most frequently leads to algorithms with running time at least quadratic in the number of observations n, i.e., O(n^2). Low-rank approximations of the kernel matrix are often considered as they allow the reduction of running time complexities to O(p^2 n), where p is the rank of the approximation. The practicality of such methods thus depends on the required rank p. In this paper, we show that in the context of kernel ridge regression, for approximations based on a random subset of columns of the original kernel matrix, the rank p may be chosen to be linear in the degrees of freedom associated with the problem, a quantity which is classically used in the statistical analysis of such methods, and is often seen as the implicit number of parameters of non-parametric estimators. This result enables simple algorithms that have sub-quadratic running time complexity, but provably exhibit the same predictive performance than existing algorithms, for any given problem instance, and not only for worst-case situations.
Upper Bounds on the Number of Codewords of Some Separating Codes
Venue: arXiv cs.IT 2013
Year: 2013

Separating codes have their applications in collusion-secure fingerprinting for generic digital data, while they are also related to the other structures including hash family, intersection code and group testing. In this paper we study upper bounds for separating codes. First, some new upper bound for restricted separating codes is proposed. Then we illustrate that the Upper Bound Conjecture for separating Reed-Solomon codes inherited from Silverberg's question holds true for almost all Reed-Solomon codes.
DisC Diversity: Result Diversification based on Dissimilarity and Coverage
Venue: arXiv cs.DB 2013
Year: 2013

Recently, result diversification has attracted a lot of attention as a means to improve the quality of results retrieved by user queries. In this paper, we propose a new, intuitive definition of diversity called DisC diversity. A DisC diverse subset of a query result contains objects such that each object in the result is represented by a similar object in the diverse subset and the objects in the diverse subset are dissimilar to each other. We show that locating a minimum DisC diverse subset is an NP-hard problem and provide heuristics for its approximation. We also propose adapting DisC diverse subsets to a different degree of diversification. We call this operation zooming. We present efficient implementations of our algorithms based on the M-tree, a spatial index structure, and experimentally evaluate their performance.
A Simple Proof of Threshold Saturation for Coupled Vector Recursions
Venue: arXiv cs.IT 2013
Year: 2013

Convolutional low-density parity-check (LDPC) codes (or spatially-coupled codes) have now been shown to achieve capacity on binary-input memoryless symmetric channels. The principle behind this surprising result is the threshold-saturation phenomenon, which is defined by the belief-propagation threshold of the spatially-coupled ensemble saturating to a fundamental threshold defined by the uncoupled system. Previously, the authors demonstrated that potential functions can be used to provide a simple proof of threshold saturation for coupled scalar recursions. In this paper, we present a simple proof of threshold saturation that applies to a wide class of coupled vector recursions. The conditions of the theorem are verified for the density-evolution equations of: (i) joint decoding of irregular LDPC codes for a Slepian-Wolf problem with erasures, (ii) joint decoding of irregular LDPC codes on an erasure multiple-access channel, and (iii) general protograph codes on the BEC. This proves threshold saturation for these systems.
In-Vivo Bytecode Instrumentation for Improving Privacy on Android Smartphones in Uncertain Environments
Venue: arXiv cs.CR 2013
Year: 2013

In this paper we claim that an efficient and readily applicable means to improve privacy of Android applications is: 1) to perform runtime monitoring by instrumenting the application bytecode and 2) in-vivo, i.e. directly on the smartphone. We present a tool chain to do this and present experimental results showing that this tool chain can run on smartphones in a reasonable amount of time and with a realistic effort. Our findings also identify challenges to be addressed before running powerful runtime monitoring and instrumentations directly on smartphones. We implemented two use-cases leveraging the tool chain: BetterPermissions, a fine-grained user centric permission policy system and AdRemover an advertisement remover. Both prototypes improve the privacy of Android systems thanks to in-vivo bytecode instrumentation.
Syntactic Complexity of R- and J-Trivial Regular Languages
Venue: arXiv cs.FL 2013
Year: 2013

The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of the class of regular languages is the maximal syntactic complexity of languages in that class, taken as a function of the state complexity n of these languages. We study the syntactic complexity of R- and J-trivial regular languages, and prove that n! and floor of [e(n-1)!] are tight upper bounds for these languages, respectively. We also prove that 2^{n-1} is the tight upper bound on the state complexity of reversal of J-trivial regular languages.
Hitting all Maximal Independent Sets of a Bipartite Graph
Venue: arXiv cs.CC 2013
Year: 2013

We prove that given a bipartite graph G with vertex set V and an integer k, deciding whether there exists a subset of V of size k hitting all maximal independent sets of G is complete for the class Sigma_2^P.