OpenRaiser/Intern-Atlas huggingface dataset:
Towards Optimal Secure Distributed Storage Systems with Exact Repair
Venue: arXiv cs.IT 2014
Year: 2014

Distributed storage systems in the presence of a wiretapper are considered. A distributed storage system (DSS) is parameterized by three parameters (n, k,d), in which a file stored across n distributed nodes, can be recovered from any k out of n nodes. If a node fails, any d out of (n-1) nodes help in the repair of the failed node. For such a (n,k,d)-DSS, two types of wiretapping scenarios are investigated: (a) Type-I (node) adversary which can wiretap the data stored on any l<k nodes; and a more severe (b) Type-II (repair data) adversary which can wiretap the contents of the repair data that is used to repair a set of l failed nodes over time. The focus of this work is on the practically relevant setting of exact repair regeneration in which the repair process must replace a failed node by its exact replica. We make new progress on several non-trivial instances of this problem which prior to this work have been open. The main contribution of this paper is the optimal characterization of the secure storage-vs-exact-repair-bandwidth tradeoff region of a (n,k,d)-DSS, with n<=4 and any l<k in the presence of both Type-I and Type-II adversaries. While the problem remains open for a general (n,k,d)-DSS with n>4, we present extensions of these results to a (n, n-1,n-1)-DSS, in presence of a Type-II adversary that can observe the repair data of any l=(n-2) nodes. The key technical contribution of this work is in developing novel information theoretic converse proofs for the Type-II adversarial scenario. From our results, we show that in the presence of Type-II attacks, the only efficient point in the storage-vs-exact-repair-bandwidth tradeoff is the MBR (minimum bandwidth regenerating) point. This is in sharp contrast to the case of a Type-I attack in which the storage-vs-exact-repair-bandwidth tradeoff allows a spectrum of operating points beyond the MBR point.
Modernizing PHCpack through phcpy
Venue: arXiv cs.MS 2014
Year: 2014

PHCpack is a large software package for solving systems of polynomial equations. The executable phc is menu driven and file oriented. This paper describes the development of phcpy, a Python interface to PHCpack. Instead of navigating through menus, users of phcpy solve systems in the Python shell or via scripts. Persistent objects replace intermediate files.
Network Reconstruction from Intrinsic Noise
Venue: arXiv cs.SY 2014
Year: 2014

This paper considers the problem of inferring an unknown network of dynamical systems driven by unknown, intrinsic, noise inputs. Equivalently we seek to identify direct causal dependencies among manifest variables only from observations of these variables. For linear, time-invariant systems of minimal order, we characterise under what conditions this problem is well posed. We first show that if the transfer matrix from the inputs to manifest states is minimum phase, this problem has a unique solution irrespective of the network topology. This is equivalent to there being only one valid spectral factor (up to a choice of signs of the inputs) of the output spectral density. If the assumption of phase-minimality is relaxed, we show that the problem is characterised by a single Algebraic Riccati Equation (ARE), of dimension determined by the number of latent states. The number of solutions to this ARE is an upper bound on the number of solutions for the network. We give necessary and sufficient conditions for any two dynamical networks to have equal output spectral density, which can be used to construct all equivalent networks. Extensive simulations quantify the number of solutions for a range of problem sizes. For a slightly simpler case, we also provide an algorithm to construct all equivalent networks from the output spectral density.
Gap Amplification for Small-Set Expansion via Random Walks
Venue: arXiv cs.CC 2014
Year: 2014

In this work, we achieve gap amplification for the Small-Set Expansion problem. Specifically, we show that an instance of the Small-Set Expansion Problem with completeness $ε$ and soundness $\frac{1}{2}$ is at least as difficult as Small-Set Expansion with completeness $ε$ and soundness $f(ε)$, for any function $f(ε)$ which grows faster than $\sqrtε$. We achieve this amplification via random walks -- our gadget is the graph with adjacency matrix corresponding to a random walk on the original graph. An interesting feature of our reduction is that unlike gap amplification via parallel repetition, the size of the instances (number of vertices) produced by the reduction remains the same.
Towards Statistical Prioritization for Software Product Lines Testing
Venue: arXiv cs.SE 2014
Year: 2014

Software Product Lines (SPL) are inherently difficult to test due to the combinatorial explosion of the number of products to consider. To reduce the number of products to test, sampling techniques such as combinatorial interaction testing have been proposed. They usually start from a feature model and apply a coverage criterion (e.g. pairwise feature interaction or dissimilarity) to generate tractable, fault-finding, lists of configurations to be tested. Prioritization can also be used to sort/generate such lists, optimizing coverage criteria or weights assigned to features. However, current sampling/prioritization techniques barely take product behavior into account. We explore how ideas of statistical testing, based on a usage model (a Markov chain), can be used to extract configurations of interest according to the likelihood of their executions. These executions are gathered in featured transition systems, compact representation of SPL behavior. We discuss possible scenarios and give a prioritization procedure illustrated on an example.
Intrinsic filtering on Lie groups with applications to attitude estimation
Venue: arXiv cs.SY 2014
Year: 2014

This paper proposes a probabilistic approach to the problem of intrinsic filtering of a system on a matrix Lie group with invariance properties. The problem of an invariant continuous-time model with discrete-time measurements is cast into a rigorous stochastic and geometric framework. Building upon the theory of continuous-time invariant observers, we show that, as in the linear case, the error equation is a Markov chain that does not depend on the state estimate. Thus, when the filter's gains are held fixed, and the filter admits almost-global convergence properties with noise turned off, the noisy error's distribution is proved to converge to a stationary distribution, providing insight into the mathematical theory of filtering on Lie groups. For engineering purposes we also introduce the discrete-time Invariant Extended Kalman Filter, for which the trusted covariance matrix is shown to asymptotically converge, and some numerically more involved sample-based methods as well to compute the Kalman gains. The methods are applied to attitude estimation, allowing to derive novel theoretical results in this field, and illustrated through simulations on synthetic data.
Product Backlog Rating: A Case Study On Measuring Test Quality In Scrum
Venue: arXiv cs.SE 2014
Year: 2014

Agile software development methodologies focus on software projects which are behind schedule or highly likely to have a problematic development phase. In the last decade, Agile methods have transformed from cult techniques to mainstream methodologies. Scrum, an Agile software development method, has been widely adopted due to its adaptive nature. This paper presents a metric that measures the quality of the testing process in a Scrum process. As product quality and process quality correlate, improved test quality can ensure high quality products. Also, gaining experience from eight years of successful Scrum implementation at SoftwarePeople, we describe the Scrum process emphasizing the testing process. We propose a metric Product Backlog Rating (PBR) to assess the testing process in Scrum. PBR considers the complexity of the features to be developed in an iteration of Scrum, assesses test ratings and offers a numerical score of the testing process. This metric is able to provide a comprehensive overview of the testing process over the development cycle of a product. We present a case study which shows how the metric is used at SoftwarePeople. The case study explains some features that have been developed in a Sprint in terms of feature complexity and potential test assessment difficulties and shows how PBR is calculated during the Sprint. We propose a test process assessment metric that provides insights into the Scrum testing process. However, the metric needs further evaluation considering associated resources (e.g., quality assurance engineers, the length of the Scrum cycle).
Characterizing Strategic Cascades on Networks
Venue: arXiv cs.SI 2014
Year: 2014

Transmission of disease, spread of information and rumors, adoption of new products, and many other network phenomena can be fruitfully modeled as cascading processes, where actions chosen by nodes influence the subsequent behavior of neighbors in the network graph. Current literature on cascades tends to assume nodes choose myopically based on the state of choices already taken by other nodes. We examine the possibility of strategic choice, where agents representing nodes anticipate the choices of others who have not yet decided, and take into account their own influence on such choices. Our study employs the framework of Chierichetti et al. [2012], who (under assumption of myopic node behavior) investigate the scheduling of node decisions to promote cascades of product adoptions preferred by the scheduler. We show that when nodes behave strategically, outcomes can be extremely different. We exhibit cases where in the strategic setting 100% of agents adopt, but in the myopic setting only an arbitrarily small epsilon % do. Conversely, we present cases where in the strategic setting 0% of agents adopt, but in the myopic setting (100-epsilon)% do, for any constant epsilon > 0. Additionally, we prove some properties of cascade processes with strategic agents, both in general and for particular classes of graphs.
Half-integrality, LP-branching and FPT Algorithms
Venue: arXiv cs.DS 2014
Year: 2014

A recent trend in parameterized algorithms is the application of polytope tools (specifically, LP-branching) to FPT algorithms (e.g., Cygan et al., 2011; Narayanaswamy et al., 2012). However, although interesting results have been achieved, the methods require the underlying polytope to have very restrictive properties (half-integrality and persistence), which are known only for few problems (essentially Vertex Cover (Nemhauser and Trotter, 1975) and Node Multiway Cut (Garg et al., 1994)). Taking a slightly different approach, we view half-integrality as a \emph{discrete} relaxation of a problem, e.g., a relaxation of the search space from $\{0,1\}^V$ to $\{0,1/2,1\}^V$ such that the new problem admits a polynomial-time exact solution. Using tools from CSP (in particular Thapper and Živný, 2012) to study the existence of such relaxations, we provide a much broader class of half-integral polytopes with the required properties, unifying and extending previously known cases. In addition to the insight into problems with half-integral relaxations, our results yield a range of new and improved FPT algorithms, including an $O^*(|Σ|^{2k})$-time algorithm for node-deletion Unique Label Cover with label set $Σ$ and an $O^*(4^k)$-time algorithm for Group Feedback Vertex Set, including the setting where the group is only given by oracle access. All these significantly improve on previous results. The latter result also implies the first single-exponential time FPT algorithm for Subset Feedback Vertex Set, answering an open question of Cygan et al. (2012). Additionally, we propose a network flow-based approach to solve some cases of the relaxation problem. This gives the first linear-time FPT algorithm to edge-deletion Unique Label Cover.
Scaling Graph-based Semi Supervised Learning to Large Number of Labels Using Count-Min Sketch
Venue: arXiv cs.LG 2014
Year: 2014

Graph-based Semi-supervised learning (SSL) algorithms have been successfully used in a large number of applications. These methods classify initially unlabeled nodes by propagating label information over the structure of graph starting from seed nodes. Graph-based SSL algorithms usually scale linearly with the number of distinct labels (m), and require O(m) space on each node. Unfortunately, there exist many applications of practical significance with very large m over large graphs, demanding better space and time complexity. In this paper, we propose MAD-SKETCH, a novel graph-based SSL algorithm which compactly stores label distribution on each node using Count-min Sketch, a randomized data structure. We present theoretical analysis showing that under mild conditions, MAD-SKETCH can reduce space complexity at each node from O(m) to O(log m), and achieve similar savings in time complexity as well. We support our analysis through experiments on multiple real world datasets. We observe that MAD-SKETCH achieves similar performance as existing state-of-the-art graph- based SSL algorithms, while requiring smaller memory footprint and at the same time achieving up to 10x speedup. We find that MAD-SKETCH is able to scale to datasets with one million labels, which is beyond the scope of existing graph- based SSL algorithms.
Overlapping community detection in signed networks
Venue: arXiv cs.SI 2014
Year: 2014

Complex networks considering both positive and negative links have gained considerable attention during the past several years. Community detection is one of the main challenges for complex network analysis. Most of the existing algorithms for community detection in a signed network aim at providing a hard-partition of the network where any node should belong to a community or not. However, they cannot detect overlapping communities where a node is allowed to belong to multiple communities. The overlapping communities widely exist in many real world networks. In this paper, we propose a signed probabilistic mixture (SPM) model for overlapping community detection in signed networks. Compared with the existing models, the advantages of our methodology are (i) providing soft-partition solutions for signed networks; (ii) providing soft-memberships of nodes. Experiments on a number of signed networks show that our SPM model: (i) can identify assortative structures or disassortative structures as the same as other state-of-the-art models; (ii) can detect overlapping communities; (iii) outperform other state-of-the-art models at shedding light on the community detection in synthetic signed networks.
A Unifying Model for External Noise Sources and ISI in Diffusive Molecular Communication
Venue: arXiv cs.IT 2014
Year: 2014

This paper considers the impact of external noise sources, including interfering transmitters, on a diffusive molecular communication system, where the impact is measured as the number of noise molecules expected to be observed at a passive receiver. A unifying model for noise, multiuser interference, and intersymbol interference is presented, where, under certain circumstances, interference can be approximated as a noise source that is emitting continuously. The model includes the presence of advection and molecule degradation. The time-varying and asymptotic impact is derived for a series of special cases, some of which facilitate closed-form solutions. Simulation results show the accuracy of the expressions derived for the impact of a continuously-emitting noise source, and show how approximating intersymbol interference as a noise source can simplify the calculation of the expected bit error probability of a weighted sum detector.
Monotone Simultaneous Embedding of Directed Paths
Venue: arXiv cs.CG 2014
Year: 2014

We study monotone simultaneous embeddings of upward planar digraphs, which are simultaneous embeddings where the drawing of each digraph is upward planar, and the directions of the upwardness of different graphs can differ. We first consider the special case where each digraph is a directed path. In contrast to the known result that any two directed paths admit a monotone simultaneous embedding, there exist examples of three paths that do not admit such an embedding for any possible choice of directions of monotonicity. We prove that if a monotone simultaneous embedding of three paths exists then it also exists for any possible choice of directions of monotonicity. We provide a polynomial-time algorithm that, given three paths, decides whether a monotone simultaneous embedding exists and, in the case of existence, also constructs such an embedding. On the other hand, we show that already for three paths, any monotone simultaneous embedding might need a grid of exponential (w.r.t. the number of vertices) size. For more than three paths, we present a polynomial-time algorithm that, given any number of paths and predefined directions of monotonicity, decides whether the paths admit a monotone simultaneous embedding with respect to the given directions, including the construction of a solution if it exists. Further, we show several implications of our results on monotone simultaneous embeddings of general upward planar digraphs. Finally, we discuss complexity issues related to our problems.
Modeling Oligarchs' Campaign Donations and Ideological Preferences with Simulated Agent-Based Spatial Elections
Venue: arXiv cs.MA 2014
Year: 2014

In this paper, we investigate the interactions among oligarchs, political parties, and voters using an agent-based modeling approach. We introduce the OLIGO model, which is based on the spatial model of democracy, where voters have positions in a policy space and vote for the party that appears closest to them, and parties move in policy space to seek more votes. We extend the existing literature on agent-based models of political economy in the following manner: (1) by introducing a new class of agents- oligarchs - that represent leaders of firms in a common industry who lobby for beneficial subsidies through campaign donations; and (2) by investigating the effects of ideological preferences of the oligarchs on legislative action. We test hypotheses from the literature in political economics on the behavior of oligarchs and political parties as they interact, under conditions of imperfect information and bounded rationality. Our key results indicate that (1) oligarchs tend to donate less to political campaigns when the parties are more resistant to changing their policies, or when voters are more informed; and (2) if Oligarchs donate to parties based on a combination of ideological and profit motivations, Oligarchs will tend to donate at a lower equilibrium level, due to the influence of lost profits. We validate these outcomes via comparisons to real world polling data on changes in party support over time.
Counting Triangles in Real-World Graph Streams: Dealing with Repeated Edges and Time Windows
Venue: arXiv cs.DS 2014
Year: 2014

Real-world graphs often manifest as a massive temporal stream of edges. The need for real-time analysis of such large graph streams has led to progress on low memory, one-pass streaming graph algorithms. These algorithms were designed for simple graphs, assuming an edge is not repeated in the stream. Real graph streams however, are almost always multigraphs i.e., they contain many duplicate edges. The assumption of no repeated edges requires an extra pass *storing all the edges* just for deduplication, which defeats the purpose of small memory algorithms. We describe an algorithm for estimating the triangle count of a multigraph stream of edges. We show that all previous streaming algorithms for triangle counting fail for multigraph streams, despite their impressive accuracies for simple graphs. The bias created by duplicate edges is a major problem, and leads these algorithms astray. Our algorithm avoids these biases through careful debiasing strategies and has provable theoretical guarantees and excellent empirical performance. Our algorithm builds on the previously introduced wedge sampling methodology. Another challenge in analyzing temporal graphs is finding the right temporal window size. Our algorithm seamlessly handles multiple time windows, and does not require committing to any window size(s) a priori. We apply our algorithm to discover fascinating transitivity and triangle trends in real-world graph streams.
Staying Alive: System Design for Self-Sufficient Sensor Networks
Venue: arXiv cs.NI 2014
Year: 2014

Self-sustainability is a crucial step for modern sensor networks. Here, we offer an original and comprehensive framework for autonomous sensor networks powered by renewable energy sources. We decompose our design into two nested optimization steps: the inner step characterizes the optimal network operating point subject to an average energy consumption constraint, while the outer step provides online energy management policies making the system energetically self-sufficient in the presence of unpredictable and intermittent energy sources. Our framework sheds new light into the design of pragmatic schemes for the control of energy harvesting sensor networks} and permits to gauge the impact of key sensor network parameters, such as the battery capacity, the harvester size, the information transmission rate and the radio duty cycle. We analyze the robustness of the obtained energy management policies in the cases where the nodes have differing energy inflow statistics and where topology changes may occur, devising effective heuristics. Our energy management policies are finally evaluated considering real solar radiation traces, validating them against state of the art solutions and describing the impact of relevant design choices in terms of achievable network throughput and battery level dynamics.
Backhaul Limited Asymmetric Cooperation for MIMO Cellular Networks via Semidefinite Relaxation
Venue: arXiv cs.IT 2014
Year: 2014

Multicell cooperation has recently attracted tremendous attention because of its ability to eliminate intercell interference and increase spectral efficiency. However, the enormous amount of information being exchanged, including channel state information and user data, over backhaul links may deteriorate the network performance in a realistic system. This paper adopts a backhaul cost metric that considers the number of active directional cooperation links, which gives a first order measurement of the backhaul loading required in asymmetric Multiple-Input Multiple-Output (MIMO) cooperation. We focus on a downlink scenario for multi-antenna base stations and single-antenna mobile stations. The design problem is minimizing the number of active directional cooperation links and jointly optimizing the beamforming vectors among the cooperative BSs subject to signal-to-interference-and-noise-ratio (SINR) constraints at the mobile station. This problem is non-convex and solving it requires combinatorial search. A practical algorithm based on smooth approximation and semidefinite relaxation is proposed to solve the combinatorial problem efficiently. We show that semidefinite relaxation is tight with probability 1 in our algorithm and stationary convergence is guaranteed. Simulation results show the saving of backhaul cost and power consumption is notable compared with several baseline schemes and its effectiveness is demonstrated.