OpenRaiser/Intern-Atlas huggingface dataset:
Propositional Reasoning about Safety and Termination of Heap-Manipulating Programs
Venue: arXiv cs.LO 2014
Year: 2014

This paper shows that it is possible to reason about the safety and termination of programs handling potentially cyclic, singly-linked lists using propositional reasoning even when the safety invariants and termination arguments depend on constraints over the lengths of lists. For this purpose, we propose the theory SLH of singly-linked lists with length, which is able to capture non-trivial interactions between shape and arithmetic. When using the theory of bit-vector arithmetic as a background, SLH is efficiently decidable via a reduction to SAT. We show the utility of SLH for software verification by using it to express safety invariants and termination arguments for programs manipulating potentially cyclic, singly-linked lists with unrestricted, unspecified sharing. We also provide an implementation of the decision procedure and use it to check safety and termination proofs for several heap-manipulating programs.
Attenuating the Impact of Integrity Attacks on Real-Time Pricing in Smart Grids
Venue: arXiv cs.SY 2014
Year: 2014

The vulnerability of false data injection attacks on real-time electricity pricing for the power grid market has been recently explored. Previous work has focused on the impact caused by attackers that compromise pricing signals and send false prices to a subset of consumers. In this paper we extend previous work by considering a more powerful and general adversary model, a new analysis method based on sensitivity functions, and by proposing several countermeasures that can mitigate the negative impact of these attacks. Countermeasures include adding a low-pass filter to the pricing signals, selecting the time interval between price updates, selecting parameters of the controller, designing robust control algorithms, and by detecting anomalies in the behavior of the system.
Dynamic Cluster Head Node Election (DCHNE) Model over Wireless Sensor Networks (WSNs)
Venue: arXiv cs.NI 2014
Year: 2014

WSNs are becoming an appealing research area due to their several application domains. The performance of WSNs depends on the topology of sensors and their ability to adapt to changes in the network. Sensor nodes are often resource constrained by their limited power, less communication distance capacity, and restricted sensing capability. Therefore, they need to cooperate with each other to accomplish a specific task. Thus, clustering enables sensor nodes to communicate through the cluster head node for continuous communication process. In this paper, we introduce a dynamic cluster head election mechanism. Each node in the cluster calculates its residual energy value to determine its candidacy to become the Cluster Head Node (CHN). With this mechanism, each sensor node compares its residual energy level to other nodes in the same cluster. Depending on the residual energy level the sensor node acts as the next cluster head. Evaluation of the dynamic CHN election mechanism is conducted using network simulator-2 (ns2). The simulation results demonstrate that the proposed approach prolongs the network lifetime and balancing the energy
Sparsity Methods for Networked Control
Venue: arXiv cs.SY 2014
Year: 2014

In this presentation, we introduce sparsity methods for networked control systems and show the effectiveness of sparse control. In networked control, efficient data transmission is important since transmission delay and error can critically deteriorate the stability and performance. We will show that this problem is solved by sparse control designed by recent sparse optimization methods.
Linguistic Analysis of Toxic Behavior in an Online Video Game
Venue: arXiv cs.SI 2014
Year: 2014

In this paper we explore the linguistic components of toxic behavior by using crowdsourced data from over 590 thousand cases of accused toxic players in a popular match-based competition game, League of Legends. We perform a series of linguistic analyses to gain a deeper understanding of the role communication plays in the expression of toxic behavior. We characterize linguistic behavior of toxic players and compare it with that of typical players in an online competition game. We also find empirical support describing how a player transitions from typical to toxic behavior. Our findings can be helpful to automatically detect and warn players who may become toxic and thus insulate potential victims from toxic playing in advance.
Spatially correlated channel estimation based on block iterative support detection for large-scale MIMO
Venue: arXiv cs.IT 2014
Year: 2014

Downlink channel estimation with low pilot overhead is an important and challenging problem in large-scale MIMO systems due to the substantially increased MIMO channel dimension. In this letter, we propose a block iterative support detection (block-ISD) based algorithm for downlink channel estimation to reduce the pilot overhead, which is achieved by fully exploiting the block sparsity inherent in the block-sparse equivalent channel derived from the spatial correlations of MIMO channels. Furthermore, unlike conventional compressive sensing (CS) algorithms that rely on prior knowledge of the sparsity level, block-ISD relaxes this demanding requirement and is thus more practically appealing. Simulation results demonstrate that block-ISD yields better normalized mean square error (NMSE) performance than classical CS algorithms, and achieve a reduction of 84% pilot overhead than conventional channel estimation techniques.
On the Influence of Graph Density on Randomized Gossiping
Venue: arXiv cs.DS 2014
Year: 2014

Information dissemination is a fundamental problem in parallel and distributed computing. In its simplest variant, the broadcasting problem, a message has to be spread among all nodes of a graph. A prominent communication protocol for this problem is based on the random phone call model (Karp et al., FOCS 2000). In each step, every node opens a communication channel to a randomly chosen neighbor for bi-directional communication. Motivated by replicated databases and peer-to-peer networks, Berenbrink et al., ICALP 2010, considered the gossiping problem in the random phone call model. There, each node starts with its own message and all messages have to be disseminated to all nodes in the network. They showed that any $O(\log n)$-time algorithm in complete graphs requires $Ω(\log n)$ message transmissions per node to complete gossiping, w.h.p, while for broadcasting the average number of transmissions per node is $O(\log\log n)$. It is known that the $O(n\log\log n)$ bound on the number of transmissions required for randomized broadcasting in complete graphs cannot be achieved in sparse graphs even if they have best expansion and connectivity properties. In this paper, we analyze whether a similar influence of the graph density also holds w.r.t. the performance of gossiping. We study analytically and empirically the communication overhead generated by randomized gossiping in random graphs and consider simple modifications of the random phone call model in these graphs. Our results indicate that, unlike in broadcasting, there is no significant difference between the performance of randomized gossiping in complete graphs and sparse random graphs. Furthermore, our simulations indicate that by tuning the parameters of our algorithms, we can significantly reduce the communication overhead compared to the traditional push-pull approach in the graphs we consider.
Scalable Parallel Factorizations of SDD Matrices and Efficient Sampling for Gaussian Graphical Models
Venue: arXiv cs.DS 2014
Year: 2014

Motivated by a sampling problem basic to computational statistical inference, we develop a nearly optimal algorithm for a fundamental problem in spectral graph theory and numerical analysis. Given an $n\times n$ SDDM matrix ${\bf \mathbf{M}}$, and a constant $-1 \leq p \leq 1$, our algorithm gives efficient access to a sparse $n\times n$ linear operator $\tilde{\mathbf{C}}$ such that $${\mathbf{M}}^{p} \approx \tilde{\mathbf{C}} \tilde{\mathbf{C}}^\top.$$ The solution is based on factoring ${\bf \mathbf{M}}$ into a product of simple and sparse matrices using squaring and spectral sparsification. For ${\mathbf{M}}$ with $m$ non-zero entries, our algorithm takes work nearly-linear in $m$, and polylogarithmic depth on a parallel machine with $m$ processors. This gives the first sampling algorithm that only requires nearly linear work and $n$ i.i.d. random univariate Gaussian samples to generate i.i.d. random samples for $n$-dimensional Gaussian random fields with SDDM precision matrices. For sampling this natural subclass of Gaussian random fields, it is optimal in the randomness and nearly optimal in the work and parallel complexity. In addition, our sampling algorithm can be directly extended to Gaussian random fields with SDD precision matrices.
Location Verification Systems Under Spatially Correlated Shadowing
Venue: arXiv cs.IT 2014
Year: 2014

The verification of the location information utilized in wireless communication networks is a subject of growing importance. In this work we formally analyze, for the first time, the performance of a wireless Location Verification System (LVS) under the realistic setting of spatially correlated shadowing. Our analysis illustrates that anticipated levels of correlated shadowing can lead to a dramatic performance improvement of a Received Signal Strength (RSS)-based LVS. We also analyze the performance of an LVS that utilizes Differential Received Signal Strength (DRSS), formally proving the rather counter-intuitive result that a DRSS-based LVS has identical performance to that of an RSS-based LVS, for all levels of correlated shadowing. Even more surprisingly, the identical performance of RSS and DRSS-based LVSs is found to hold even when the adversary does not optimize his true location. Only in the case where the adversary does not optimize all variables under her control, do we find the performance of an RSS-based LVS to be better than a DRSS-based LVS. The results reported here are important for a wide range of emerging wireless communication applications whose proper functioning depends on the authenticity of the location information reported by a transceiver.
Blind Adaptive MIMO Receivers for CDMA Systems with Space-Time Block-Codes and Low-Cost Algorithms
Venue: arXiv cs.IT 2014
Year: 2014

In this paper we present low-complexity blind multi-input multi-output (MIMO) adaptive linear multiuser receivers for direct sequence code division multiple access (DS-CDMA) systems using multiple transmit antennas and space-time block codes (STBC) in multipath channels. A space-time code-constrained constant modulus (CCM) design criterion based on constrained optimization techniques and low-complexity stochastic gradient (SG) adaptive algorithms are developed for estimating the parameters of the space-time linear receivers. The receivers are designed by exploiting the unique structure imposed by both spreading codes and STBC. A blind space-time channel estimation scheme for STBC systems based on a subspace approach is also proposed along with an efficient SG algorithm. Simulation results for a downlink scenario assess the receiver structures and algorithms and show that the proposed schemes achieve excellent performance, outperforming existing methods.
Analysis and Design of Multi-Hop Diffusion-Based Molecular Communication Networks
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we consider a multi-hop molecular communication network consisting of one nanotransmitter, one nanoreceiver, and multiple nanotransceivers acting as relays. We consider three different relaying schemes to improve the range of diffusion-based molecular communication. In the first scheme, different types of messenger molecules are utilized in each hop of the multi-hop network. In the second and third scheme, we assume that two types of molecules and one type of molecule are utilized in the network, respectively. We identify self-interference, backward intersymbol interference (backward-ISI), and forward-ISI as the performance-limiting effects for the second and third relaying schemes. Furthermore, we consider two relaying modes analogous to those used in wireless communication systems, namely full-duplex and half-duplex relaying. We propose the adaptation of the decision threshold as an effective mechanism to mitigate self-interference and backward-ISI at the relay for full-duplex and half-duplex transmission. We derive closed-form expressions for the expected end-to-end error probability of the network for the three considered relaying schemes. Furthermore, we derive closed-form expressions for the optimal number of molecules released by the nanotransmitter and the optimal detection threshold of the nanoreceiver for minimization of the expected error probability of each hop.
Z2-double cyclic codes
Venue: arXiv cs.IT 2014
Year: 2014

A binary linear code $C$ is a $\mathbb{Z}_2$-double cyclic code if the set of coordinates can be partitioned into two subsets such that any cyclic shift of the coordinates of both subsets leaves invariant the code. These codes can be identified as submodules of the $\mathbb{Z}_2[x]$-module $\mathbb{Z}_2[x]/(x^r-1)\times\mathbb{Z}_2[x]/(x^s-1).$ We determine the structure of $\mathbb{Z}_2$-double cyclic codes giving the generator polynomials of these codes. The related polynomial representation of $\mathbb{Z}_2$-double cyclic codes and its duals, and the relations between the polynomial generators of these codes are studied.
DAPriv: Decentralized architecture for preserving the privacy of medical data
Venue: arXiv cs.CR 2014
Year: 2014

The digitization of the medical data has been a sensitive topic. In modern times laws such as the HIPAA provide some guidelines for electronic transactions in medical data to prevent attacks and fraudulent usage of private information. In our paper, we explore an architecture that uses hybrid computing with decentralized key management and show how it is suitable in preventing a special form of re-identification attack that we name as the re-assembly attack. This architecture would be able to use current infrastructure from mobile phones to server certificates and cloud based decentralized storage models in an efficient way to provide a reliable model for communication of medical data. We encompass entities including patients, doctors, insurance agents, emergency contacts, researchers, medical test laboratories and technicians. This is a complete architecture that provides patients with a good level of privacy, secure communication and more direct control.
A Computer Virus Propagation Model Using Delay Differential Equations With Probabilistic Contagion And Immunity
Venue: arXiv cs.SI 2014
Year: 2014

The SIR model is used extensively in the field of epidemiology, in particular, for the analysis of communal diseases. One problem with SIR and other existing models is that they are tailored to random or Erdos type networks since they do not consider the varying probabilities of infection or immunity per node. In this paper, we present the application and the simulation results of the pSEIRS model that takes into account the probabilities, and is thus suitable for more realistic scale free networks. In the pSEIRS model, the death rate and the excess death rate are constant for infective nodes. Latent and immune periods are assumed to be constant and the infection rate is assumed to be proportional to I (t) N(t), where N (t) is the size of the total population and I(t) is the size of the infected population. A node recovers from an infection temporarily with a probability p and dies from the infection with probability (1-p).
Closed-form Output Statistics of MIMO Block-Fading Channels
Venue: arXiv cs.IT 2014
Year: 2014

The information that can be transmitted through a wireless channel, with multiple-antenna equipped transmitter and receiver, is crucially influenced by the channel behavior as well as by the structure of the input signal. We characterize in closed form the probability density function (pdf) of the output of MIMO block-fading channels, for an arbitrary SNR value. Our results provide compact expressions for such output statistics, paving the way to a more detailed analytical information-theoretic exploration of communications in presence of block fading. The analysis is carried out assuming two different structures for the input signal: the i.i.d. Gaussian distribution and a product form that has been proved to be optimal for non-coherent communication, i.e., in absence of any channel state information. When the channel is fed by an i.i.d. Gaussian input, we assume the Gramian of the channel matrix to be unitarily invariant and derive the output statistics in both the noise-limited and the interference-limited scenario, considering different fading distributions. When the product-form input is adopted, we provide the expressions of the output pdf as the relationship between the overall number of antennas and the fading coherence length varies. We also highlight the relation between our newly derived expressions and the results already available in the literature, and, for some cases, we numerically compute the mutual information, based on the proposed expression of the output statistics.
Testing Security Policies for Distributed Systems: Vehicular Networks as a Case Study
Venue: arXiv cs.CR 2014
Year: 2014

Due to the increasing complexity of distributed systems, security testing is becoming increasingly critical in insuring reliability of such systems in relation to their security requirements. . To challenge this issue, we rely in this paper1 on model based active testing. In this paper we propose a framework to specify security policies and test their implementation. Our framework makes it possible to automatically generate test sequences, in order to validate the conformance of a security policy. This framework contains several new methods to ease the test case generation. To demonstrate the reliability of our framework, we present a Vehicular Networks System as an ongoing case study.
Mean-Field Networks
Venue: arXiv cs.LG 2014
Year: 2014

The mean field algorithm is a widely used approximate inference algorithm for graphical models whose exact inference is intractable. In each iteration of mean field, the approximate marginals for each variable are updated by getting information from the neighbors. This process can be equivalently converted into a feedforward network, with each layer representing one iteration of mean field and with tied weights on all layers. This conversion enables a few natural extensions, e.g. untying the weights in the network. In this paper, we study these mean field networks (MFNs), and use them as inference tools as well as discriminative models. Preliminary experiment results show that MFNs can learn to do inference very efficiently and perform significantly better than mean field as discriminative models.
The Relative Succinctness and Expressiveness of Modal Logics Can Be Arbitrarily Complex
Venue: arXiv cs.LO 2014
Year: 2014

We study the relative succinctness and expressiveness of modal logics, and prove that these relationships can be as complex as any countable partial order. For this, we use two uniform formalisms to define modal operators, and obtain results on succinctness and expressiveness in these two settings. Our proofs are based on formula size games introduced by Adler and Immerman and bisimulations.
Cosine Similarity Measure According to a Convex Cost Function
Venue: arXiv cs.LG 2014
Year: 2014

In this paper, we describe a new vector similarity measure associated with a convex cost function. Given two vectors, we determine the surface normals of the convex function at the vectors. The angle between the two surface normals is the similarity measure. Convex cost function can be the negative entropy function, total variation (TV) function and filtered variation function. The convex cost function need not be differentiable everywhere. In general, we need to compute the gradient of the cost function to compute the surface normals. If the gradient does not exist at a given vector, it is possible to use the subgradients and the normal producing the smallest angle between the two vectors is used to compute the similarity measure.
The Lovelace 2.0 Test of Artificial Creativity and Intelligence
Venue: arXiv cs.AI 2014
Year: 2014

Observing that the creation of certain types of artistic artifacts necessitate intelligence, we present the Lovelace 2.0 Test of creativity as an alternative to the Turing Test as a means of determining whether an agent is intelligent. The Lovelace 2.0 Test builds off prior tests of creativity and additionally provides a means of directly comparing the relative intelligence of different agents.
The Probabilistic Structure of Discrete Agent-Based Models
Venue: arXiv cs.MA 2014
Year: 2014

This paper describes a formalization of agent-based models (ABMs) as random walks on regular graphs and relates the symmetry group of those graphs to a coarse-graining of the ABM that is still Markovian. An ABM in which $N$ agents can be in $δ$ different states leads to a Markov chain with $δ^N$ states. In ABMs with a sequential update scheme by which one agent is chosen to update its state at a time, transitions are only allowed between system configurations that differ with respect to a single agent. This characterizes ABMs as random walks on regular graphs. The non-trivial automorphisms of those graphs make visible the dynamical symmetries that an ABM gives rise to because sets of micro configurations can be interchanged without changing the probability structure of the random walk. This allows for a systematic loss-less reduction of the state space of the model.
Application of reactive transport modelling to growth and transport of microorganisms in the capillary fringe
Venue: arXiv cs.CE 2014
Year: 2014

A multicomponent multiphase reactive transport simulator has been developed to facilitate the investigation of a large variety of phenomena in porous media including component transport, diffusion, microbiological growth and decay, cell attachment and detachment and phase exchange. The coupled problem is solved using operator splitting. This approach allows a flexible adaptation of the solution strategy to the concrete problem. Moreover, the individual submodels were optimised to be able to describe behaviour of Escherichia coli (HB101 K12 pGLO) in the capillary fringe in the presence or absence of dissolved organic carbon and oxygen under steady-state and flow conditions. Steady-state and flow through experiments in a Hele-Shaw cell, filled with quartz sand, were conducted to study eutrophic bacterial growth and transport in both saturated and unsaturated porous media. As E. coli cells can form the green fluorescent protein (GFP), the cell densities, calculated by evaluation of measured fluorescence intensities (in situ detection) were compared with the cell densities computed by numerical simulation. The comparison showed the laboratory experiments can be well described by our mathematical model.
Justifying and Improving Meta-Agent Conflict-Based Search
Venue: arXiv cs.AI 2014
Year: 2014

The Meta-Agent Conflict-Based Search~(MA-CBS) is a recently proposed algorithm for the multi-agent path finding problem. The algorithm is an extension of Conflict-Based Search~(CBS), which automatically merges conflicting agents into meta-agents if the number of conflicts exceeds a certain threshold. However, the decision to merge agents is made according to an empirically chosen fixed threshold on the number of conflicts. The best threshold depends both on the domain and on the number of agents, and the nature of the dependence is not clearly understood. We suggest a justification for the use of a fixed threshold on the number of conflicts based on the analysis of a model problem. Following the suggested justification, we introduce new decision policies for the MA-CBS algorithm, which considerably improve the algorithm's performance. The improved variants of the algorithm are evaluated on several sets of problems, chosen to underline different aspects of the algorithms.