OpenRaiser/Intern-Atlas huggingface dataset:
Asymptotic Properties of One-Bit Distributed Detection with Ordered Transmissions
Venue: arXiv cs.IT 2011
Year: 2011

Consider a sensor network made of remote nodes connected to a common fusion center. In a recent work Blum and Sadler [1] propose the idea of ordered transmissions -sensors with more informative samples deliver their messages first- and prove that optimal detection performance can be achieved using only a subset of the total messages. Taking to one extreme this approach, we show that just a single delivering allows making the detection errors as small as desired, for a sufficiently large network size: a one-bit detection scheme can be asymptotically consistent. The transmission ordering is based on the modulus of some local statistic (MO system). We derive analytical results proving the asymptotic consistency and, for the particular case that the local statistic is the log-likelihood (\ell-MO system), we also obtain a bound on the error convergence rate. All the theorems are proved under the general setup of random number of sensors. Computer experiments corroborate the analysis and address typical examples of applications including: non-homogeneous Poisson-deployed networks, detection by per-sensor censoring, monitoring of energy-constrained phenomenon.
A New Secret key Agreement Scheme in a Four-Terminal Network
Venue: arXiv cs.CR 2011
Year: 2011

A new scenario for generating a secret key and two private keys among three Terminals in the presence of an external eavesdropper is considered. Terminals 1, 2 and 3 intend to share a common secret key concealed from the external eavesdropper (Terminal 4) and simultaneously, each of Terminals 1 and 2 intends to share a private key with Terminal 3 while keeping it concealed from each other and from Terminal 4. All four Terminals observe i.i.d. outputs of correlated sources and there is a public channel from Terminal 3 to Terminals 1 and 2. An inner bound of the "secret key-private keys capacity region" is derived and the single letter capacity regions are obtained for some special cases.
On primary and secondary repetitions in words
Venue: arXiv cs.FL 2011
Year: 2011

Combinatorial properties of maximal repetitions (runs) in formal words are studied. We classify all maximal repetitions in a word as primary and secondary where the set of all primary repetitions determines all the other repetitons in the word. Essential combinatorial properties of primary repetitions are established.
Political protest Italian-style: The dissonance between the blogosphere and mainstream media in the promotion and coverage of Beppe Grillo's V-day
Venue: arXiv cs.SI 2011
Year: 2011

We analyze the organization, promotion and public perception of V-day, a political rally that took place on September 8, 2007, to protest against corruption in the Italian Parliament. Launched by blogger Beppe Grillo, and promoted via a word of mouth mobilization on the Italian blogosphere, V-day brought close to one million Italians in the streets on a single day, but was mostly ignored by mainstream media. This article is divided into two parts. In the first part, we analyze the volume and content of online articles published by both bloggers and mainstream news sources from June 14 (the day V-day was announced) until September 15, 2007 (one week after it took place) . We find that the success of V-day can be attributed to the coverage of bloggers and small-scale local news outlets only, suggesting a strong grassroots component in the organization of the rally. We also find a dissonant thematic relationship between content published by blogs and mainstream media: while the majority of blogs analyzed promote V-day, major mainstream media sources critique the methods of information production and dissemination employed by Grillo. Based on this finding, in the second part of the study, we explore the role of Grillo in the organization of the rally from a network analysis perspective. We study the interlinking structure of the V-day blogosphere network, to determine its structure, its levels of heterogeneity, and resilience. Our analysis contradicts the hypothesis that Grillo served as a top-down, broadcast-like source of information. Rather, we find that information about V-day was transferred across heterogeneous nodes in a moderately robust and resilient core network of blogs. We speculate that the organization of V-day represents the very first case, in Italian history, of a political demonstration developed and promoted primarily via the use of social media on the web.
Shannon Entropy based Randomness Measurement and Test for Image Encryption
Venue: arXiv cs.CR 2011
Year: 2011

The quality of image encryption is commonly measured by the Shannon entropy over the ciphertext image. However, this measurement does not consider to the randomness of local image blocks and is inappropriate for scrambling based image encryption methods. In this paper, a new information entropy-based randomness measurement for image encryption is introduced which, for the first time, answers the question of whether a given ciphertext image is sufficiently random-like. It measures the randomness over the ciphertext in a fairer way by calculating the averaged entropy of a series of small image blocks within the entire test image. In order to fulfill both quantitative and qualitative measurement, the expectation and the variance of this averaged block entropy for a true-random image are strictly derived and corresponding numerical reference tables are also provided. Moreover, a hypothesis test at significance-level is given to help accept or reject the hypothesis that the test image is ideally encrypted/random-like. Simulation results show that the proposed test is able to give both effectively quantitative and qualitative results for image encryption. The same idea can also be applied to measure other digital data, like audio and video.
A Comparison of Link Layer Attacks on Wireless Sensor Networks
Venue: arXiv cs.CR 2011
Year: 2011

Wireless sensor networks (WSNs) have many potential applications [1, 5] and unique challenges. They usually consist of hundreds or thousands small sensor nodes such as MICA2, which operate autonomously; conditions such as cost, invisible deployment and many application domains, lead to small size and limited resources sensors [2]. WSNs are susceptible to many types of link layer attacks [1] and most of traditional networks security techniques are unusable on WSNs [2]; due to wireless and shared nature of communication channel, untrusted transmissions, deployment in open environments, unattended nature and limited resources [1]. So, security is a vital requirement for these networks; but we have to design a proper security mechanism that attends to WSN's constraints and requirements. In this paper, we focus on security of WSNs, divide it (the WSNs security) into four categories and will consider them, include: an overview of WSNs, security in WSNs, the threat model on WSNs, a wide variety of WSNs' link layer attacks and a comparison of them. This work enables us to identify the purpose and capabilities of the attackers; also, the goal and effects of the link layer attacks on WSNs are introduced. Also, this paper discusses known approaches of security detection and defensive mechanisms against the link layer attacks; this would enable it security managers to manage the link layer attacks of WSNs more effectively.
Recoverable Values for Independent Sets
Venue: arXiv cs.DS 2011
Year: 2011

The notion of {\em recoverable value} was advocated in work of Feige, Immorlica, Mirrokni and Nazerzadeh [Approx 2009] as a measure of quality for approximation algorithms. There this concept was applied to facility location problems. In the current work we apply a similar framework to the maximum independent set problem (MIS). We say that an approximation algorithm has {\em recoverable value} $ρ$, if for every graph it recovers an independent set of size at least $\max_I \sum_{v\in I} \min[1,ρ/(d(v) + 1)]$, where $d(v)$ is the degree of vertex $v$, and $I$ ranges over all independent sets in $G$. Hence, in a sense, from every vertex $v$ in the maximum independent set the algorithm recovers a value of at least $ρ/(d_v + 1)$ towards the solution. This quality measure is most effective in graphs in which the maximum independent set is composed of low degree vertices. It easily follows from known results that some simple algorithms for MIS ensure $ρ\ge 1$. We design a new randomized algorithm for MIS that ensures an expected recoverable value of at least $ρ\ge 7/3$. In addition, we show that approximating MIS in graphs with a given $k$-coloring within a ratio larger than $2/k$ is unique games hard. This rules out a natural approach for obtaining $ρ\ge 2$.
To Parallelize or Not to Parallelize, Speed Up Issue
Venue: arXiv cs.SE 2011
Year: 2011

Running parallel applications requires special and expensive processing resources to obtain the required results within a reasonable time. Before parallelizing serial applications, some analysis is recommended to be carried out to decide whether it will benefit from parallelization or not. In this paper we discuss the issue of speed up gained from parallelization using Message Passing Interface (MPI) to compromise between the overhead of parallelization cost and the gained parallel speed up. We also propose an experimental method to predict the speed up of MPI applications.
Partially Linear Estimation with Application to Sparse Signal Recovery From Measurement Pairs
Venue: arXiv cs.IT 2011
Year: 2011

We address the problem of estimating a random vector X from two sets of measurements Y and Z, such that the estimator is linear in Y. We show that the partially linear minimum mean squared error (PLMMSE) estimator does not require knowing the joint distribution of X and Y in full, but rather only its second-order moments. This renders it of potential interest in various applications. We further show that the PLMMSE method is minimax-optimal among all estimators that solely depend on the second-order statistics of X and Y. We demonstrate our approach in the context of recovering a signal, which is sparse in a unitary dictionary, from noisy observations of it and of a filtered version of it. We show that in this setting PLMMSE estimation has a clear computational advantage, while its performance is comparable to state-of-the-art algorithms. We apply our approach both in static and dynamic estimation applications. In the former category, we treat the problem of image enhancement from blurred/noisy image pairs, where we show that PLMMSE estimation performs only slightly worse than state-of-the art algorithms, while running an order of magnitude faster. In the dynamic setting, we provide a recursive implementation of the estimator and demonstrate its utility in the context of tracking maneuvering targets from position and acceleration measurements.
Converging an Overlay Network to a Gradient Topology
Venue: arXiv cs.SY 2011
Year: 2011

In this paper, we investigate the topology convergence problem for the gossip-based Gradient overlay network. In an overlay network where each node has a local utility value, a Gradient overlay network is characterized by the properties that each node has a set of neighbors with the same utility value (a similar view) and a set of neighbors containing higher utility values (gradient neighbor set), such that paths of increasing utilities emerge in the network topology. The Gradient overlay network is built using gossiping and a preference function that samples from nodes using a uniform random peer sampling service. We analyze it using tools from matrix analysis, and we prove both the necessary and sufficient conditions for convergence to a complete gradient structure, as well as estimating the convergence time and providing bounds on worst-case convergence time. Finally, we show in simulations the potential of the Gradient overlay, by building a more efficient live-streaming peer-to-peer (P2P) system than one built using uniform random peer sampling.
Planning to Be Surprised: Optimal Bayesian Exploration in Dynamic Environments
Venue: arXiv cs.AI 2011
Year: 2011

To maximize its success, an AGI typically needs to explore its initially unknown world. Is there an optimal way of doing so? Here we derive an affirmative answer for a broad class of environments.
Finding the Minimal DFA of Very Large Finite State Automata with an Application to Token Passing Networks
Venue: arXiv cs.DC 2011
Year: 2011

Finite state automata (FSA) are ubiquitous in computer science. Two of the most important algorithms for FSA processing are the conversion of a non-deterministic finite automaton (NFA) to a deterministic finite automaton (DFA), and then the production of the unique minimal DFA for the original NFA. We exhibit a parallel disk-based algorithm that uses a cluster of 29 commodity computers to produce an intermediate DFA with almost two billion states and then continues by producing the corresponding unique minimal DFA with less than 800,000 states. The largest previous such computation in the literature was carried out on a 512-processor CM-5 supercomputer in 1996. That computation produced an intermediate DFA with 525,000 states and an unreported number of states for the corresponding minimal DFA. The work is used to provide strong experimental evidence satisfying a conjecture on a series of token passing networks. The conjecture concerns stack sortable permutations for a finite stack and a 3-buffer. The origins of this problem lie in the work on restricted permutations begun by Knuth and Tarjan in the late 1960s. The parallel disk-based computation is also compared with both a single-threaded and multi-threaded RAM-based implementation using a 16-core 128 GB large shared memory computer.
Interference Alignment: A one-sided approach
Venue: arXiv cs.IT 2011
Year: 2011

Interference Alignment (IA) is the process of designing signals in such a way that they cast overlapping shadows at their unintended receivers, while remaining distinguishable at the intended ones. Our goal in this paper is to come up with an algorithm for IA that runs at the transmitters only (and is transparent to the receivers), that doesn't require channel reciprocity, and that alleviates the need to alternate between the forward and reverse network as is the case in Distributed IA (Gomadam, Cadambe, Jafar 08'), thereby inducing significant overhead in certain environments where the channel changes frequently. Most importantly, our effort is focused on ensuring that this one-sided approach does not degrade the performance of the system w.r.t. Distributed IA (since it cannot improve it). As a first step, we model the interference in each receiver's desired signal as a function of the transmitters' beamforming vectors. We then propose a simple steepest descent (SD) algorithm and use it to minimize the interference in each receiver's desired signal space. We mathematically establish equivalences between our approach and the Distributed IA algorithm (Gomadam, Cadambe, Jafar 08') and show that our algorithm also converges to an alignment solution (when the solution is feasible).
A Review of Interference Reduction in Wireless Networks Using Graph Coloring Methods
Venue: arXiv cs.NI 2011
Year: 2011

The interference imposes a significant negative impact on the performance of wireless networks. With the continuous deployment of larger and more sophisticated wireless networks, reducing interference in such networks is quickly being focused upon as a problem in today's world. In this paper we analyze the interference reduction problem from a graph theoretical viewpoint. A graph coloring methods are exploited to model the interference reduction problem. However, additional constraints to graph coloring scenarios that account for various networking conditions result in additional complexity to standard graph coloring. This paper reviews a variety of algorithmic solutions for specific network topologies.
DOLFIN: Automated Finite Element Computing
Venue: arXiv cs.MS 2011
Year: 2011

We describe here a library aimed at automating the solution of partial differential equations using the finite element method. By employing novel techniques for automated code generation, the library combines a high level of expressiveness with efficient computation. Finite element variational forms may be expressed in near mathematical notation, from which low-level code is automatically generated, compiled and seamlessly integrated with efficient implementations of computational meshes and high-performance linear algebra. Easy-to-use object-oriented interfaces to the library are provided in the form of a C++ library and a Python module. This paper discusses the mathematical abstractions and methods used in the design of the library and its implementation. A number of examples are presented to demonstrate the use of the library in application code.
Decentralized Online Learning Algorithms for Opportunistic Spectrum Access
Venue: arXiv cs.LG 2011
Year: 2011

The fundamental problem of multiple secondary users contending for opportunistic spectrum access over multiple channels in cognitive radio networks has been formulated recently as a decentralized multi-armed bandit (D-MAB) problem. In a D-MAB problem there are $M$ users and $N$ arms (channels) that each offer i.i.d. stochastic rewards with unknown means so long as they are accessed without collision. The goal is to design a decentralized online learning policy that incurs minimal regret, defined as the difference between the total expected rewards accumulated by a model-aware genie, and that obtained by all users applying the policy. We make two contributions in this paper. First, we consider the setting where the users have a prioritized ranking, such that it is desired for the $K$-th-ranked user to learn to access the arm offering the $K$-th highest mean reward. For this problem, we present the first distributed policy that yields regret that is uniformly logarithmic over time without requiring any prior assumption about the mean rewards. Second, we consider the case when a fair access policy is required, i.e., it is desired for all users to experience the same mean reward. For this problem, we present a distributed policy that yields order-optimal regret scaling with respect to the number of users and arms, better than previously proposed policies in the literature. Both of our distributed policies make use of an innovative modification of the well known UCB1 policy for the classic multi-armed bandit problem that allows a single user to learn how to play the arm that yields the $K$-th largest mean reward.
Towards an automated query modification assistant
Venue: arXiv cs.IR 2011
Year: 2011

Users who need several queries before finding what they need can benefit from an automatic search assistant that provides feedback on their query modification strategies. We present a method to learn from a search log which types of query modifications have and have not been effective in the past. The method analyses query modifications along two dimensions: a traditional term-based dimension and a semantic dimension, for which queries are enriches with linked data entities. Applying the method to the search logs of two search engines, we identify six opportunities for a query modification assistant to improve search: modification strategies that are commonly used, but that often do not lead to satisfactory results.
On Interference Alignment and the Deterministic Capacity for Cellular Channels with Weak Symmetric Cross Links
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we study the uplink of a cellular system using the linear deterministic approximation model, where there are two users transmitting to a receiver, mutually interfering with a third transmitter communicating with a second receiver. We give an achievable coding scheme and prove its optimality, i.e. characterize the capacity region. This scheme is a form of interference alignment which exploits the channel gain difference of the two-user cell.
Exact and Efficient Algorithm to Discover Extreme Stochastic Events in Wind Generation over Transmission Power Grids
Venue: arXiv cs.SY 2011
Year: 2011

In this manuscript we continue the thread of [M. Chertkov, F. Pan, M. Stepanov, Predicting Failures in Power Grids: The Case of Static Overloads, IEEE Smart Grid 2011] and suggest a new algorithm discovering most probable extreme stochastic events in static power grids associated with intermittent generation of wind turbines. The algorithm becomes EXACT and EFFICIENT (polynomial) in the case of the proportional (or other low parametric) control of standard generation, and log-concave probability distribution of the renewable generation, assumed known from the wind forecast. We illustrate the algorithm's ability to discover problematic extreme events on the example of the IEEE RTS-96 model of transmission with additions of 10%, 20% and 30% of renewable generation. We observe that the probability of failure may grow but it may also decrease with increase in renewable penetration, if the latter is sufficiently diversified and distributed.
Density Evolution Analysis of Node-Based Verification-Based Algorithms in Compressive Sensing
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we present a new approach for the analysis of iterative node-based verification-based (NB-VB) recovery algorithms in the context of compressive sensing. These algorithms are particularly interesting due to their low complexity (linear in the signal dimension $n$). The asymptotic analysis predicts the fraction of unverified signal elements at each iteration $\ell$ in the asymptotic regime where $n \rightarrow \infty$. The analysis is similar in nature to the well-known density evolution technique commonly used to analyze iterative decoding algorithms. To perform the analysis, a message-passing interpretation of NB-VB algorithms is provided. This interpretation lacks the extrinsic nature of standard message-passing algorithms to which density evolution is usually applied. This requires a number of non-trivial modifications in the analysis. The analysis tracks the average performance of the recovery algorithms over the ensembles of input signals and sensing matrices as a function of $\ell$. Concentration results are devised to demonstrate that the performance of the recovery algorithms applied to any choice of the input signal over any realization of the sensing matrix follows the deterministic results of the analysis closely. Simulation results are also provided which demonstrate that the proposed asymptotic analysis matches the performance of recovery algorithms for large but finite values of $n$. Compared to the existing technique for the analysis of NB-VB algorithms, which is based on numerically solving a large system of coupled differential equations, the proposed method is much simpler and more accurate.
High Speed Multiple Valued Logic Full Adder Using Carbon Nano Tube Field Effect Transistor
Venue: arXiv cs.AR 2011
Year: 2011

High speed Full-Adder (FA) module is a critical element in designing high performance arithmetic circuits. In this paper, we propose a new high speed multiple-valued logic FA module. The proposed FA is constructed by 14 transistors and 3 capacitors, using carbon nano-tube field effect transistor (CNFET) technology. Furthermore, our proposed technique has been examined in different voltages (i.e., 0.65v and 0.9v). The observed results reveal power consumption and power delay product (PDP) improvements compared to existing FA counterparts