OpenRaiser/Intern-Atlas huggingface dataset:
Fast and Accurate Frequency Estimation Using Sliding DFT
Venue: arXiv cs.SY 2012
Year: 2012

Frequency Estimation of a complex exponential is a problem relevant to a large number of fields. In this paper a computationally efficient and accurate frequency estimator is presented using the guaranteed stable Sliding DFT which gives stability as well as computational efficiency. The estimator approaches Jacobsen's estimator and Candan's estimator for large N with an extra correction term multiplied to it for the stabilization of the sliding DFT. Simulation results show that the performance of the proposed estimator were found to be better than Jacobsen's estimator and Candan's estimator.
Deterministic Leader Election Among Disoriented Anonymous Sensors
Venue: arXiv cs.DC 2012
Year: 2012

We address the Leader Election (LE) problem in networks of anonymous sensors sharing no kind of common coordinate system. Leader Election is a fundamental symmetry breaking problem in distributed computing. Its goal is to assign value 1 (leader) to one of the entities and value 0 (non-leader) to all others. In this paper, assuming n > 1 disoriented anonymous sensors, we provide a complete charac- terization on the sensors positions to deterministically elect a leader, provided that all the sensors' positions are known by every sensor. More precisely, our contribution is twofold: First, assuming n anonymous sensors agreeing on a common handedness (chirality) of their own coordinate system, we provide a complete characterization on the sensors positions to deterministically elect a leader. Second, we also provide such a complete chararacterization for sensors devoided of a common handedness. Both characterizations rely on a particular object from combinatorics on words, namely the Lyndon Words.
Computing Nash Equilibrium in Wireless Ad Hoc Networks: A Simulation-Based Approach
Venue: arXiv cs.GT 2012
Year: 2012

This paper studies the problem of computing Nash equilibrium in wireless networks modeled by Weighted Timed Automata. Such formalism comes together with a logic that can be used to describe complex features such as timed energy constraints. Our contribution is a method for solving this problem using Statistical Model Checking. The method has been implemented in UPPAAL model checker and has been applied to the analysis of Aloha CSMA/CD and IEEE 802.15.4 CSMA/CA protocols.
Rich Counter-Examples for Temporal-Epistemic Logic Model Checking
Venue: arXiv cs.LO 2012
Year: 2012

Model checking verifies that a model of a system satisfies a given property, and otherwise produces a counter-example explaining the violation. The verified properties are formally expressed in temporal logics. Some temporal logics, such as CTL, are branching: they allow to express facts about the whole computation tree of the model, rather than on each single linear computation. This branching aspect is even more critical when dealing with multi-modal logics, i.e. logics expressing facts about systems with several transition relations. A prominent example is CTLK, a logic that reasons about temporal and epistemic properties of multi-agent systems. In general, model checkers produce linear counter-examples for failed properties, composed of a single computation path of the model. But some branching properties are only poorly and partially explained by a linear counter-example. This paper proposes richer counter-example structures called tree-like annotated counter-examples (TLACEs), for properties in Action-Restricted CTL (ARCTL), an extension of CTL quantifying paths restricted in terms of actions labeling transitions of the model. These counter-examples have a branching structure that supports more complete description of property violations. Elements of these counter-examples are annotated with parts of the property to give a better understanding of their structure. Visualization and browsing of these richer counter-examples become a critical issue, as the number of branches and states can grow exponentially for deeply-nested properties. This paper formally defines the structure of TLACEs, characterizes adequate counter-examples w.r.t. models and failed properties, and gives a generation algorithm for ARCTL properties. It also illustrates the approach with examples in CTLK, using a reduction of CTLK to ARCTL. The proposed approach has been implemented, first by extending the NuSMV model checker to generate and export branching counter-examples, secondly by providing an interactive graphical interface to visualize and browse them.
Study Paper on Test Case generation for GUI Based Testing
Venue: arXiv cs.SE 2012
Year: 2012

With the advent of WWW and outburst in technology and software development, testing the software became a major concern. Due to the importance of the testing phase in a software development life cycle, testing has been divided into graphical user interface (GUI) based testing, logical testing, integration testing, etc.GUI Testing has become very important as it provides more sophisticated way to interact with the software. The complexity of testing GUI increased over time. The testing needs to be performed in a way that it provides effectiveness, efficiency, increased fault detection rate and good path coverage. To cover all use cases and to provide testing for all possible (success/failure) scenarios the length of the test sequence is considered important. Intent of this paper is to study some techniques used for test case generation and process for various GUI based software applications.
Unified model of voltage/current mode control to predict saddle-node bifurcation
Venue: arXiv cs.SY 2012
Year: 2012

A unified model of voltage mode control (VMC) and current mode control (CMC) is proposed to predict the saddle-node bifurcation (SNB). Exact SNB boundary conditions are derived, and can be further simplified in various forms for design purpose. Many approaches, including steady-state, sampled-data, average, harmonic balance, and loop gain analyses are applied to predict SNB. Each approach has its own merits and complement the other approaches.
Additive Entropies of Partitions
Venue: arXiv cs.IT 2012
Year: 2012

We provide, under minimal continuity assumptions, a description of \textsl{additive partition entropies}. They are real functions $I$ on the set of finite partitions that are additive on stochastically independent partitions in a given probability space.
Adaptive and Dynamic Wireless Routers with Smart Antenna for Power Management
Venue: arXiv cs.NI 2012
Year: 2012

In the recent evolution of wireless technologies, the power management has been a worrying factor. In order to overcome the power shortage, steps are taken to find new kind of energy harvesting methods, power attenuation reduction methods and power saving techniques. Wireless routers even though consume not much of power, battery powered devices require a lot. Omni directional antenna embedded with multiple antennae focusing the beam of radio wave signals in the direction of nodes with least transmission angle can be a solution for this problem which is called as "Smart Antenna". To reduce power maceration we are going for adaptive and dynamic transmission wherein the transmission angle of antennae is varied in accordance with the movement of nodes. Apart from saving the power considerably, it also improves the signal strength
A General Form of Attribute Exploration
Venue: arXiv cs.LO 2012
Year: 2012

We present a general form of attribute exploration, a knowledge completion algorithm from Formal Concept Analysis. The aim of our presentation is not only to extend the applicability of attribute exploration by a general description. It may also allow to view different existing variants of attribute exploration as instances of a general form, which may simplify theoretical considerations.
Automatic Deduction in Dynamic Geometry using Sage
Venue: arXiv cs.MS 2012
Year: 2012

We present a symbolic tool that provides robust algebraic methods to handle automatic deduction tasks for a dynamic geometry construction. The main prototype has been developed as two different worksheets for the open source computer algebra system Sage, corresponding to two different ways of coding a geometric construction. In one worksheet, diagrams constructed with the open source dynamic geometry system GeoGebra are accepted. In this worksheet, Groebner bases are used to either compute the equation of a geometric locus in the case of a locus construction or to determine the truth of a general geometric statement included in the GeoGebra construction as a boolean variable. In the second worksheet, locus constructions coded using the common file format for dynamic geometry developed by the Intergeo project are accepted for computation. The prototype and several examples are provided for testing. Moreover, a third Sage worksheet is presented in which a novel algorithm to eliminate extraneous parts in symbolically computed loci has been implemented. The algorithm, based on a recent work on the Groebner cover of parametric systems, identifies degenerate components and extraneous adherence points in loci, both natural byproducts of general polynomial algebraic methods. Detailed examples are discussed.
The GF Mathematics Library
Venue: arXiv cs.MS 2012
Year: 2012

This paper is devoted to present the Mathematics Grammar Library, a system for multilingual mathematical text processing. We explain the context in which it originated, its current design and functionality and the current development goals. We also present two prototype services and comment on possible future applications in the area of artificial mathematics assistants.
Improved Linear Precoding over Block Diagonalization in Multi-cell Cooperative Networks
Venue: arXiv cs.IT 2012
Year: 2012

In downlink multiuser multiple-input multiple-output (MIMO) systems, block diagonalization (BD) is a practical linear precoding scheme which achieves the same degrees of freedom (DoF) as the optimal linear/nonlinear precoding schemes. However, its sum-rate performance is rather poor in the practical SNR regime due to the transmit power boost problem. In this paper, we propose an improved linear precoding scheme over BD with a so-called "effective-SNR-enhancement" technique. The transmit covariance matrices are obtained by firstly solving a power minimization problem subject to the minimum rate constraint achieved by BD, and then properly scaling the solution to satisfy the power constraints. It is proved that such approach equivalently enhances the system SNR, and hence compensates the transmit power boost problem associated with BD. The power minimization problem is in general non-convex. We therefore propose an efficient algorithm that solves the problem heuristically. Simulation results show significant sum rate gains over the optimal BD and the existing minimum mean square error (MMSE) based precoding schemes.
Jam-X: Wireless Agreement under Interference
Venue: arXiv cs.NI 2012
Year: 2012

Wireless low-power transceivers used in sensor networks such as IEEE 802.15.4 typically operate in unlicensed frequency bands that are subject to external interference from devices transmitting at much higher power. Communication protocols should therefore be designed to be robust against such interference. A critical building block of many protocols at all layers is agreement on a piece of information among a set of nodes. At the MAC layer, nodes may need to agree on a new time slot or frequency channel; at the application layer nodes may need to agree on handing over a leader role from one node to another. Message loss caused by interference may break agreement in two different ways: none of the nodes use the new information (time slot, channel, leader) and stick with the previous assignment, or - even worse - some nodes use the new information and some do not. This may lead to reduced performance or failures. In this paper we investigate the problem of agreement under interference and point out the limitations of the traditional message-based n-way handshake approach. We propose novel protocols that use jamming instead of message transmissions and show that they outperform the n-way handshake in terms of agreement probability, energy consumption, and time-to-completion both in the unicast case (two neighboring nodes agree) as well as in the broadcast case (any number of neighboring nodes agree).
Multilevel Image Encryption
Venue: arXiv cs.CR 2012
Year: 2012

With the fast evolution of digital data exchange and increased usage of multi media images, it is essential to protect the confidential image data from unauthorized access. In natural images the values and position of the neighbouring pixels are strongly correlated. The method proposed in this paper, breaks this correlation increasing entropy of the position and entropy of pixel values using block shuffling and encryption by chaotic sequence respectively. The plain-image is initially row wise shuffled and first level of encryption is performed using addition modulo operation. The image is divided into blocks and then block based shuffling is performed using Arnold Cat transformation, further the blocks are uniformly scrambled across the image. Finally the shuffled image undergoes second level of encryption by bitwise XOR operation, and then the image as a whole is shuffled column wise to produce the ciphered image for transmission. The experimental results show that the proposed algorithm can successfully encrypt or decrypt the image with the secret keys, and the analysis of the algorithm also demonstrates that the encrypted image has good information entropy and low correlation coefficients.
Innovative SQA Service Maturity Model using CMMI and ITIL
Venue: arXiv cs.OH 2012
Year: 2012

This Journal details a maturity model for SQA services which has been developed during QMS implementation in the IT division of a large multinational organization. The scope of the engagement was to establish a standard set of processes based on CMMI\textregistered and ITIL\textregistered Framework across four business verticals scattered in Europe, United States and Asia. The services of Software Quality Analyst (SQA) from different vendors were leveraged to facilitate implementation of processes which was referred to as the Quality Management System (QMS). To co-ordinate and support QMS implementation, a Software Quality Assurance Group (SQAG) was established at the organizational level. Considering the large number of applications, the business verticals proposed that process implementation should be owned and managed by practitioners themselves so that the mass deployment of QMS can be achieved at a faster rate with the same SQA capacity. This called for a need to devise an innovative implementation solution before moving to a process implementation model which proposed Project Managers implementing processes themself. While there are process models and frameworks available in the market for establishing processes in an organization, there is no model that elaborates activities to be performed by the SQA for effective implementation of processes. SQA service maturity model was proposed as a solution based on CMMI\textregistered and developed to eventually proceed towards a 'Process Implementation Model proposing Project Managers implementing processes themself'. SQA Service Maturity Model is a Software Quality Assurance implementation framework that enables organisations to increase Efficiencies in Software Quality Assurance, reduce the Cost of Defects and ultimately Increasing Return on Investment in IT.
Lossy Source Coding via Spatially Coupled LDGM Ensembles
Venue: arXiv cs.IT 2012
Year: 2012

We study a new encoding scheme for lossy source compression based on spatially coupled low-density generator-matrix codes. We develop a belief-propagation guided-decimation algorithm, and show that this algorithm allows to approach the optimal distortion of spatially coupled ensembles. Moreover, using the survey propagation formalism, we also observe that the optimal distortions of the spatially coupled and individual code ensembles are the same. Since regular low-density generator-matrix codes are known to achieve the Shannon rate-distortion bound under optimal encoding as the degrees grow, our results suggest that spatial coupling can be used to reach the rate-distortion bound, under a {\it low complexity} belief-propagation guided-decimation algorithm. This problem is analogous to the MAX-XORSAT problem in computer science.
Two-way Interference Channels
Venue: arXiv cs.IT 2012
Year: 2012

We consider two-way interference channels (ICs) where forward and backward channels are ICs but not necessarily the same. We first consider a scenario where there are only two forward messages and feedback is offered through the backward IC for aiding forward-message transmission. For a linear deterministic model of this channel, we develop inner and outer bounds that match for a wide range of channel parameters. We find that the backward IC can be more efficiently used for feedback rather than if it were used for sending its own independent backward messages. As a consequence, we show that feedback can provide a net increase in capacity even if feedback cost is taken into consideration. Moreover we extend this to a more general scenario with two additional independent backward messages, from which we find that interaction can provide an arbitrarily large gain in capacity.
Efficient Algorithms for Solving Hypergraphic Steiner Tree Relaxations in Quasi-Bipartite Instances
Venue: arXiv cs.DM 2012
Year: 2012

We consider the Steiner tree problem in quasi-bipartite graphs, where no two Steiner vertices are connected by an edge. For this class of instances, we present an efficient algorithm to exactly solve the so called directed component relaxation (DCR), a specific form of hypergraphic LP relaxation that was instrumental in the recent break-through result by Byrka et al. [BGRS10] (STOC 2010). Our algorithm hinges on an efficiently computable map from extreme points of the bidirected cut relaxation to feasible solutions of (DCR). As a consequence, together with [BGRS10] we immediately obtain an efficient 73/60-approximation for quasi-bipartite Steiner tree instances. We also present a particularly simple (BCR)-based random sampling algorithm that achieves a performance guarantee slightly better than 77/60.
Secure Compressed Reading in Smart Grids
Venue: arXiv cs.IT 2012
Year: 2012

Smart Grids measure energy usage in real-time and tailor supply and delivery accordingly, in order to improve power transmission and distribution. For the grids to operate effectively, it is critical to collect readings from massively-installed smart meters to control centers in an efficient and secure manner. In this paper, we propose a secure compressed reading scheme to address this critical issue. We observe that our collected real-world meter data express strong temporal correlations, indicating they are sparse in certain domains. We adopt Compressed Sensing technique to exploit this sparsity and design an efficient meter data transmission scheme. Our scheme achieves substantial efficiency offered by compressed sensing, without the need to know beforehand in which domain the meter data are sparse. This is in contrast to traditional compressed-sensing based scheme where such sparse-domain information is required a priori. We then design specific dependable scheme to work with our compressed sensing based data transmission scheme to make our meter reading reliable and secure. We provide performance guarantee for the correctness, efficiency, and security of our proposed scheme. Through analysis and simulations, we demonstrate the effectiveness of our schemes and compare their performance to prior arts.
Elitism Levels Traverse Mechanism For The Derivation of Upper Bounds on Unimodal Functions
Venue: arXiv cs.NE 2012
Year: 2012

In this article we present an Elitism Levels Traverse Mechanism that we designed to find bounds on population-based Evolutionary algorithms solving unimodal functions. We prove its efficiency theoretically and test it on OneMax function deriving bounds cμn log n - O(μ n). This analysis can be generalized to any similar algorithm using variants of tournament selection and genetic operators that flip or swap only 1 bit in each string.
Application of Steganography for Anonymity through the Internet
Venue: arXiv cs.CR 2012
Year: 2012

In this paper, a novel steganographic scheme based on chaotic iterations is proposed. This research work takes place into the information hiding security framework. The applications for anonymity and privacy through the Internet are regarded too. To guarantee such an anonymity, it should be possible to set up a secret communication channel into a web page, being both secure and robust. To achieve this goal, we propose an information hiding scheme being stego-secure, which is the highest level of security in a well defined and studied category of attacks called "watermark-only attack". This category of attacks is the best context to study steganography-based anonymity through the Internet. The steganalysis of our steganographic process is also studied in order to show it security in a real test framework.
DPCube: Differentially Private Histogram Release through Multidimensional Partitioning
Venue: arXiv cs.DB 2012
Year: 2012

Differential privacy is a strong notion for protecting individual privacy in privacy preserving data analysis or publishing. In this paper, we study the problem of differentially private histogram release for random workloads. We study two multidimensional partitioning strategies including: 1) a baseline cell-based partitioning strategy for releasing an equi-width cell histogram, and 2) an innovative 2-phase kd-tree based partitioning strategy for releasing a v-optimal histogram. We formally analyze the utility of the released histograms and quantify the errors for answering linear queries such as counting queries. We formally characterize the property of the input data that will guarantee the optimality of the algorithm. Finally, we implement and experimentally evaluate several applications using the released histograms, including counting queries, classification, and blocking for record linkage and show the benefit of our approach.
Global $H_\infty$ Consensus of Multi-Agent Systems with Lipschitz Nonlinear Dynamics
Venue: arXiv cs.SY 2012
Year: 2012

This paper addresses the global consensus problems of a class of nonlinear multi-agent systems with Lipschitz nonlinearity and directed communication graphs, by using a distributed consensus protocol based on the relative states of neighboring agents. A two-step algorithm is presented to construct a protocol, under which a Lipschitz multi-agent system without disturbances can reach global consensus for a strongly connected directed communication graph. Another algorithm is then given to design a protocol which can achieve global consensus with a guaranteed $H_\infty$ performance for a Lipschitz multiagent system subject to external disturbances. The case with a leader-follower communication graph is also discussed. Finally, the effectiveness of the theoretical results is demonstrated through a network of single-link manipulators.
L1-norm minimization for quaternion signals
Venue: arXiv cs.NA 2012
Year: 2012

The l1-norm minimization problem plays an important role in the compressed sensing (CS) theory. We present in this letter an algorithm for solving the problem of l1-norm minimization for quaternion signals by converting it to second-order cone programming. An application example of the proposed algorithm is also given for practical guidelines of perfect recovery of quaternion signals. The proposed algorithm may find its potential application when CS theory meets the quaternion signal processing.