OpenRaiser/Intern-Atlas huggingface dataset:
Coherent Causal Memory
Venue: arXiv cs.DC 2014
Year: 2014

Coherent causal memory (CCM) is causal memory in which prefixes of an execution can be mapped to global memory states in a consistent way. While CCM requires conflicting pairs of writes to be globally ordered, it allows writes to remain unordered with respect to both reads and nonconflicting writes. Nevertheless, it supports assertional, state-based program reasoning using generalized Owicki-Gries proof outlines (where assertions can be attached to any causal program edge). Indeed, we show that from a reasoning standpoint, CCM differs from sequentially consistent (SC) memory only in that ghost code added by the user is not allowed to introduce new write-write races. While CCM provides most of the formal reasoning leverage of SC memory, it is much more efficiently implemented. As an illustration, we describe a simple programming discipline that provides CCM on top of x86-TSO. The discipline is considerably more relaxed than the one needed to ensure SC; for example, it introduces no burden whatsoever for programs in which at most one thread writes to any variable.
Genie Chains: Exploring Outer Bounds on the Degrees of Freedom of MIMO Interference Networks
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we propose a novel genie chains approach to obtain information theoretic degrees of freedom (DoF) outer bounds for MIMO wireless interference networks. This new approach creates a chain of mappings from genie signals provided to a receiver to the exposed signal spaces at that receiver, which then serve as the genie signals for the next receiver in the chain subject to certain linear independence requirements, essentially converting an information theoretic DoF outer bound problem into a linear algebra problem. Several applications of the genie chains approach are presented.
On the Minimal Revision Problem of Specification Automata
Venue: arXiv cs.SY 2014
Year: 2014

As robots are being integrated into our daily lives, it becomes necessary to provide guarantees on the safe and provably correct operation. Such guarantees can be provided using automata theoretic task and mission planning where the requirements are expressed as temporal logic specifications. However, in real-life scenarios, it is to be expected that not all user task requirements can be realized by the robot. In such cases, the robot must provide feedback to the user on why it cannot accomplish a given task. Moreover, the robot should indicate what tasks it can accomplish which are as "close" as possible to the initial user intent. This paper establishes that the latter problem, which is referred to as the minimal specification revision problem, is NP complete. A heuristic algorithm is presented that can compute good approximations to the Minimal Revision Problem (MRP) in polynomial time. The experimental study of the algorithm demonstrates that in most problem instances the heuristic algorithm actually returns the optimal solution. Finally, some cases where the algorithm does not return the optimal solution are presented.
Power System Parameters Forecasting Using Hilbert-Huang Transform and Machine Learning
Venue: arXiv cs.LG 2014
Year: 2014

A novel hybrid data-driven approach is developed for forecasting power system parameters with the goal of increasing the efficiency of short-term forecasting studies for non-stationary time-series. The proposed approach is based on mode decomposition and a feature analysis of initial retrospective data using the Hilbert-Huang transform and machine learning algorithms. The random forests and gradient boosting trees learning techniques were examined. The decision tree techniques were used to rank the importance of variables employed in the forecasting models. The Mean Decrease Gini index is employed as an impurity function. The resulting hybrid forecasting models employ the radial basis function neural network and support vector regression. Apart from introduction and references the paper is organized as follows. The section 2 presents the background and the review of several approaches for short-term forecasting of power system parameters. In the third section a hybrid machine learning-based algorithm using Hilbert-Huang transform is developed for short-term forecasting of power system parameters. Fourth section describes the decision tree learning algorithms used for the issue of variables importance. Finally in section six the experimental results in the following electric power problems are presented: active power flow forecasting, electricity price forecasting and for the wind speed and direction forecasting.
Fast Structuring of Radio Networks for Multi-Message Communications
Venue: arXiv cs.NI 2014
Year: 2014

We introduce collision free layerings as a powerful way to structure radio networks. These layerings can replace hard-to-compute BFS-trees in many contexts while having an efficient randomized distributed construction. We demonstrate their versatility by using them to provide near optimal distributed algorithms for several multi-message communication primitives. Designing efficient communication primitives for radio networks has a rich history that began 25 years ago when Bar-Yehuda et al. introduced fast randomized algorithms for broadcasting and for constructing BFS-trees. Their BFS-tree construction time was $O(D \log^2 n)$ rounds, where $D$ is the network diameter and $n$ is the number of nodes. Since then, the complexity of a broadcast has been resolved to be $T_{BC} = Θ(D \log \frac{n}{D} + \log^2 n)$ rounds. On the other hand, BFS-trees have been used as a crucial building block for many communication primitives and their construction time remained a bottleneck for these primitives. We introduce collision free layerings that can be used in place of BFS-trees and we give a randomized construction of these layerings that runs in nearly broadcast time, that is, w.h.p. in $T_{Lay} = O(D \log \frac{n}{D} + \log^{2+ε} n)$ rounds for any constant $ε>0$. We then use these layerings to obtain: (1) A randomized algorithm for gathering $k$ messages running w.h.p. in $O(T_{Lay} + k)$ rounds. (2) A randomized $k$-message broadcast algorithm running w.h.p. in $O(T_{Lay} + k \log n)$ rounds. These algorithms are optimal up to the small difference in the additive poly-logarithmic term between $T_{BC}$ and $T_{Lay}$. Moreover, they imply the first optimal $O(n \log n)$ round randomized gossip algorithm.
Approximating the Regular Graphic TSP in near linear time
Venue: arXiv cs.DS 2014
Year: 2014

We present a randomized approximation algorithm for computing traveling salesperson tours in undirected regular graphs. Given an $n$-vertex, $k$-regular graph, the algorithm computes a tour of length at most $\left(1+\frac{7}{\ln k-O(1)}\right)n$, with high probability, in $O(nk \log k)$ time. This improves upon a recent result by Vishnoi (\cite{Vishnoi12}, FOCS 2012) for the same problem, in terms of both approximation factor, and running time. The key ingredient of our algorithm is a technique that uses edge-coloring algorithms to sample a cycle cover with $O(n/\log k)$ cycles with high probability, in near linear time. Additionally, we also give a deterministic $\frac{3}{2}+O\left(\frac{1}{\sqrt{k}}\right)$ factor approximation algorithm running in time $O(nk)$.
A Signal-Space Analysis of Spatial Self-Interference Isolation for Full-Duplex Wireless
Venue: arXiv cs.IT 2014
Year: 2014

The challenge to in-band full-duplex wireless communication is managing self-interference. Many designs have employed spatial isolation mechanisms, such as shielding or multi-antenna beamforming, to isolate the self-interference wave from the receiver. Such spatial isolation methods are effective, but by confining the transmit and receive signals to a subset of the available space, the full spatial resources of the channel be under-utilized, expending a cost that may nullify the net benefit of operating in full-duplex mode. In this paper we leverage an antenna-theory-based channel model to analyze the spatial degrees of freedom available to a full-duplex capable base station, and observe that whether or not spatial isolation out-performs time-division (i.e. half-duplex) depends heavily on the geometric distribution of scatterers. Unless the angular spread of the objects that scatter to the intended users is overlapped by the spread of objects that backscatter to the base station, then spatial isolation outperforms time division, otherwise time division may be optimal.
Asymptotics of Fingerprinting and Group Testing: Tight Bounds from Channel Capacities
Venue: arXiv cs.IT 2014
Year: 2014

In this work we consider the large-coalition asymptotics of various fingerprinting and group testing games, and derive explicit expressions for the capacities for each of these models. We do this both for simple decoders (fast but suboptimal) and for joint decoders (slow but optimal). For fingerprinting, we show that if the pirate strategy is known, the capacity often decreases linearly with the number of colluders, instead of quadratically as in the uninformed fingerprinting game. For many attacks the joint capacity is further shown to be strictly higher than the simple capacity. For group testing, we improve upon known results about the joint capacities, and derive new explicit asymptotics for the simple capacities. These show that existing simple group testing algorithms are suboptimal, and that simple decoders cannot asymptotically be as efficient as joint decoders. For the traditional group testing model, we show that the gap between the simple and joint capacities is a factor 1.44 for large numbers of defectives.
How Complex Contagions Spread Quickly in the Preferential Attachment Model and Other Time-Evolving Networks
Venue: arXiv cs.SI 2014
Year: 2014

In this paper, we study the spreading speed of complex contagions in a social network. A $k$-complex contagion starts from a set of initially infected seeds such that any node with at least $k$ infected neighbors gets infected. Simple contagions, i.e., $k=1$, quickly spread to the entire network in small world graphs. However, fast spreading of complex contagions appears to be less likely and more delicate; the successful cases depend crucially on the network structure~\cite{G08,Ghasemiesfeh:2013:CCW}. Our main result shows that complex contagions can spread fast in a general family of time-evolving networks that includes the preferential attachment model~\cite{barabasi99emergence}. We prove that if the initial seeds are chosen as the oldest nodes in a network of this family, a $k$-complex contagion covers the entire network of $n$ nodes in $O(\log n)$ steps. We show that the choice of the initial seeds is crucial. If the initial seeds are uniformly randomly chosen in the PA model, even with a polynomial number of them, a complex contagion would stop prematurely. The oldest nodes in a preferential attachment model are likely to have high degrees. However, we remark that it is actually not the power law degree distribution per se that facilitates fast spreading of complex contagions, but rather the evolutionary graph structure of such models. Some members of the said family do not even have a power-law distribution. We also prove that complex contagions are fast in the copy model~\cite{KumarRaRa00}, a variant of the preferential attachment family. Finally, we prove that when a complex contagion starts from an arbitrary set of initial seeds on a general graph, determining if the number of infected vertices is above a given threshold is $\mathbf{P}$-complete. Thus, one cannot hope to categorize all the settings in which complex contagions percolate in a graph.
Optimal Encodings for Range Majority Queries
Venue: arXiv cs.DS 2014
Year: 2014

We study the problem of designing a data structure that reports the positions of the distinct $τ$-majorities within any range of an array $A[1,n]$, without storing $A$. A $τ$-majority in a range $A[i,j]$, for $0<τ< 1$, is an element that occurs more than $τ(j-i+1)$ times in $A[i,j]$. We show that $Ω(n\log(1/τ))$ bits are necessary for any data structure able just to count the number of distinct $τ$-majorities in any range. Then, we design a structure using $O(n\log(1/τ))$ bits that returns one position of each $τ$-majority of $A[i,j]$ in $O((1/τ)\log\log_w(1/τ)\log n)$ time, on a RAM machine with word size $w$ (it can output any further position where each $τ$-majority occurs in $O(1)$ additional time). Finally, we show how to remove a $\log n$ factor from the time by adding $O(n\log\log n)$ bits of space to the structure.
To Share or Not to Share in Client-Side Encrypted Clouds
Venue: arXiv cs.CR 2014
Year: 2014

With the advent of cloud computing, a number of cloud providers have arisen to provide Storage-as-a-Service (SaaS) offerings to both regular consumers and business organizations. SaaS (different than Software-as-a-Service in this context) refers to an architectural model in which a cloud provider provides digital storage on their own infrastructure. Three models exist amongst SaaS providers for protecting the confidentiality data stored in the cloud: 1) no encryption (data is stored in plain text), 2) server-side encryption (data is encrypted once uploaded), and 3) client-side encryption (data is encrypted prior to upload). This paper seeks to identify weaknesses in the third model, as it claims to offer 100% user data confidentiality throughout all data transactions (e.g., upload, download, sharing) through a combination of Network Traffic Analysis, Source Code Decompilation, and Source Code Disassembly. The weaknesses we uncovered primarily center around the fact that the cloud providers we evaluated were each operating in a Certificate Authority capacity to facilitate data sharing. In this capacity, they assume the role of both certificate issuer and certificate authorizer as denoted in a Public-Key Infrastructure (PKI) scheme - which gives them the ability to view user data contradicting their claims of 100% data confidentiality. We have collated our analysis and findings in this paper and explore some potential solutions to address these weaknesses in these sharing methods. The solutions proposed are a combination of best practices associated with the use of PKI and other cryptographic primitives generally accepted for protecting the confidentiality of shared information.
An Introduction to Digital Signature Schemes
Venue: arXiv cs.CR 2014
Year: 2014

Today, all types of digital signature schemes emphasis on secure and best verification methods. Different digital signature schemes are used in order for the websites, security organizations, banks and so on to verify user's validity. Digital signature schemes are categorized to several types such as proxy, on-time, batch and so on. In this paper, different types of schemes are compared based on security level, efficiency, difficulty of algorithm and so on. Results show that best scheme depends on security, complexity and other important parameters. We tried simply to define the schemes and review them in practice.
Normal, Abby Normal, Prefix Normal
Venue: arXiv cs.FL 2014
Year: 2014

A prefix normal word is a binary word with the property that no substring has more 1s than the prefix of the same length. This class of words is important in the context of binary jumbled pattern matching. In this paper we present results about the number $pnw(n)$ of prefix normal words of length $n$, showing that $pnw(n) =Ω\left(2^{n - c\sqrt{n\ln n}}\right)$ for some $c$ and $pnw(n) = O \left(\frac{2^n (\ln n)^2}{n}\right)$. We introduce efficient algorithms for testing the prefix normal property and a "mechanical algorithm" for computing prefix normal forms. We also include games which can be played with prefix normal words. In these games Alice wishes to stay normal but Bob wants to drive her "abnormal" -- we discuss which parameter settings allow Alice to succeed.
TreQ-CG: Clustering Accelerates High-Throughput Sequencing Read Mapping
Venue: arXiv cs.CE 2014
Year: 2014

As high-throughput sequencers become standard equipment outside of sequencing centers, there is an increasing need for efficient methods for pre-processing and primary analysis. While a vast literature proposes methods for HTS data analysis, we argue that significant improvements can still be gained by exploiting expensive pre-processing steps which can be amortized with savings from later stages. We propose a method to accelerate and improve read mapping based on an initial clustering of possibly billions of high-throughput sequencing reads, yielding clusters of high stringency and a high degree of overlap. This clustering improves on the state-of-the-art in running time for small datasets and, for the first time, makes clustering high-coverage human libraries feasible. Given the efficiently computed clusters, only one representative read from each cluster needs to be mapped using a traditional readmapper such as BWA, instead of individually mapping all reads. On human reads, all processing steps, including clustering and mapping, only require 11%-59% of the time for individually mapping all reads, achieving speed-ups for all readmappers, while minimally affecting mapping quality. This accelerates a highly sensitive readmapper such as Stampy to be competitive with a fast readmapper such as BWA on unclustered reads.
A blind robust watermarking scheme based on svd and circulant matrices
Venue: arXiv cs.MM 2014
Year: 2014

Multimedia security has been the aim point of considerable research activity because of its wide application area. The major technology to achieve copyright protection, content authentication, access control and multimedia security is watermarking which is the process of embedding data into a multimedia element such as image or audio, this embedded data can later be extracted from, or detected in the embedded element for different purposes. In this work, a blind watermarking algorithm based on SVD and circulant matrices has been presented. Every circulant matrix is associated with a matrix for which the SVD decomposition coincides with the spectral decomposition. This leads to improve the Chandra algorithm [1], our presentation will include a discussion on the data hiding capacity, watermark transparency and robustness against a wide range of common image processing attacks.
QoS group based optimal retransmission medium access protocol for wireless sensor networks
Venue: arXiv cs.NI 2014
Year: 2014

This paper presents, a Group Based Optimal Retransmission Medium Access (GORMA) Protocol is designed that combines protocol of Collision Avoidance (CA) and energy management for low-cost, short-range, low-data rate and low-energy sensor nodes applications in environment monitoring, agriculture, industrial plants etc. In this paper, the GORMA protocol focuses on efficient MAC protocol to provide autonomous Quality of Service (QoS) to the sensor nodes in one-hop QoS retransmission group and two QoS groups in WSNs where the source nodes do not have receiver circuits. Hence, they can only transmit data to a sink node, but cannot receive acknowledgement control signals from the sink node. The proposed protocol GORMA provides QoS to the nodes which work independently on predefined time by allowing them to transmit each packet an optimal number of times within a given period. Our simulation results shows that the performance of GORMA protocol, which maximize the delivery probability of one-hop QoS group and two QoS groups and minimize the energy consumption.
Markov Chain Analysis of Evolution Strategies on a Linear Constraint Optimization Problem
Venue: arXiv cs.NE 2014
Year: 2014

This paper analyses a $(1,λ)$-Evolution Strategy, a randomised comparison-based adaptive search algorithm, on a simple constraint optimisation problem. The algorithm uses resampling to handle the constraint and optimizes a linear function with a linear constraint. Two cases are investigated: first the case where the step-size is constant, and second the case where the step-size is adapted using path length control. We exhibit for each case a Markov chain whose stability analysis would allow us to deduce the divergence of the algorithm depending on its internal parameters. We show divergence at a constant rate when the step-size is constant. We sketch that with step-size adaptation geometric divergence takes place. Our results complement previous studies where stability was assumed.
Labelled OSPA metric for fixed and known number of targets
Venue: arXiv cs.SY 2014
Year: 2014

The evaluation of multiple target tracking algorithms with labelled sets can be done using the labelled optimal subpattern assignment (LOSPA) metric. In this paper, we provide the expression of the same metric for fixed and known number of targets when vector notation is used.
The Possibility Problem for Probabilistic XML (Extended Version)
Venue: arXiv cs.DB 2014
Year: 2014

We consider the possibility problem of determining if a document is a possible world of a probabilistic document, in the setting of probabilistic XML. This basic question is a special case of query answering or tree automata evaluation, but it has specific practical uses, such as checking whether an user-provided probabilistic document outcome is possible or sufficiently likely. In this paper, we study the complexity of the possibility problem for probabilistic XML models of varying expressiveness. We show that the decision problem is often tractable in the absence of long-distance dependencies, but that its computation variant is intractable on unordered documents. We also introduce an explicit matches variant to generalize practical situations where node labels are unambiguous; this ensures tractability of the possibility problem, even under long-distance dependencies, provided event conjunctions are disallowed. Our results entirely classify the tractability boundary over all considered problem variants.
Energy-Efficient Power Adaptation for Cognitive Radio Systems under Imperfect Channel Sensing
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, energy efficient power adaptation is considered in sensing-based spectrum sharing cognitive radio systems in which secondary users first perform channel sensing and then initiate data transmission with two power levels based on the sensing decisions (e.g., idle or busy). It is assumed that spectrum sensing is performed by the cognitive secondary users, albeit with possible errors. In this setting, the optimization problem of maximizing the energy efficiency (EE) subject to peak/average transmission power constraints and average interference constraints is considered. The circuit power is taken into account for total power consumption. By exploiting the quasiconcave property of the EE maximization problem, the original problem is transformed into an equivalent parameterized concave problem and Dinkelbach's method-based iterative power adaptation algorithm is proposed. The impact of sensing performance, peak/average transmit power constraints and average interference constraint on the energy efficiency of cognitive radio systems is analyzed.
Automatic Repair of Buggy If Conditions and Missing Preconditions with SMT
Venue: arXiv cs.SE 2014
Year: 2014

We present Nopol, an approach for automatically repairing buggy if conditions and missing preconditions. As input, it takes a program and a test suite which contains passing test cases modeling the expected behavior of the program and at least one failing test case embodying the bug to be repaired. It consists of collecting data from multiple instrumented test suite executions, transforming this data into a Satisfiability Modulo Theory (SMT) problem, and translating the SMT result -- if there exists one -- into a source code patch. Nopol repairs object oriented code and allows the patches to contain nullness checks as well as specific method calls.