OpenRaiser/Intern-Atlas huggingface dataset:
Faster Algorithms for Multivariate Interpolation with Multiplicities and Simultaneous Polynomial Approximations
Venue: arXiv cs.IT 2015
Year: 2015

The interpolation step in the Guruswami-Sudan algorithm is a bivariate interpolation problem with multiplicities commonly solved in the literature using either structured linear algebra or basis reduction of polynomial lattices. This problem has been extended to three or more variables; for this generalization, all fast algorithms proposed so far rely on the lattice approach. In this paper, we reduce this multivariate interpolation problem to a problem of simultaneous polynomial approximations, which we solve using fast structured linear algebra. This improves the best known complexity bounds for the interpolation step of the list-decoding of Reed-Solomon codes, Parvaresh-Vardy codes, and folded Reed-Solomon codes. In particular, for Reed-Solomon list-decoding with re-encoding, our approach has complexity $\mathcal{O}\tilde{~}(\ell^{ω-1}m^2(n-k))$, where $\ell,m,n,k$ are the list size, the multiplicity, the number of sample points and the dimension of the code, and $ω$ is the exponent of linear algebra; this accelerates the previously fastest known algorithm by a factor of $\ell / m$.
Privacy Games: Optimal User-Centric Data Obfuscation
Venue: arXiv cs.CR 2015
Year: 2015

In this paper, we design user-centric obfuscation mechanisms that impose the minimum utility loss for guaranteeing user's privacy. We optimize utility subject to a joint guarantee of differential privacy (indistinguishability) and distortion privacy (inference error). This double shield of protection limits the information leakage through obfuscation mechanism as well as the posterior inference. We show that the privacy achieved through joint differential-distortion mechanisms against optimal attacks is as large as the maximum privacy that can be achieved by either of these mechanisms separately. Their utility cost is also not larger than what either of the differential or distortion mechanisms imposes. We model the optimization problem as a leader-follower game between the designer of obfuscation mechanism and the potential adversary, and design adaptive mechanisms that anticipate and protect against optimal inference algorithms. Thus, the obfuscation mechanism is optimal against any inference algorithm.
Multi-user Linear Precoding for Multi-polarized Massive MIMO System under Imperfect CSIT
Venue: arXiv cs.IT 2015
Year: 2015

The space limitation and the channel acquisition prevent Massive MIMO from being easily deployed in a practical setup. Motivated by current deployments of LTE-Advanced, the use of multi-polarized antennas can be an efficient solution to address the space constraint. Furthermore, the dual-structured precoding, in which a preprocessing based on the spatial correlation and a subsequent linear precoding based on the short-term channel state information at the transmitter (CSIT) are concatenated, can reduce the feedback overhead efficiently. By grouping and preprocessing spatially correlated mobile stations (MSs), the dimension of the precoding signal space is reduced and the corresponding short-term CSIT dimension is reduced. In this paper, to reduce the feedback overhead further, we propose a dual-structured multi-user linear precoding, in which the subgrouping method based on co-polarization is additionally applied to the spatially grouped MSs in the preprocessing stage. Furthermore, under imperfect CSIT, the proposed scheme is asymptotically analyzed based on random matrix theory. By investigating the behavior of the asymptotic performance, we also propose a new dual-structured precoding in which the precoding mode is switched between two dual-structured precoding strategies with 1) the preprocessing based only on the spatial correlation and 2) the preprocessing based on both the spatial correlation and polarization. Finally, we extend it to 3D dual-structured precoding.
On the Relation Between Identifiability, Differential Privacy and Mutual-Information Privacy
Venue: arXiv cs.CR 2015
Year: 2015

This paper investigates the relation between three different notions of privacy: identifiability, differential privacy and mutual-information privacy. Under a unified privacy-distortion framework, where the distortion is defined to be the Hamming distance of the input and output databases, we establish some fundamental connections between these three privacy notions. Given a distortion level $D$, define $ε_{\mathrm{i}}^*(D)$ to be the smallest (best) identifiability level, and $ε_{\mathrm{d}}^*(D)$ to be the smallest differential privacy level. We characterize $ε_{\mathrm{i}}^*(D)$ and $ε_{\mathrm{d}}^*(D)$, and prove that $ε_{\mathrm{i}}^*(D)-ε_X\leε_{\mathrm{d}}^*(D)\leε_{\mathrm{i}}^*(D)$ for $D$ in some range, where $ε_X$ is a constant depending on the distribution of the original database $X$, and diminishes to zero when the distribution of $X$ is uniform. Furthermore, we show that identifiability and mutual-information privacy are consistent in the sense that given distortion level $D$, the mechanism that optimizes the mutual-information privacy also minimizes the identifiability level.
Adaptive Zero Reaction Motion Control for Free-Floating Space Manipulators
Venue: arXiv cs.SY 2015
Year: 2015

This paper investigates adaptive zero reaction motion control for free-floating space manipulators with uncertain kinematics and dynamics. The challenge in deriving the adaptive reaction null-space (RNS) based control scheme is that it is difficult to obtain a linear expression, which is the basis of the adaptive control. The main contribution of this paper is that we skillfully obtain such a linear expression, based on which, an adaptive version of the RNS-based controller (referred to as the adaptive zero reaction motion controller in the sequel) is developed at the velocity level, taking into account both the kinematic and dynamic uncertainties. It is shown that the proposed controller achieves both the spacecraft attitude regulation and end-effector trajectory tracking. The performance of the proposed adaptive controller is shown by numerical simulations with a planar 3-DOF (degree-of-freedom) space manipulator.
POD/DEIM Reduced-Order Strategies for Efficient Four Dimensional Variational Data Assimilation
Venue: arXiv cs.SY 2015
Year: 2015

This work studies reduced order modeling (ROM) approaches to speed up the solution of variational data assimilation problems with large scale nonlinear dynamical models. It is shown that a key requirement for a successful reduced order solution is that reduced order Karush-Kuhn-Tucker conditions accurately represent their full order counterparts. In particular, accurate reduced order approximations are needed for the forward and adjoint dynamical models, as well as for the reduced gradient. New strategies to construct reduced order based are developed for Proper Orthogonal Decomposition (POD) ROM data assimilation using both Galerkin and Petrov-Galerkin projections. For the first time POD, tensorial POD, and discrete empirical interpolation method (DEIM) are employed to develop reduced data assimilation systems for a geophysical flow model, namely, the two dimensional shallow water equations. Numerical experiments confirm the theoretical framework for Galerkin projection. In the case of Petrov-Galerkin projection, stabilization strategies must be considered for the reduced order models. The new reduced order shallow water data assimilation system provides analyses similar to those produced by the full resolution data assimilation system in one tenth of the computational time.
Matrix-F5 algorithms and tropical Gröbner bases computation
Venue: arXiv cs.SC 2015
Year: 2015

Let $K$ be a field equipped with a valuation. Tropical varieties over $K$ can be defined with a theory of Gröbner bases taking into account the valuation of $K$. Because of the use of the valuation, this theory is promising for stable computations over polynomial rings over a $p$-adic fields.We design a strategy to compute such tropical Gröbner bases by adapting the Matrix-F5 algorithm. Two variants of the Matrix-F5 algorithm, depending on how the Macaulay matrices are built, are available to tropical computation with respective modifications. The former is more numerically stable while the latter is faster.Our study is performed both over any exact field with valuation and some inexact fields like $\mathbb{Q}\_p$ or $\mathbb{F}\_q \llbracket t \rrbracket.$ In the latter case, we track the loss in precision, and show that the numerical stability can compare very favorably to the case of classical Gröbner bases when the valuation is non-trivial. Numerical examples are provided.
A New Framework for the Performance Analysis of Wireless Communications under Hoyt (Nakagami-q) Fading
Venue: arXiv cs.IT 2015
Year: 2015

We present a novel relationship between the distribution of circular and non-circular complex Gaussian random variables. Specifically, we show that the distribution of the squared norm of a non-circular complex Gaussian random variable, usually referred to as squared Hoyt distribution, can be constructed from a conditional exponential distribution. From this fundamental connection we introduce a new approach, the Hoyt transform method, that allows to analyze the performance of a wireless link under Hoyt (Nakagami-q) fading in a very simple way. We illustrate that many performance metrics for Hoyt fading can be calculated by leveraging well-known results for Rayleigh fading and only performing a finite-range integral. We use this technique to obtain novel results for some information and communication-theoretic metrics in Hoyt fading channels.
Distributed Localization and Tracking of Mobile Networks Including Noncooperative Objects - Extended Version
Venue: arXiv cs.IT 2015
Year: 2015

We propose a Bayesian method for distributed sequential localization of mobile networks composed of both cooperative agents and noncooperative objects. Our method provides a consistent combination of cooperative self-localization (CS) and distributed tracking (DT). Multiple mobile agents and objects are localized and tracked using measurements between agents and objects and between agents. For a distributed operation and low complexity, we combine particle-based belief propagation with a consensus or gossip scheme. High localization accuracy is achieved through a probabilistic information transfer between the CS and DT parts of the underlying factor graph. Simulation results demonstrate significant improvements in both agent self-localization and object localization performance compared to separate CS and DT, and very good scaling properties with respect to the numbers of agents and objects.
A Novel Antenna Selection Scheme for Spatially Correlated Massive MIMO Uplinks with Imperfect Channel Estimation
Venue: arXiv cs.IT 2015
Year: 2015

We propose a new antenna selection scheme for a massive MIMO system with a single user terminal and a base station with a large number of antennas. We consider a practical scenario where there is a realistic correlation among the antennas and imperfect channel estimation at the receiver side. The proposed scheme exploits the sparsity of the channel matrix for the effective selection of a limited number of antennas. To this end, we compute a sparse channel matrix by minimising the mean squared error. This optimisation problem is then solved by the well-known orthogonal matching pursuit algorithm. Widely used models for spatial correlation among the antennas and channel estimation errors are considered in this work. Simulation results demonstrate that when the impacts of spatial correlation and imperfect channel estimation introduced, the proposed scheme in the paper can significantly reduce complexity of the receiver, without degrading the system performance compared to the maximum ratio combining.
Capacity Bounds for a Class of Interference Relay Channels
Venue: arXiv cs.IT 2015
Year: 2015

The capacity of a class of Interference Relay Channels (IRC) -the Injective Semideterministic IRC where the relay can only observe one of the sources- is investigated. We first derive a novel outer bound and two inner bounds which are based on a careful use of each of the available cooperative strategies together with the adequate interference decoding technique. The outer bound extends Telatar and Tse's work while the inner bounds contain several known results in the literature as special cases. Our main result is the characterization of the capacity region of the Gaussian class of IRCs studied within a fixed number of bits per dimension -constant gap. The proof relies on the use of the different cooperative strategies in specific SNR regimes due to the complexity of the schemes. As a matter of fact, this issue reveals the complex nature of the Gaussian IRC where the combination of a single coding scheme for the Gaussian relay and interference channel may not lead to a good coding scheme for this problem, even when the focus is only on capacity to within a constant gap over all possible fading statistics.
Parameterized Inapproximability of Target Set Selection and Generalizations
Venue: arXiv cs.CC 2015
Year: 2015

In this paper, we consider the Target Set Selection problem: given a graph and a threshold value $thr(v)$ for any vertex $v$ of the graph, find a minimum size vertex-subset to "activate" s.t. all the vertices of the graph are activated at the end of the propagation process. A vertex $v$ is activated during the propagation process if at least $thr(v)$ of its neighbors are activated. This problem models several practical issues like faults in distributed networks or word-to-mouth recommendations in social networks. We show that for any functions $f$ and $ρ$ this problem cannot be approximated within a factor of $ρ(k)$ in $f(k) \cdot n^{O(1)}$ time, unless FPT = W[P], even for restricted thresholds (namely constant and majority thresholds). We also study the cardinality constraint maximization and minimization versions of the problem for which we prove similar hardness results.
Network-based Isoform Quantification with RNA-Seq Data for Cancer Transcriptome Analysis
Venue: arXiv cs.CE 2015
Year: 2015

High-throughput mRNA sequencing (RNA-Seq) is widely used for transcript quantification of gene isoforms. Since RNA-Seq data alone is often not sufficient to accurately identify the read origins from the isoforms for quantification, we propose to explore protein domain-domain interactions as prior knowledge for integrative analysis with RNA-seq data. We introduce a Network-based method for RNA-Seq-based Transcript Quantification (Net-RSTQ) to integrate protein domain-domain interaction network with short read alignments for transcript abundance estimation. Based on our observation that the abundances of the neighboring isoforms by domain-domain interactions in the network are positively correlated, Net-RSTQ models the expression of the neighboring transcripts as Dirichlet priors on the likelihood of the observed read alignments against the transcripts in one gene. The transcript abundances of all the genes are then jointly estimated with alternating optimization of multiple EM problems. In simulation Net-RSTQ effectively improved isoform transcript quantifications when isoform co-expressions correlate with their interactions. qRT-PCR results on 25 multi-isoform genes in a stem cell line, an ovarian cancer cell line, and a breast cancer cell line also showed that Net-RSTQ estimated more consistent isoform proportions with RNA-Seq data. In the experiments on the RNA-Seq data in The Cancer Genome Atlas (TCGA), the transcript abundances estimated by Net-RSTQ are more informative for patient sample classification of ovarian cancer, breast cancer and lung cancer. All experimental results collectively support that Net-RSTQ is a promising approach for isoform quantification.
Secret-Sharing for NP
Venue: arXiv cs.CR 2015
Year: 2015

A computational secret-sharing scheme is a method that enables a dealer, that has a secret, to distribute this secret among a set of parties such that a "qualified" subset of parties can efficiently reconstruct the secret while any "unqualified" subset of parties cannot efficiently learn anything about the secret. The collection of "qualified" subsets is defined by a Boolean function. It has been a major open problem to understand which (monotone) functions can be realized by a computational secret-sharing schemes. Yao suggested a method for secret-sharing for any function that has a polynomial-size monotone circuit (a class which is strictly smaller than the class of monotone functions in P). Around 1990 Rudich raised the possibility of obtaining secret-sharing for all monotone functions in NP: In order to reconstruct the secret a set of parties must be "qualified" and provide a witness attesting to this fact. Recently, Garg et al. (STOC 2013) put forward the concept of witness encryption, where the goal is to encrypt a message relative to a statement "x in L" for a language L in NP such that anyone holding a witness to the statement can decrypt the message, however, if x is not in L, then it is computationally hard to decrypt. Garg et al. showed how to construct several cryptographic primitives from witness encryption and gave a candidate construction. One can show that computational secret-sharing implies witness encryption for the same language. Our main result is the converse: we give a construction of a computational secret-sharing scheme for any monotone function in NP assuming witness encryption for NP and one-way functions. As a consequence we get a completeness theorem for secret-sharing: computational secret-sharing scheme for any single monotone NP-complete function implies a computational secret-sharing scheme for every monotone function in NP.
Optimal Spectrum Auction Design with Two-Dimensional Truthful Revelations under Uncertain Spectrum Availability
Venue: arXiv cs.NI 2015
Year: 2015

In this paper, we propose a novel sealed-bid auction framework to address the problem of dynamic spectrum allocation in cognitive radio (CR) networks. We design an optimal auction mechanism that maximizes the moderator's expected utility, when the spectrum is not available with certainty. We assume that the moderator employs collaborative spectrum sensing in order to make a reliable inference about spectrum availability. Due to the presence of a collision cost whenever the moderator makes an erroneous inference, and a sensing cost at each CR, we investigate feasibility conditions that guarantee a non-negative utility at the moderator. We present tight theoretical-bounds on instantaneous network throughput and also show that our algorithm provides maximum throughput if the CRs have i.i.d. valuations. Since the moderator fuses CRs' sensing decisions to obtain a global inference regarding spectrum availability, we propose a novel strategy-proof fusion rule that encourages the CRs to simultaneously reveal truthful sensing decisions, along with truthful valuations to the moderator. Numerical examples are also presented to provide insights into the performance of the proposed auction under different scenarios.
Uncertain Price Competition in a Duopoly with Heterogeneous Availability
Venue: arXiv cs.GT 2015
Year: 2015

We study the price competition in a duopoly with an arbitrary number of buyers. Each seller can offer multiple units of a commodity depending on the availability of the commodity which is random and may be different for different sellers. Sellers seek to select a price that will be attractive to the buyers and also fetch adequate profits. The selection will in general depend on the number of units available with the seller and also that of its competitor - the seller may only know the statistics of the latter. The setting captures a secondary spectrum access network, a non-neutral Internet, or a microgrid network in which unused spectrum bands, resources of ISPs, and excess power units constitute the respective commodities of sale. We analyze this price competition as a game, and identify a set of necessary and sufficient properties for the Nash Equilibrium (NE). The properties reveal that sellers randomize their price using probability distributions whose support sets are mutually disjoint and in decreasing order of the number of availability. We prove the uniqueness of a symmetric NE in a symmetric market, and explicitly compute the price distribution in the symmetric NE.
Multiple-Access Relay Wiretap Channel
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we investigate the effects of an additional trusted relay node on the secrecy of multiple-access wiretap channel (MAC-WT) by considering the model of multiple-access relay wiretap channel (MARC-WT). More specifically, first, we investigate the discrete memoryless MARC-WT. Three inner bounds (with respect to decode-forward (DF), noise-forward (NF) and compress-forward (CF) strategies) on the secrecy capacity region are provided. Second, we investigate the degraded discrete memoryless MARC-WT, and present an outer bound on the secrecy capacity region of this degraded model. Finally, we investigate the Gaussian MARC-WT, and find that the NF and CF strategies help to enhance Tekin-Yener's achievable secrecy rate region of Gaussian MAC-WT. Moreover, we find that if the noise variance of the transmitters-relay channel is smaller than that of the transmitters-receiver channel, the DF strategy may also enhance Tekin-Yener's achievable secrecy rate region of Gaussian MAC-WT, and it may perform even better than the NF and CF strategies.
Layer Systems for Proving Confluence
Venue: arXiv cs.LO 2015
Year: 2015

We introduce layer systems for proving generalizations of the modularity of confluence for first-order rewrite systems. Layer systems specify how terms can be divided into layers. We establish structural conditions on those systems that imply confluence. Our abstract framework covers known results like modularity, many-sorted persistence, layer-preservation and currying. We present a counterexample to an extension of persistence to order-sorted rewriting and derive new sufficient conditions for the extension to hold. All our proofs are constructive.
Faulty Successive Cancellation Decoding of Polar Codes for the Binary Erasure Channel
Venue: arXiv cs.IT 2015
Year: 2015

We study faulty successive cancellation decoding of polar codes for the binary erasure channel. To this end, we introduce a simple erasure-based fault model and we show that, under this model, polarization does not happen, meaning that fully reliable communication is not possible at any rate. Moreover, we provide numerical results for the frame erasure rate and bit erasure rate and we study an unequal error protection scheme that can significantly improve the performance of the faulty successive cancellation decoder with negligible overhead.
Optimistic Risk Perception in the Temporal Difference error Explains the Relation between Risk-taking, Gambling, Sensation-seeking and Low Fear
Venue: arXiv cs.LG 2015
Year: 2015

Understanding the affective, cognitive and behavioural processes involved in risk taking is essential for treatment and for setting environmental conditions to limit damage. Using Temporal Difference Reinforcement Learning (TDRL) we computationally investigated the effect of optimism in risk perception in a variety of goal-oriented tasks. Optimism in risk perception was studied by varying the calculation of the Temporal Difference error, i.e., delta, in three ways: realistic (stochastically correct), optimistic (assuming action control), and overly optimistic (assuming outcome control). We show that for the gambling task individuals with 'healthy' perception of control, i.e., action optimism, do not develop gambling behaviour while individuals with 'unhealthy' perception of control, i.e., outcome optimism, do. We show that high intensity of sensations and low levels of fear co-occur due to optimistic risk perception. We found that overly optimistic risk perception (outcome optimism) results in risk taking and in persistent gambling behaviour in addition to high intensity of sensations. We discuss how our results replicate risk-taking related phenomena.