OpenRaiser/Intern-Atlas huggingface dataset:
Probabilistic verifiers for asymmetric debates
Venue: arXiv cs.CC 2012
Year: 2012

We examine the power of silent constant-space probabilistic verifiers that watch asymmetric debates (where one side is unable to see some of the messages of the other) between two deterministic provers, and try to determine who is right. We prove that probabilistic verifiers outperform their deterministic counterparts as asymmetric debate checkers. It is shown that the membership problem for every language in NSPACE(s(n)) has a 2^{s(n)}-time debate where one prover is completely blind to the other one, for polynomially bounded space constructible s(n). When partial information is allowed to be seen by the handicapped prover, the class of languages debatable in 2^{s(n)} time contains TIME(2^{s(n)}), so a probabilistic finite automaton can solve any decision problem in P with small error in polynomial time with the aid of such a debate. We also compare our systems with those with a single prover, and with competing-prover interactive proof systems.
Approximation Schemes for Covering and Packing
Venue: arXiv cs.CG 2012
Year: 2012

The local search framework for obtaining PTASs for NP-hard geometric optimization problems was introduced, independently, by Chan and Har-Peled (2009) and Mustafa and Ray (2010). In this paper, we generalize the framework by extending its analysis to additional families of graphs, beyond the family of planar graphs. We then present several applications of the generalized framework, some of which are very different from those presented to date (using the original framework). These applications include PTASs for finding a maximum l-shallow set of a set of fat objects, for finding a maximum triangle matching in an l-shallow unit disk graph, and for vertex-guarding a (not-necessarily-simple) polygon under an appropriate shallowness assumption. We also present a PTAS (using the original framework) for the important problem where one has to find a minimum-cardinality subset of a given set of disks (of varying radii) that covers a given set of points, and apply it to a class cover problem (studied in Bereg et al., 2012) to obtain an improved solution.
APS Implementation Over Vehicular Ad Hoc Networks
Venue: arXiv cs.NI 2012
Year: 2012

The real world scenario has changed from the wired connection to wireless connection.Over the years software, development has responded to the increasing growth of wireless connectivity in developing network enabled software.The problem arises in the wireless domain due to random packet loss in transport layer and as well as in data link layer for the end to end connection. The basic problem has been considered in this work is to convert the real world scenario of Vehicular ad hoc network into a lab oriented problem by used the APS-system and study the result to achieve better performance in the wireless domain. The real world physical problems map into analytical problem and simulate that analytic problem with respect to real world scenario by Automated Position System (APS) for antenna mounted over the mobile node in 2 Dimension space. Here the methodology quantifies the performance and the impact of the packet loss, delay, by the bit error rate and throughput with respect to the real- world scenario of VANET in the MAC layer, data link layer and transport layer. The result presents the Directional Antenna which is mounted over the vehicle gives less bit error in comparison to Isotropic and Discone antenna.
Developing Improved Greedy Crossover to Solve Symmetric Traveling Salesman Problem
Venue: arXiv cs.NE 2012
Year: 2012

The Traveling Salesman Problem (TSP) is one of the most famous optimization problems. Greedy crossover designed by Greffenstette et al, can be used while Symmetric TSP (STSP) is resolved by Genetic Algorithm (GA). Researchers have proposed several versions of greedy crossover. Here we propose improved version of it. We compare our greedy crossover with some of recent crossovers, we use our greedy crossover and some recent crossovers in GA then compare crossovers on speed and accuracy.
Game Theoretical Modelling for Dynamic Spectrum Access in TV Whitespace
Venue: arXiv cs.GT 2012
Year: 2012

In order to assess TV whitespace access scenarios, three oligopoly game models are considered and reformulated in terms of radio access: Cournot, Stackelberg, and Bertrand. Besides revisiting the relevance of Nash and Pareto equilibria, a new equilibrium concept, the joint Nash-Pareto equilibrium, is considered. An evolutionary game equilibria detection method is used. The analysis of the simulation results brings relevant insights on the issue of autonomy vs. regulation in emerging cognitive radio environments.
Model based neuro-fuzzy ASR on Texas processor
Venue: arXiv cs.CV 2012
Year: 2012

In this paper an algorithm for recognizing speech has been proposed. The recognized speech is used to execute related commands which use the MFCC and two kind of classifiers, first one uses MLP and second one uses fuzzy inference system as a classifier. The experimental results demonstrate the high gain and efficiency of the proposed algorithm. We have implemented this system based on graphical design and tested on a fix point digital signal processor (DSP) of 600 MHz, with reference DM6437-EVM of Texas instrument.
The Medusa of Spatial Sorting: 3D Kinetic Alpha Complexes and Implementation
Venue: arXiv cs.CG 2012
Year: 2012

Motivated by an application in cell biology, we consider spatial sorting processes defined by particles moving from an initial to a final configuration. We describe an algorithm for constructing a cell complex in space-time, called the medusa, that measures topological properties of the sorting process. The algorithm requires an extension of the kinetic data structures framework from Delaunay triangulations to fixed-radius alpha complexes. We report on several techniques to accelerate the computation.
Secure electronic lock using pic 16f628a microcontroller
Venue: arXiv cs.OH 2012
Year: 2012

The proposed system implements the electronic embedded lock, its provides a great benefit over traditional lock, which use the manual key, so if the key lost or theft then anybody could open the lock, while thieving or losing the long and complex password is harder compare to traditional key, furthermore combining both manual key with computerized password make the system more secure. Long password will reduce the possibilities of breaking the code and opening the lock. The system comprised keypad, and HD44780 20x2 LCD Along with PIC16f628a microcontroller. The firmware control these components such that interaction with keypad is very is ver easy and smoothly, the LCD provide user with messages and notification to be informed about what is the system state. User can performing opening and closing the lock, changing the current password in the microcontroller EEPROM and clearing single digit while entering the password when wrong digit entered (back space). The proposed system firmware developed using assembly language with MPLAB development environment. It tested and implemented in real hardware with proper functioning and bug free.
A New Compression Based Index Structure for Efficient Information Retrieval
Venue: arXiv cs.IR 2012
Year: 2012

Finding desired information from large data set is a difficult problem. Information retrieval is concerned with the structure, analysis, organization, storage, searching, and retrieval of information. Index is the main constituent of an IR system. Now a day exponential growth of information makes the index structure large enough affecting the IR system's quality. So compressing the Index structure is our main contribution in this paper. We compressed the document number in inverted file entries using a new coding technique based on run-length encoding. Our coding mechanism uses a specified code which acts over run-length coding. We experimented and found that our coding mechanism on an average compresses 67.34% percent more than the other techniques.
Segmentation of Breast Regions in Mammogram Based on Density: A Review
Venue: arXiv cs.CV 2012
Year: 2012

The focus of this paper is to review approaches for segmentation of breast regions in mammograms according to breast density. Studies based on density have been undertaken because of the relationship between breast cancer and density. Breast cancer usually occurs in the fibroglandular area of breast tissue, which appears bright on mammograms and is described as breast density. Most of the studies are focused on the classification methods for glandular tissue detection. Others highlighted on the segmentation methods for fibroglandular tissue, while few researchers performed segmentation of the breast anatomical regions based on density. There have also been works on the segmentation of other specific parts of breast regions such as either detection of nipple position, skin-air interface or pectoral muscles. The problems on the evaluation performance of the segmentation results in relation to ground truth are also discussed in this paper.
On computable approximations of Landau's constant
Venue: arXiv cs.NA 2012
Year: 2012

We present an algorithm which computes the Landau constant up to any given precision.
A Tutorial for Creating and Publishing Open Source Lisp Software
Venue: arXiv cs.OH 2012
Year: 2012

The proliferation and accessability of the Internet have made it simple to view, download, and publish source code. This paper gives a short tutorial on how to create a new Common Lisp project and publish it.
Extension du formalisme des flux opérationnels par une algèbre temporelle
Venue: arXiv cs.AI 2012
Year: 2012

Workflows constitute an important language to represent knowledge about processes, but also increasingly to reason on such knowledge. On the other hand, there is a limit to which time constraints between activities can be expressed. Qualitative interval algebras can model processes using finer temporal relations, but they cannot reproduce all workflow patterns. This paper defines a common ground model-theoretical semantics for both workflows and interval algebras, making it possible for reasoning systems working with either to interoperate. Thanks to this, interesting properties and inferences can be defined, both on workflows and on an extended formalism combining workflows with interval algebras. Finally, similar formalisms proposing a sound formal basis for workflows and extending them are discussed.
Environmental Sounds Spectrogram Classification using Log-Gabor Filters and Multiclass Support Vector Machines
Venue: arXiv cs.CV 2012
Year: 2012

This paper presents novel approaches for efficient feature extraction using environmental sound magnitude spectrogram. We propose approach based on the visual domain. This approach included three methods. The first method is based on extraction for each spectrogram a single log-Gabor filter followed by mutual information procedure. In the second method, the spectrogram is passed by the same steps of the first method but with an averaged bank of 12 log-Gabor filter. The third method consists of spectrogram segmentation into three patches, and after that for each spectrogram patch we applied the second method. The classification results prove that the second method is the most efficient in our environmental sound classification system.
Windows into Relational Events: Data Structures for Contiguous Subsequences of Edges
Venue: arXiv cs.DS 2012
Year: 2012

We consider the problem of analyzing social network data sets in which the edges of the network have timestamps, and we wish to analyze the subgraphs formed from edges in contiguous subintervals of these timestamps. We provide data structures for these problems that use near-linear preprocessing time, linear space, and sublogarithmic query time to handle queries that ask for the number of connected components, number of components that contain cycles, number of vertices whose degree equals or is at most some predetermined value, number of vertices that can be reached from a starting set of vertices by time-increasing paths, and related queries.
Investigation of Hill Cipher Modifications Based on Permutation and Iteration
Venue: arXiv cs.CR 2012
Year: 2012

Two recent Hill cipher modifications which iteratively use interweaving and interlacing are considered. We show that strength of these ciphers is due to non-linear transformation used in them (bit-level permutations). Impact of number of iterations on the avalanche effect is investigated. We propose two Hill cipher modifications using column swapping and arbitrary permutation with significantly less computational complexity (2 iterations are used versus 16). The proposed modifications decrease encryption time while keeping the strength of the ciphers. Numerical experiments for two proposed ciphers indicate that they can provide a substantial avalanche effect.
On the correctness of a branch displacement algorithm
Venue: arXiv cs.LO 2012
Year: 2012

The branch displacement problem is a well-known problem in assembler design. It revolves around the feature, present in several processor families, of having different instructions, of different sizes, for jumps of different displacements. The problem, which is provably NP-hard, is then to select the instructions such that one ends up with the smallest possible program. During our research with the CerCo project on formally verifying a C compiler, we have implemented and proven correct an algorithm for this problem. In this paper, we discuss the problem, possible solutions, our specific solutions and the proofs.
Toward Cloud Computing Evolution
Venue: arXiv cs.CY 2012
Year: 2012

-Information Technology (IT) shaped the success of organizations, giving them a solid foundation that increases both their level of efficiency as well as productivity. The computing industry is witnessing a paradigm shift in the way computing is performed worldwide. There is a growing awareness among consumers and enterprises to access their IT resources extensively through a "utility" model known as "cloud computing." Cloud computing was initially rooted in distributed grid-based computing. It has become a significant technology trend and expect that cloud computing will reshape IT processes and the IT marketplace. With the cloud computing technology, clients use a variety of smart mobile devices to access programs, storage, and application-development platforms over the network and internet, through services offered by cloud computing providers.An innovative new way to boost capacity and add capabilities in computing without spending money on a new infrastructure, training new personnel or licensing software is one of the characteristics of a cloud computing. Demands for fastest access to information is changing and increasing, therefore, the availability of cloud computing has made it easier for organizations to share and store related data and information with their stakeholders.Moreover, cloud computing is the use of internet-based services to support business processes.Our research is to find out what the demand and main emphasized of cloud computing compared with efficiency, trendy and security that leads to improved business processes within corporate as cloud user.
A Diffie-Hellman Key Exchange Using Matrices Over Non Commutative Rings
Venue: arXiv cs.CR 2012
Year: 2012

We consider a key exchange procedure whose security is based on the difficulty of computing discrete logarithms in a group, and where exponentiation is hidden by a conjugation. We give a platform-dependent cryptanalysis of this protocol. Finally, to take full advantage of this procedure, we propose a group of matrices over a noncommutative ring as platform group
More Is Better: Large Scale Partially-supervised Sentiment Classification - Appendix
Venue: arXiv cs.LG 2012
Year: 2012

We describe a bootstrapping algorithm to learn from partially labeled data, and the results of an empirical study for using it to improve performance of sentiment classification using up to 15 million unlabeled Amazon product reviews. Our experiments cover semi-supervised learning, domain adaptation and weakly supervised learning. In some cases our methods were able to reduce test error by more than half using such large amount of data. NOTICE: This is only the supplementary material.
Cryptanalysis and Improvements on Some Graph-based Authentication Schemes
Venue: arXiv cs.CR 2012
Year: 2012

In 2010, Grigoriev and Shpilrain, introduced some graph-based authentication schemes. We present a cryptanalysis of some of these protocols, and introduce some new schemes to fix the problems.
Four-Step Approach Model of Inspection (FAMI) for Effective Defect Management in Software Development
Venue: arXiv cs.SE 2012
Year: 2012

IT industry should inculcate effective defect management on a continual basis to deploy nearly a zerodefect product to their customers. Inspection is one of the most imperative and effective strategies of defect management. Nevertheless, existing defect management strategies in leading software industries are successful to deliver a maximum of 96% defect-free product. An empirical study of various projects across several service-based and product-based industries proves the above affirmations. This paper provides an enhanced approach of inspection through a Four-Step Approach Model of Inspection (FAMI). FAMI consists of i) integration of Inspection Life Cycle in V-model of software development, ii) implementation of process metric Depth of Inspection (DI), iii) implementation of people metric Inspection Performance Metric (IPM), iv) application of Bayesian probability approach for selection of appropriate values of inspection affecting parameters to achieve the desirable DI. The managers of software houses can make use of P2 metric as a benchmarking tool for the projects in order to improve the in-house defect management process. Implementation of FAMI in software industries reflects a continual process improvement and leads to the development of nearly a zero-defect product through effective defect management.
Vulnerability Management for an Enterprise Resource Planning System
Venue: arXiv cs.OH 2012
Year: 2012

Enterprise resource planning (ERP) systems are commonly used in technical educational institutions(TEIs). ERP systems should continue providing services to its users irrespective of the level of failure. There could be many types of failures in the ERP systems. There are different types of measures or characteristics that can be defined for ERP systems to handle the levels of failure. Here in this paper, various types of failure levels are identified along with various characteristics which are concerned with those failures. The relation between all these is summarized. The disruptions causing vulnerabilities in TEIs are identified .A vulnerability management cycle has been suggested along with many commercial and open source vulnerability management tools. The paper also highlights the importance of resiliency in ERP systems in TEIs.
Online Financial Algorithms Competitive Analysis
Venue: arXiv cs.CE 2012
Year: 2012

Analysis of algorithms with complete knowledge of its inputs is sometimes not up to our expectations. Many times we are surrounded with such scenarios where inputs are generated without any prior knowledge. Online Algorithms have found their applicability in broad areas of computer engineering. Among these, an online financial algorithm is one of the most important areas where lots of efforts have been used to produce an efficient algorithm. In this paper various Online Algorithms have been reviewed for their efficiency and various alternative measures have been explored for analysis purposes.
Optimal Solution for the Index Coding Problem Using Network Coding over GF(2)
Venue: arXiv cs.IT 2012
Year: 2012

The index coding problem is a fundamental transmission problem which occurs in a wide range of multicast networks. Network coding over a large finite field size has been shown to be a theoretically efficient solution to the index coding problem. However the high computational complexity of packet encoding and decoding over a large finite field size, and its subsequent penalty on encoding and decoding throughput and higher energy cost makes it unsuitable for practical implementation in processor and energy constraint devices like mobile phones and wireless sensors. While network coding over GF(2) can alleviate these concerns, it comes at a tradeoff cost of degrading throughput performance. To address this tradeoff, we propose a throughput optimal triangular network coding scheme over GF(2). We show that such a coding scheme can supply unlimited number of innovative packets and the decoding involves the simple back substitution. Such a coding scheme provides an efficient solution to the index coding problem and its lower computation and energy cost makes it suitable for practical implementation on devices with limited processing and energy capacity.
Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
Venue: arXiv cs.DS 2012
Year: 2012

We study the parameterized complexity of the directed variant of the classical {\sc Steiner Tree} problem on various classes of directed sparse graphs. While the parameterized complexity of {\sc Steiner Tree} parameterized by the number of terminals is well understood, not much is known about the parameterization by the number of non-terminals in the solution tree. All that is known for this parameterization is that both the directed and the undirected versions are W[2]-hard on general graphs, and hence unlikely to be fixed parameter tractable FPT. The undirected {\sc Steiner Tree} problem becomes FPT when restricted to sparse classes of graphs such as planar graphs, but the techniques used to show this result break down on directed planar graphs. In this article we precisely chart the tractability border for {\sc Directed Steiner Tree} (DST) on sparse graphs parameterized by the number of non-terminals in the solution tree. Specifically, we show that the problem is fixed parameter tractable on graphs excluding a topological minor, but becomes W[2]-hard on graphs of degeneracy 2. On the other hand we show that if the subgraph induced by the terminals is required to be acyclic then the problem becomes FPT on graphs of bounded degeneracy. We further show that our algorithm achieves the best possible running time dependence on the solution size and degeneracy of the input graph, under standard complexity theoretic assumptions. Using the ideas developed for DST, we also obtain improved algorithms for {\sc Dominating Set} on sparse undirected graphs. These algorithms are asymptotically optimal.
A fast parallel algorithm for minimum-cost small integral flows
Venue: arXiv cs.DC 2012
Year: 2012

We present a new approach to the minimum-cost integral flow problem for small values of the flow. It reduces the problem to the tests of simple multi-variate polynomials over a finite field of characteristic two for non-identity with zero. In effect, we show that a minimum-cost flow of value k in a network with n vertices, a sink and a source, integral edge capacities and positive integral edge costs polynomially bounded in n can be found by a randomized PRAM, with errors of exponentially small probability in n, running in O(k\log (kn)+\log^2 (kn)) time and using 2^{k}(kn)^{O(1)} processors. Thus, in particular, for the minimum-cost flow of value O(\log n), we obtain an RNC^2 algorithm.
Efficient Parallel Path Checking for Linear-Time Temporal Logic With Past and Bounds
Venue: arXiv cs.LO 2012
Year: 2012

Path checking, the special case of the model checking problem where the model under consideration is a single path, plays an important role in monitoring, testing, and verification. We prove that for linear-time temporal logic (LTL), path checking can be efficiently parallelized. In addition to the core logic, we consider the extensions of LTL with bounded-future (BLTL) and past-time (LTL+Past) operators. Even though both extensions improve the succinctness of the logic exponentially, path checking remains efficiently parallelizable: Our algorithm for LTL, LTL+Past, and BLTL+Past is in AC^1(logDCFL) \subseteq NC.