OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Locally Repairable and Secure Codes for Distributed Storage Systems
Venue: arXiv cs.IT 2013
Year: 2013

This paper aims to go beyond resilience into the study of security and local-repairability for distributed storage systems (DSS). Security and local-repairability are both important as features of an efficient storage system, and this paper aims to understand the trade-offs between resilience, security, and local-repairability in these systems. In particular, this paper first investigates security in the presence of colluding eavesdroppers, where eavesdroppers are assumed to work together in decoding stored information. Second, the paper focuses on coding schemes that enable optimal local repairs. It further brings these two concepts together, to develop locally repairable coding schemes for DSS that are secure against eavesdroppers. The main results of this paper include: a. An improved bound on the secrecy capacity for minimum storage regenerating codes, b. secure coding schemes that achieve the bound for some special cases, c. a new bound on minimum distance for locally repairable codes, d. code construction for locally repairable codes that attain the minimum distance bound, and e. repair-bandwidth-efficient locally repairable codes with and without security constraints.
Parameterized Complexity and Kernel Bounds for Hard Planning Problems
Venue: arXiv cs.DS 2013
Year: 2013

The propositional planning problem is a notoriously difficult computational problem. Downey et al. (1999) initiated the parameterized analysis of planning (with plan length as the parameter) and Bäckström et al. (2012) picked up this line of research and provided an extensive parameterized analysis under various restrictions, leaving open only one stubborn case. We continue this work and provide a full classification. In particular, we show that the case when actions have no preconditions and at most $e$ postconditions is fixed-parameter tractable if $e\leq 2$ and W[1]-complete otherwise. We show fixed-parameter tractability by a reduction to a variant of the Steiner Tree problem; this problem has been shown fixed-parameter tractable by Guo et al. (2007). If a problem is fixed-parameter tractable, then it admits a polynomial-time self-reduction to instances whose input size is bounded by a function of the parameter, called the kernel. For some problems, this function is even polynomial which has desirable computational implications. Recent research in parameterized complexity has focused on classifying fixed-parameter tractable problems on whether they admit polynomial kernels or not. We revisit all the previously obtained restrictions of planning that are fixed-parameter tractable and show that none of them admits a polynomial kernel unless the polynomial hierarchy collapses to its third level.
Stochastic ADMM for Nonsmooth Optimization
Venue: arXiv cs.LG 2013
Year: 2013

We present a stochastic setting for optimization problems with nonsmooth convex separable objective functions over linear equality constraints. To solve such problems, we propose a stochastic Alternating Direction Method of Multipliers (ADMM) algorithm. Our algorithm applies to a more general class of nonsmooth convex functions that does not necessarily have a closed-form solution by minimizing the augmented function directly. We also demonstrate the rates of convergence for our algorithm under various structural assumptions of the stochastic functions: $O(1/\sqrt{t})$ for convex functions and $O(\log t/t)$ for strongly convex functions. Compared to previous literature, we establish the convergence rate of ADMM algorithm, for the first time, in terms of both the objective value and the feasibility violation.
Cramér-Rao bounds for synchronization of rotations
Venue: arXiv cs.IT 2013
Year: 2013

Synchronization of rotations is the problem of estimating a set of rotations R_i in SO(n), i = 1, ..., N, based on noisy measurements of relative rotations R_i R_j^T. This fundamental problem has found many recent applications, most importantly in structural biology. We provide a framework to study synchronization as estimation on Riemannian manifolds for arbitrary n under a large family of noise models. The noise models we address encompass zero-mean isotropic noise, and we develop tools for Gaussian-like as well as heavy-tail types of noise in particular. As a main contribution, we derive the Cramér-Rao bounds of synchronization, that is, lower-bounds on the variance of unbiased estimators. We find that these bounds are structured by the pseudoinverse of the measurement graph Laplacian, where edge weights are proportional to measurement quality. We leverage this to provide interpretation in terms of random walks and visualization tools for these bounds in both the anchored and anchor-free scenarios. Similar bounds previously established were limited to rotations in the plane and Gaussian-like noise.
The Complexity of Optimal Mechanism Design
Venue: arXiv cs.GT 2013
Year: 2013

Myerson's seminal work provides a computationally efficient revenue-optimal auction for selling one item to multiple bidders. Generalizing this work to selling multiple items at once has been a central question in economics and algorithmic game theory, but its complexity has remained poorly understood. We answer this question by showing that a revenue-optimal auction in multi-item settings cannot be found and implemented computationally efficiently, unless ZPP contains P^#P. This is true even for a single additive bidder whose values for the items are independently distributed on two rational numbers with rational probabilities. Our result is very general: we show that it is hard to compute any encoding of an optimal auction of any format (direct or indirect, truthful or non-truthful) that can be implemented in expected polynomial time. In particular, under well-believed complexity-theoretic assumptions, revenue-optimization in very simple multi-item settings can only be tractably approximated. We note that our hardness result applies to randomized mechanisms in a very simple setting, and is not an artifact of introducing combinatorial structure to the problem by allowing correlation among item values, introducing combinatorial valuations, or requiring the mechanism to be deterministic (whose structure is readily combinatorial). Our proof is enabled by a flow-interpretation of the solutions of an exponential-size linear program for revenue maximization with an additional supermodularity constraint.
Exact and Stable Recovery of Rotations for Robust Synchronization
Venue: arXiv cs.IT 2013
Year: 2013

The synchronization problem over the special orthogonal group $SO(d)$ consists of estimating a set of unknown rotations $R_1,R_2,...,R_n$ from noisy measurements of a subset of their pairwise ratios $R_{i}^{-1}R_{j}$. The problem has found applications in computer vision, computer graphics, and sensor network localization, among others. Its least squares solution can be approximated by either spectral relaxation or semidefinite programming followed by a rounding procedure, analogous to the approximation algorithms of \textsc{Max-Cut}. The contribution of this paper is three-fold: First, we introduce a robust penalty function involving the sum of unsquared deviations and derive a relaxation that leads to a convex optimization problem; Second, we apply the alternating direction method to minimize the penalty function; Finally, under a specific model of the measurement noise and for both complete and random measurement graphs, we prove that the rotations are exactly and stably recovered, exhibiting a phase transition behavior in terms of the proportion of noisy measurements. Numerical simulations confirm the phase transition behavior for our method as well as its improved accuracy compared to existing methods.
Optimizing Abstract Abstract Machines
Venue: arXiv cs.PL 2013
Year: 2013

The technique of abstracting abstract machines (AAM) provides a systematic approach for deriving computable approximations of evaluators that are easily proved sound. This article contributes a complementary step-by-step process for subsequently going from a naive analyzer derived under the AAM approach, to an efficient and correct implementation. The end result of the process is a two to three order-of-magnitude improvement over the systematically derived analyzer, making it competitive with hand-optimized implementations that compute fundamentally less precise results.
Spectrum Access through Threats in Cognitive Radio Networks
Venue: arXiv cs.GT 2013
Year: 2013

We consider multiple access games in which primary users are interested in maximizing their confidential data rate at the minimum possible transmission power and secondary users employ eavesdropping as a leverage to maximize their data rate to a common destination at minimum transmission energy. For the non-cooperative static game, Nash equilibria in pure and mixed strategies are derived and shown to be Pareto inefficient in general, when channel gains are common knowledge. For the two-player Stackelberg game where the primary user is the leader, it is shown that the secondary user is forced to play as the follower where the Stackelberg equilibrium dominates the Nash equilibrium, even if the eavesdropper channel is better than the primary channel. Here, the utility achieved by the Stackelberg game Pareto-dominates the achieved Nash utility. Moreover, we study the unknown eavesdropper channel case numerically where the primary user has only statistical knowledge about the channel gain. We compare the results to the first scenario and show that it is not always beneficial for the cognitive user to hide the actual eavesdropper channel gain. Finally, we extend the equilibrium analysis to a multiple SU game where the primary system selects a subset of the secondary users to transmit such that the performance of the primary users is maximized.
Optimizing Synchronization Algorithm for Auto-parallelizing Compiler
Venue: arXiv cs.DC 2013
Year: 2013

In this paper, we focus on the need for two approaches to optimize producer and consumer synchronization for auto-parallelizing compiler. Emphasis is placed on the construction of a criterion model by which the compiler reduce the number of synchronization operations needed to synchronize the dependence in a loop and perform optimization reduces the overhead of enforcing all dependence. In accordance with our study, we transform to modify and eliminate dependence on iteration space diagram (ISD), and carry out the problems of acyclic and cyclic dependence in detail. we eliminate partial dependence and optimize the synchronize instructions. Some didactic examples are included to illustrate the optimize procedure.
Inference of the Russian drug community from one of the largest social networks in the Russian Federation
Venue: arXiv cs.SI 2013
Year: 2013

The criminal nature of narcotics complicates the direct assessment of a drug community, while having a good understanding of the type of people drawn or currently using drugs is vital for finding effective intervening strategies. Especially for the Russian Federation this is of immediate concern given the dramatic increase it has seen in drug abuse since the fall of the Soviet Union in the early nineties. Using unique data from the Russian social network 'LiveJournal' with over 39 million registered users worldwide, we were able for the first time to identify the on-line drug community by context sensitive text mining of the users' blogs using a dictionary of known drug-related official and 'slang' terminology. By comparing the interests of the users that most actively spread information on narcotics over the network with the interests of the individuals outside the on-line drug community, we found that the 'average' drug user in the Russian Federation is generally mostly interested in topics such as Russian rock, non-traditional medicine, UFOs, Buddhism, yoga and the occult. We identify three distinct scale-free sub-networks of users which can be uniquely classified as being either 'infectious', 'susceptible' or 'immune'.
Fast Marginalized Block Sparse Bayesian Learning Algorithm
Venue: arXiv cs.IT 2013
Year: 2013

The performance of sparse signal recovery from noise corrupted, underdetermined measurements can be improved if both sparsity and correlation structure of signals are exploited. One typical correlation structure is the intra-block correlation in block sparse signals. To exploit this structure, a framework, called block sparse Bayesian learning (BSBL), has been proposed recently. Algorithms derived from this framework showed superior performance but they are not very fast, which limits their applications. This work derives an efficient algorithm from this framework, using a marginalized likelihood maximization method. Compared to existing BSBL algorithms, it has close recovery performance but is much faster. Therefore, it is more suitable for large scale datasets and applications requiring real-time implementation.
Model Checking Parse Trees
Venue: arXiv cs.LO 2013
Year: 2013

Parse trees are fundamental syntactic structures in both computational linguistics and compilers construction. We argue in this paper that, in both fields, there are good incentives for model-checking sets of parse trees for some word according to a context-free grammar. We put forward the adequacy of propositional dynamic logic (PDL) on trees in these applications, and study as a sanity check the complexity of the corresponding model-checking problem: although complete for exponential time in the general case, we find natural restrictions on grammars for our applications and establish complexities ranging from nondeterministic polynomial time to polynomial space in the relevant cases.
Generalized Degrees of Freedom for Network-Coded Cognitive Interference Channel
Venue: arXiv cs.IT 2013
Year: 2013

We study a two-user cognitive interference channel (CIC) where one of the transmitters (primary) has knowledge of a linear combination (over an appropriate finite field) of the two information messages. We refer to this channel model as Network-Coded CIC, since the linear combination may be the result of some linear network coding scheme implemented in the backbone wired network.In this paper, we characterize the generalized degrees of freedom (GDoF) for the Gaussian Network-Coded CIC. For achievability, we use the novel Precoded Compute-and-Forward (PCoF) and Dirty Paper Coding (DPC), based on nested lattice codes. As a consequence of the GDoF characterization, we show that knowing "mixed data" (linear combinations of the information messages) provides a {\em multiplicative} gain for the Gaussian CIC, if the power ratio of signal-to-noise (SNR) to interference-to-noise (INR) is larger than certain threshold. For example, when $\SNR=\INR$, the Network-Coded cognition yields a 100% gain over the classical Gaussian CIC.
Optimal Power and Range Adaptation for Green Broadcasting
Venue: arXiv cs.IT 2013
Year: 2013

Improving energy efficiency is key to network providers maintaining profit levels and an acceptable carbon footprint in the face of rapidly increasing data traffic in cellular networks in the coming years. The energy-saving concept studied in this paper is the adaptation of a base station's (BS's) transmit power levels and coverage area according to channel conditions and traffic load. The traffic load in cellular networks exhibits significant fluctuations in both space and time, which can be exploited, through cell range adaptation, for energy saving. In this paper, we design short- and long-term BS power control (STPC and LTPC respectively) policies for the OFDMA-based downlink of a single-cell system, where bandwidth is dynamically and equally shared among a random number of mobile users (MUs). STPC is a function of all MUs' channel gains that maintains the required user-level quality of service (QoS), while LTPC (including BS on-off control) is a function of traffic density that minimizes the long-term energy consumption at the BS under a minimum throughput constraint. We first develop a power scaling law that relates the (short-term) average transmit power at BS with the given cell range and MU density. Based on this result, we derive the optimal (long-term) transmit adaptation policy by considering a joint range adaptation and LTPC problem. By identifying the fact that energy saving at BS essentially comes from two major energy saving mechanisms (ESMs), i.e. range adaptation and BS on-off power control, we propose low-complexity suboptimal schemes with various combinations of the two ESMs to investigate their impacts on system energy consumption. It is shown that when the network throughput is low, BS on-off power control is the most effective ESM, while when the network throughput is higher, range adaptation becomes more effective.
Scalable Spectral Algorithms for Community Detection in Directed Networks
Venue: arXiv cs.SI 2013
Year: 2013

Community detection has been one of the central problems in network studies and directed network is particularly challenging due to asymmetry among its links. In this paper, we found that incorporating the direction of links reveals new perspectives on communities regarding to two different roles, source and terminal, that a node plays in each community. Intriguingly, such communities appear to be connected with unique spectral property of the graph Laplacian of the adjacency matrix and we exploit this connection by using regularized SVD methods. We propose harvesting algorithms, coupled with regularized SVDs, that are linearly scalable for efficient identification of communities in huge directed networks. The proposed algorithm shows great performance and scalability on benchmark networks in simulations and successfully recovers communities in real network applications.
Calculation of orthant probabilities by the holonomic gradient method
Venue: arXiv cs.NA 2013
Year: 2013

We apply the holonomic gradient method (HGM) introduced by [9] to the calculation of orthant probabilities of multivariate normal distribution. The holonomic gradient method applied to orthant probabilities is found to be a variant of Plackett's recurrence relation ([14]). However an implementation of the method yields recurrence relations more suitable for numerical computation than Plackett's recurrence relation. We derive some theoretical results on the holonomic system for the orthant probabilities. These results show that multivariate normal orthant probabilities possess some remarkable properties from the viewpoint of holonomic systems. Finally we show that numerical performance of our method is comparable or superior compared to existing methods.
Orientation Determination from Cryo-EM images Using Least Unsquared Deviation
Venue: arXiv cs.LG 2013
Year: 2013

A major challenge in single particle reconstruction from cryo-electron microscopy is to establish a reliable ab-initio three-dimensional model using two-dimensional projection images with unknown orientations. Common-lines based methods estimate the orientations without additional geometric information. However, such methods fail when the detection rate of common-lines is too low due to the high level of noise in the images. An approximation to the least squares global self consistency error was obtained using convex relaxation by semidefinite programming. In this paper we introduce a more robust global self consistency error and show that the corresponding optimization problem can be solved via semidefinite relaxation. In order to prevent artificial clustering of the estimated viewing directions, we further introduce a spectral norm term that is added as a constraint or as a regularization term to the relaxed minimization problem. The resulted problems are solved by using either the alternating direction method of multipliers or an iteratively reweighted least squares procedure. Numerical experiments with both simulated and real images demonstrate that the proposed methods significantly reduce the orientation estimation error when the detection rate of common-lines is low.
Collective Phenomena and Non-Finite State Computation in a Human Social System
Venue: arXiv cs.SI 2013
Year: 2013

We investigate the computational structure of a paradigmatic example of distributed social interaction: that of the open-source Wikipedia community. We examine the statistical properties of its cooperative behavior, and perform model selection to determine whether this aspect of the system can be described by a finite-state process, or whether reference to an effectively unbounded resource allows for a more parsimonious description. We find strong evidence, in a majority of the most-edited pages, in favor of a collective-state model, where the probability of a "revert" action declines as the square root of the number of non-revert actions seen since the last revert. We provide evidence that the emergence of this social counter is driven by collective interaction effects, rather than properties of individual users.
An Efficient Simulation Algorithm on Kripke Structures
Venue: arXiv cs.LO 2013
Year: 2013

A number of algorithms for computing the simulation preorder (and equivalence) on Kripke structures are available. Let Sigma denote the state space, -> the transition relation and Psim the partition of Sigma induced by simulation equivalence. While some algorithms are designed to reach the best space bounds, whose dominating additive term is |Psim|^2, other algorithms are devised to attain the best time complexity O(|Psim||->|). We present a novel simulation algorithm which is both space and time efficient: it runs in O(|Psim|^2 log|Psim| + |Sigma|log|Sigma|) space and O(|Psim||->|log|Sigma|) time. Our simulation algorithm thus reaches the best space bounds while closely approaching the best time complexity.
The geometric stability of Voronoi diagrams in normed spaces which are not uniformly convex
Venue: arXiv cs.CG 2013
Year: 2013

The Voronoi diagram is a geometric object which is widely used in many areas. Recently it has been shown that under mild conditions Voronoi diagrams have a certain continuity property: small perturbations of the sites yield small perturbations in the shapes of the corresponding Voronoi cells. However, this result is based on the assumption that the ambient normed space is uniformly convex. Unfortunately, simple counterexamples show that if uniform convexity is removed, then instability can occur. Since Voronoi diagrams in normed spaces which are not uniformly convex do appear in theory and practice, e.g., in the plane with the Manhattan (ell_1) distance, it is natural to ask whether the stability property can be generalized to them, perhaps under additional assumptions. This paper shows that this is indeed the case assuming the unit sphere of the space has a certain (non-exotic) structure and the sites satisfy a certain "general position" condition related to it. The condition on the unit sphere is that it can be decomposed into at most one "rotund part" and at most finitely many non-degenerate convex parts. Along the way certain topological properties of Votonoi cells (e.g., that the induced bisectors are not "fat") are proved.