OpenRaiser/Intern-Atlas huggingface dataset:
New Optimization Approach Using Clustering-Based Parallel Genetic Algorithm
Venue: arXiv cs.NE 2013
Year: 2013

In many global Optimization Problems, it is required to evaluate a global point (min or max) in large space that calculation effort is very high. In this paper is presented new approach for optimization problem with subdivision labeling method (SLM) but in this method for higher dimensional has high calculation effort. Clustering-Based Parallel Genetic Algorithm (CBPGA) in optimization problems is one of the solutions of this problem. That the initial population is crossing points and subdividing in each step is according to mutation. After labeling all of crossing points, selecting is according to polytope that has complete label. In this method we propose an algorithm, based on parallelization scheme using master-slave. SLM algorithm is implemented by CBPGA and compared the experimental results. The numerical examples and numerical results show that SLMCBPGA is improved speed up and efficiency.
Solving Traveling Salesman Problem by Marker Method
Venue: arXiv cs.NE 2013
Year: 2013

In this paper we use marker method and propose a new mutation operator that selects the nearest neighbor among all near neighbors solving Traveling Salesman Problem.
Visual saliency estimation by integrating features using multiple kernel learning
Venue: arXiv cs.CV 2013
Year: 2013

In the last few decades, significant achievements have been attained in predicting where humans look at images through different computational models. However, how to determine contributions of different visual features to overall saliency still remains an open problem. To overcome this issue, a recent class of models formulates saliency estimation as a supervised learning problem and accordingly apply machine learning techniques. In this paper, we also address this challenging problem and propose to use multiple kernel learning (MKL) to combine information coming from different feature dimensions and to perform integration at an intermediate level. Besides, we suggest to use responses of a recently proposed filterbank of object detectors, known as Object-Bank, as additional semantic high-level features. Here we show that our MKL-based framework together with the proposed object-specific features provide state-of-the-art performance as compared to SVM or AdaBoost-based saliency models.
Speaker Independent Continuous Speech to Text Converter for Mobile Application
Venue: arXiv cs.CL 2013
Year: 2013

An efficient speech to text converter for mobile application is presented in this work. The prime motive is to formulate a system which would give optimum performance in terms of complexity, accuracy, delay and memory requirements for mobile environment. The speech to text converter consists of two stages namely front-end analysis and pattern recognition. The front end analysis involves preprocessing and feature extraction. The traditional voice activity detection algorithms which track only energy cannot successfully identify potential speech from input because the unwanted part of the speech also has some energy and appears to be speech. In the proposed system, VAD that calculates energy of high frequency part separately as zero crossing rate to differentiate noise from speech is used. Mel Frequency Cepstral Coefficient (MFCC) is used as feature extraction method and Generalized Regression Neural Network is used as recognizer. MFCC provides low word error rate and better feature extraction. Neural Network improves the accuracy. Thus a small database containing all possible syllable pronunciation of the user is sufficient to give recognition accuracy closer to 100%. Thus the proposed technique entertains realization of real time speaker independent applications like mobile phones, PDAs etc.
Entropy of Closure Operators
Venue: arXiv cs.IT 2013
Year: 2013

The entropy of a closure operator has been recently proposed for the study of network coding and secret sharing. In this paper, we study closure operators in relation to their entropy. We first introduce four different kinds of rank functions for a given closure operator, which determine bounds on the entropy of that operator. This yields new axioms for matroids based on their closure operators. We also determine necessary conditions for a large class of closure operators to be solvable. We then define the Shannon entropy of a closure operator, and use it to prove that the set of closure entropies is dense. Finally, we justify why we focus on the solvability of closure operators only.
Human and Automatic Evaluation of English-Hindi Machine Translation
Venue: arXiv cs.CL 2013
Year: 2013

For the past 60 years, Research in machine translation is going on. For the development in this field, a lot of new techniques are being developed each day. As a result, we have witnessed development of many automatic machine translators. A manager of machine translation development project needs to know the performance increase/decrease, after changes have been done in his system. Due to this reason, a need for evaluation of machine translation systems was felt. In this article, we shall present the evaluation of some machine translators. This evaluation will be done by a human evaluator and by some automatic evaluation metrics, which will be done at sentence, document and system level. In the end we shall also discuss the comparison between the evaluations.
Synthesis from Knowledge-Based Specifications
Venue: arXiv cs.LO 2013
Year: 2013

In program synthesis, we transform a specification into a program that is guaranteed to satisfy the specification. In synthesis of reactive systems, the environment in which the program operates may behave nondeterministically, e.g., by generating different sequences of inputs in different runs of the system. To satisfy the specification, the program needs to act so that the specification holds in every computation generated by its interaction with the environment. Often, the program cannot observe all attributes of its environment. In this case, we should transform a specification into a program whose behavior depends only on the observable history of the computation. This is called synthesis with incomplete information. In such a setting, it is desirable to have a knowledge-based specification, which can refer to the uncertainty the program has about the environment's behavior. In this work we solve the problem of synthesis with incomplete information with respect to specifications in the logic of knowledge and time. We show that the problem has the same worst-case complexity as synthesis with complete information.
Electronic Visualisation in Chemistry: From Alchemy to Art
Venue: arXiv cs.GR 2013
Year: 2013

Chemists now routinely use software as part of their work. For example, virtual chemistry allows chemical reactions to be simulated. In particular, a selection of software is available for the visualisation of complex 3-dimensional molecular structures. Many of these are very beautiful in their own right. As well as being included as illustrations in academic papers, such visualisations are often used on the covers of chemistry journals as artistically decorative and attractive motifs. Chemical images have also been used as the basis of artworks in exhibitions. This paper explores the development of the relationship of chemistry, art, and IT. It covers some of the increasingly sophisticated software used to generate these projections (e.g., UCSF Chimera) and their progressive use as a visual art form.
On construction and analysis of sparse random matrices and expander graphs with applications to compressed sensing
Venue: arXiv cs.IT 2013
Year: 2013

We revisit the probabilistic construction of sparse random matrices where each column has a fixed number of nonzeros whose row indices are drawn uniformly at random. These matrices have a one-to-one correspondence with the adjacency matrices of lossless expander graphs. We present tail bounds on the probability that the cardinality of the set of neighbors for these graphs will be less than the expected value. The bounds are derived through the analysis of collisions in unions of sets using a {\em dyadic splitting} technique. This analysis led to the derivation of better constants that allow for quantitative theorems on existence of lossless expander graphs and hence the sparse random matrices we consider and also quantitative compressed sensing sampling theorems when using sparse non mean-zero measurement matrices.
Mutual information matrices are not always positive semi-definite
Venue: arXiv cs.IT 2013
Year: 2013

For discrete random variables X_1,..., X_n we construct an n by n matrix. In the (i,j) entry we put the mutual information I(X_i;X_j) between X_i and X_j. In particular, in the (i,i) entry we put the entropy H(X_i)=I(X_i;X_i) of X_i. This matrix, called the mutual information matrix of (X_1,...,X_n), has been conjectured to be positive semi-definite. In this note, we give counterexamples to the conjecture, and show that the conjecture holds for up to three random variables.
Study of Encryption and Decryption of Wave File in Image Formats
Venue: arXiv cs.CR 2013
Year: 2013

This paper describes a novel method of encrypting wave files in popular image formats like JPEG, TIF and PNG along with retrieving them from these image files. MATLAB software is used to perform matrix manipulation to encrypt and decrypt sound files into and from image files. This method is not only a stenographic means but also a data compression technique.
Aggregation and Control of Populations of Thermostatically Controlled Loads by Formal Abstractions
Venue: arXiv cs.SY 2013
Year: 2013

This work discusses a two-step procedure, based on formal abstractions, to generate a finite-space stochastic dynamical model as an aggregation of the continuous temperature dynamics of a homogeneous population of Thermostatically Controlled Loads (TCL). The temperature of a single TCL is described by a stochastic difference equation and the TCL status (ON, OFF) by a deterministic switching mechanism. The procedure is formal as it allows the exact quantification of the error introduced by the abstraction -- as such it builds and improves on a known, earlier approximation technique in the literature. Further, the contribution discusses the extension to the case of a heterogeneous population of TCL by means of two approaches resulting in the notion of approximate abstractions. It moreover investigates the problem of global (population-level) regulation and load balancing for the case of TCL that are dependent on a control input. The procedure is tested on a case study and benchmarked against the mentioned alternative approach in the literature.
Efficient quantum protocols for XOR functions
Venue: arXiv cs.CC 2013
Year: 2013

We show that for any Boolean function f on {0,1}^n, the bounded-error quantum communication complexity of XOR functions $f\circ \oplus$ satisfies that $Q_ε(f\circ \oplus) = O(2^d (\log\|\hat f\|_{1,ε} + \log \frac{n}ε) \log(1/ε))$, where d is the F2-degree of f, and $\|\hat f\|_{1,ε} = \min_{g:\|f-g\|_\infty \leq ε} \|\hat f\|_1$. This implies that the previous lower bound $Q_ε(f\circ \oplus) = Ω(\log\|\hat f\|_{1,ε})$ by Lee and Shraibman \cite{LS09} is tight for f with low F2-degree. The result also confirms the quantum version of the Log-rank Conjecture for low-degree XOR functions. In addition, we show that the exact quantum communication complexity satisfies $Q_E(f) = O(2^d \log \|\hat f\|_0)$, where $\|\hat f\|_0$ is the number of nonzero Fourier coefficients of f. This matches the previous lower bound $Q_E(f(x,y)) = Ω(\log rank(M_f))$ by Buhrman and de Wolf \cite{BdW01} for low-degree XOR functions.
CONE-DHT: A distributed self-stabilizing algorithm for a heterogeneous storage system
Venue: arXiv cs.DC 2013
Year: 2013

We consider the problem of managing a dynamic heterogeneous storage system in a distributed way so that the amount of data assigned to a host in that system is related to its capacity. Two central problems have to be solved for this: (1) organizing the hosts in an overlay network with low degree and diameter so that one can efficiently check the correct distribution of the data and route between any two hosts, and (2) distributing the data among the hosts so that the distribution respects the capacities of the hosts and can easily be adapted as the set of hosts or their capacities change. We present distributed protocols for these problems that are self-stabilizing and that do not need any global knowledge about the system such as the number of nodes or the overall capacity of the system. Prior to this work no solution was known satisfying these properties.
Interdisciplinary Research Collaborations: Evaluation of a Funding Program
Venue: arXiv cs.DL 2013
Year: 2013

Innovative ideas are often situated where disciplines meet, and socio-economic problems generally require contributions from several disciplines. Ways to stimulate interdisciplinary research collaborations are therefore an increasing point of attention for science policy. There is concern that 'regular' funding programs, involving advice from disciplinary experts and discipline-bound viewpoints, may not adequately stimulate, select or evaluate this kind of research. This has led to specific policies aimed at interdisciplinary research in many countries. There is however at this moment no generally accepted method to adequately select and evaluate interdisciplinary research. In the vast context of different forms of interdisciplinarity, this paper aims to contribute to the debate on best practices to stimulate and support interdisciplinary research collaborations. It describes the selection procedures and results of a university program supporting networks formed 'bottom up', integrating expertise from different disciplines. The program's recent evaluation indicates that it is successful in selecting and supporting the interdisciplinary synergies aimed for, responding to a need experienced in the field. The analysis further confirms that potential for interdisciplinary collaboration is present in all disciplines.
Spin glass approach to the feedback vertex set problem
Venue: arXiv cs.CC 2013
Year: 2013

A feedback vertex set (FVS) of an undirected graph is a set of vertices that contains at least one vertex of each cycle of the graph. The feedback vertex set problem consists of constructing a FVS of size less than a certain given value. This combinatorial optimization problem has many practical applications, but it is in the nondeterministic polynomial-complete class of worst-case computational complexity. In this paper we define a spin glass model for the FVS problem and then study this model on the ensemble of finite-connectivity random graphs. In our model the global cycle constraints are represented through the local constraints on all the edges of the graph, and they are then treated by distributed message-passing procedures such as belief propagation. Our belief propagation-guided decimation algorithm can construct nearly optimal feedback vertex sets for single random graph instances and regular lattices. We also design a spin glass model for the FVS problem on a directed graph. Our work will be very useful for identifying the set of vertices that contribute most significantly to the dynamical complexity of a large networked system.
A Survey of Home Energy Management Systems in Future Smart Grid Communications
Venue: arXiv cs.NI 2013
Year: 2013

In this paper we present a systematic review of various home energy management (HEM) schemes. Employment of home energy management programs will make the electricity consumption smarter and more efficient. Advantages of HEM include, increased savings for consumers as well as utilities, reduced peak to average ratio (PAR) and peak demand. Where there are numerous applications of smart grid technologies, home energy management is probably the most important one to be addressed. Utilities across the globe have taken various steps for efficient consumption of electricity. New pricing schemes like, Real Time Pricing (RTP), Time of Use (ToU), Inclining Block Rates (IBR), Critical Peak Pricing (CPP) etc, have been proposed for smart grid. Distributed Energy Resources (DER) (local generation) and/or home appliances coordination along with different tariff schemes lead towards efficient consumption of electricity. This work also discusses a HEM systems general architecture and various challenges in implementation of this architecture in smart grid.
DREEM-ME: Distributed Regional Energy Efficient Multi-hop Routing Protocol based on Maximum Energy in WSNs
Venue: arXiv cs.NI 2013
Year: 2013

Wireless distributed sensor network consists of randomly deployed sensors having low energy assets. These networks can be used for monitoring a variety of environments. Major problems of these networks are energy constraints and their finite lifetimes. To overcome these problems different routing protocols and clustering techniques are introduced. We propose DREEM-ME which uses a unique technique for clustering to overcome these two problems efficiently. DREEM-ME elects a fix number of cluster heads (CHs) in each round instead of probabilistic selection of CHs. Packet Drop Technique is also implemented in our protocol to make it more comprehensive and practical. In DREEM-ME confidence interval is also shown in each graph which helps in visualising the maximum deviation from original course. Our simulations and results show that DREEM-ME is much better than existing protocols of the same nature.
An approximation algorithm for the Bandpass-2 problem
Venue: arXiv cs.DS 2013
Year: 2013

The general Bandpass-$B$ problem is NP-hard and can be approximated by a reduction into the weighted $B$-set packing problem, with a worst case performance ratio of $O(B^2)$. When $B = 2$, a maximum weight matching gives a 2-approximation to the problem. In this paper, we call the Bandpass-2 problem simply the Bandpass problem. The Bandpass problem can be viewed as a variation of the maximum traveling salesman problem, in which the edge weights are dynamic rather than given at the front. We present a ${426}{227}$-approximation algorithm for the problem. Such an improved approximation is built on an intrinsic structural property proven for the optimal solution and several novel schemes to partition a $b$-matching into desired matchings.
Toward Recovering Complete SRS for Softbody Simulation System and a Sample Application -- a Team 9a SOEN6481 W13 Project Report
Venue: arXiv cs.SE 2013
Year: 2013

This document aims at specifying the requirements and capturing the needs of users for building a softbody simulation system. This system has different applications ranging from computer games to surgery training which facilitates the creation and visualization of a certain softbody object. It also allows users to interact with created object at real time. A softbody or deformable object is an object whose shape changes due to an external force. Deformation type varies depending on the amount of object deformation. Each object can have multiple layers and each layer can have its own properties. So layers can be different in pressure, density and motion.
SIMPLE: Stable Increased-throughput Multi-hop Protocol for Link Efficiency in Wireless Body Area Networks
Venue: arXiv cs.NI 2013
Year: 2013

In this work, we propose a reliable, power efficient and high throughput routing protocol for Wireless Body Area Networks (WBANs). We use multi-hop topology to achieve minimum energy consumption and longer network lifetime. We propose a cost function to select parent node or forwarder. Proposed cost function selects a parent node which has high residual energy and minimum distance to sink. Residual energy parameter balances the energy consumption among the sensor nodes while distance parameter ensures successful packet delivery to sink. Simulation results show that our proposed protocol maximize the network stability period and nodes stay alive for longer period. Longer stability period contributes high packet delivery to sink which is major interest for continuous patient monitoring.
LPCH and UDLPCH: Location-aware Routing Techniques in WSNs
Venue: arXiv cs.NI 2013
Year: 2013

Wireless sensor nodes along with Base Station (BS) constitute a Wireless Sensor Network (WSN). Nodes comprise of tiny power battery. Nodes sense the data and send it to BS. WSNs need protocol for efficient energy consumption of the network. In direct transmission and minimum transmission energy routing protocols, energy consumption is not well distributed. However, LEACH (Low-Energy Adaptive Clustering Hierarchy) is a clustering protocol; randomly selects the Cluster Heads (CHs) in each round. However, random selection of CHs does not guarantee efficient energy consumption of the network. Therefore, we proposed new clustering techniques in routing protocols, Location-aware Permanent CH (LPCH) and User Defined Location-aware Permanent CH (UDLPCH). In both protocols, network field is physically divided in to two regions, equal number of nodes are randomly deployed in each region. In LPCH, number of CHs are selected by LEACH algorithm in first round. However in UDLPCH, equal and optimum number of CHs are selected in each region, throughout the network life time number of CHs are remain same. Simulation results show that stability period and throughput of LPCH is greater than LEACH, stability period and throughput of UDLPCH is greater than LPCH.
Gardner's Minichess Variant is solved
Venue: arXiv cs.GT 2013
Year: 2013

A 5x5 board is the smallest board on which one can set up all kind of chess pieces as a start position. We consider Gardner's minichess variant in which all pieces are set as in a standard chessboard (from Rook to King). This game has roughly 9x10^{18} legal positions and is comparable in this respect with checkers. We weakly solve this game, that is we prove its game-theoretic value and give a strategy to draw against best play for White and Black sides. Our approach requires surprisingly small computing power. We give a human readable proof. The way the result is obtained is generic and could be generalized to bigger chess settings or to other games.
On the Scalability of Reliable Data Transfer in High Speed Networks
Venue: arXiv cs.NI 2013
Year: 2013

This paper considers reliable data transfer in a high-speed network (HSN) in which the per-connection capacity is very large. We focus on sliding window protocols employing selective repeat for reliable data transfer and study two reliability mechanisms based on ARQ and FEC. The question we ask is which mechanism is more suitable for an HSN in which the scalability of reliable data transfer in terms of receiver's buffer requirement and achievable delay and throughput is a concern. To efficiently utilize the large bandwidth available to a connection in an HSN, sliding window protocols require a large transmission window. In this regime of large transmission windows, we show that while both mechanisms achieve the same asymptotic throughput in the presence of packet losses, their delay and buffer requirements are different. Specifically, an FEC-based mechanism has delay and receiver's buffer requirement that are asymptotically smaller than that of an ARQ-based selective repeat mechanism by a factor of log W, where W is the window size of the selective repeat mechanism. This result is then used to investigate the implications of each reliability mechanism on protocol design in an HSN in terms of throughput, delay, buffer requirement, and control overhead.