OpenRaiser/Intern-Atlas huggingface dataset:
On the Computation of Fully Proportional Representation
Venue: arXiv cs.GT 2014
Year: 2014

We investigate two systems of fully proportional representation suggested by Chamberlin Courant and Monroe. Both systems assign a representative to each voter so that the "sum of misrepresentations" is minimized. The winner determination problem for both systems is known to be NP-hard, hence this work aims at investigating whether there are variants of the proposed rules and/or specific electorates for which these problems can be solved efficiently. As a variation of these rules, instead of minimizing the sum of misrepresentations, we considered minimizing the maximal misrepresentation introducing effectively two new rules. In the general case these "minimax" versions of classical rules appeared to be still NP-hard. We investigated the parameterized complexity of winner determination of the two classical and two new rules with respect to several parameters. Here we have a mixture of positive and negative results: e.g., we proved fixed-parameter tractability for the parameter the number of candidates but fixed-parameter intractability for the number of winners. For single-peaked electorates our results are overwhelmingly positive: we provide polynomial-time algorithms for most of the considered problems. The only rule that remains NP-hard for single-peaked electorates is the classical Monroe rule.
NuMVC: An Efficient Local Search Algorithm for Minimum Vertex Cover
Venue: arXiv cs.AI 2014
Year: 2014

The Minimum Vertex Cover (MVC) problem is a prominent NP-hard combinatorial optimization problem of great importance in both theory and application. Local search has proved successful for this problem. However, there are two main drawbacks in state-of-the-art MVC local search algorithms. First, they select a pair of vertices to exchange simultaneously, which is time-consuming. Secondly, although using edge weighting techniques to diversify the search, these algorithms lack mechanisms for decreasing the weights. To address these issues, we propose two new strategies: two-stage exchange and edge weighting with forgetting. The two-stage exchange strategy selects two vertices to exchange separately and performs the exchange in two stages. The strategy of edge weighting with forgetting not only increases weights of uncovered edges, but also decreases some weights for each edge periodically. These two strategies are used in designing a new MVC local search algorithm, which is referred to as NuMVC. We conduct extensive experimental studies on the standard benchmarks, namely DIMACS and BHOSLIB. The experiment comparing NuMVC with state-of-the-art heuristic algorithms show that NuMVC is at least competitive with the nearest competitor namely PLS on the DIMACS benchmark, and clearly dominates all competitors on the BHOSLIB benchmark. Also, experimental results indicate that NuMVC finds an optimal solution much faster than the current best exact algorithm for Maximum Clique on random instances as well as some structured ones. Moreover, we study the effectiveness of the two strategies and the run-time behaviour through experimental analysis.
Divide-And-Conquer Computation of Cylindrical Algebraic Decomposition
Venue: arXiv cs.SC 2014
Year: 2014

We present a divide-and-conquer version of the Cylindrical Algebraic Decomposition (CAD) algorithm. The algorithm represents the input as a Boolean combination of subformulas, computes cylindrical algebraic decompositions of solution sets of the subformulas, and combines the results. We propose a graph-based heuristic to find a suitable partitioning of the input and present empirical comparison with direct CAD computation.
LWRP: Low Power Consumption Weighting Replacement Policy using Buffer Memory
Venue: arXiv cs.OS 2014
Year: 2014

As the performance gap between memory and processors has increased, then it leads to the poor performance. Efficient virtual memory can overcome this problem. And the efficiency of virtual memory depends on the replacement policy used for cache. In this paper, our algorithm not only based on the time to last access and frequency index but, we also consider the power consumption. We show that Low Power Consumption Weighting Replacement Policy (LWRP) has better performance and low power consumption.
A survey on Human Computer Interaction Mechanism Using Finger Tracking
Venue: arXiv cs.HC 2014
Year: 2014

Human Computer Interaction (HCI) is a field in which developer makes a user friendly system. User can interact with a computer system without using any conventional peripheral devices. Marker is used to recognize hand movement accurately & successfully. Researchers establish the mechanism to interact with computer system using computer vision. The interaction is better than normal static keyboard and mouse. This paper represents most of innovative mechanisms of the finger tracking used to interact with a computer system using computer vision.
Short-term plasticity as cause-effect hypothesis testing in distal reward learning
Venue: arXiv cs.NE 2014
Year: 2014

Asynchrony, overlaps and delays in sensory-motor signals introduce ambiguity as to which stimuli, actions, and rewards are causally related. Only the repetition of reward episodes helps distinguish true cause-effect relationships from coincidental occurrences. In the model proposed here, a novel plasticity rule employs short and long-term changes to evaluate hypotheses on cause-effect relationships. Transient weights represent hypotheses that are consolidated in long-term memory only when they consistently predict or cause future rewards. The main objective of the model is to preserve existing network topologies when learning with ambiguous information flows. Learning is also improved by biasing the exploration of the stimulus-response space towards actions that in the past occurred before rewards. The model indicates under which conditions beliefs can be consolidated in long-term memory, it suggests a solution to the plasticity-stability dilemma, and proposes an interpretation of the role of short-term plasticity.
Water Eminence Scrutinizing Scheme Based On Zigbee and Wireless Antenna Expertise - A Study
Venue: arXiv cs.NI 2014
Year: 2014

Wireless Sensor Network is the essential structure of a water eminence monitoring by means of wireless sensor network technology To scrutinize water quality greater than different sites as a synchronized application an estimable system structural design constituted by spread sensor nodes and a base station is suggested The nodes and base stations are linked using WSN technology like Zigbee Base stations are related via Ethernet. Design and execution of a prototype using WSN technology are the exigent work. Data are identified by means of dissimilar sensors at the node plane to compute the parameters like turbidity and oxygen quantity is transmitted via WSN to the support station Information unruffled from the distant location is capable of displayed in diagram setup as well as it is able to be calculated using dissimilar replication tools at the supporting station. The recent methods have benefits such as null amount carbon emission low power utilization more stretchy to put together at distant locations.
Robust Satisfiability of Systems of Equations
Venue: arXiv cs.CC 2014
Year: 2014

We study the problem of \emph{robust satisfiability} of systems of nonlinear equations, namely, whether for a given continuous function $f:\,K\to\mathbb{R}^n$ on a~finite simplicial complex $K$ and $α>0$, it holds that each function $g:\,K\to\mathbb{R}^n$ such that $\|g-f\|_\infty \leq α$, has a root in $K$. Via a reduction to the extension problem of maps into a sphere, we particularly show that this problem is decidable in polynomial time for every fixed $n$, assuming $\dim K \le 2n-3$. This is a substantial extension of previous computational applications of \emph{topological degree} and related concepts in numerical and interval analysis. Via a reverse reduction we prove that the problem is undecidable when $\dim K\ge 2n-2$, where the threshold comes from the \emph{stable range} in homotopy theory. For the lucidity of our exposition, we focus on the setting when $f$ is piecewise linear. Such functions can approximate general continuous functions, and thus we get approximation schemes and undecidability of the robust satisfiability in other possible settings.
Fair Division and Redistricting
Venue: arXiv cs.GT 2014
Year: 2014

Recently, Landau, Reid and Yershov provided a novel solution to the problem of redistricting. Instead of trying to ensure fairness by restricting the shape of the possible maps or by assigning the power to draw the map to nonbiased entities, the solution ensures fairness by balancing competing interests against each other. This kind of solution is an example of what are known as "fair division" solutions--- such solutions involve the preferences of all parties and are accompanied by rigorous guarantees of a specified well-defined notion of fairness. In this expository article, we give an introduction to the ideas of fair division in the context of this redistricting solution. Through examples and discussion we clarify how fair division methods can play an important role in a realistic redistricting solution by introducing an interactive step that incorporates a certain kind of fairness that can be used in concert with, and not a substitute for, other necessary or desired criteria for a good redistricting solution.
A Secure Communication in Mobile Agent System
Venue: arXiv cs.CR 2014
Year: 2014

A mobile agent is a software code with mobility which can be move from a computer into another computers through network. The mobile agent paradigm provides many benefits in developments of distributed application at the same time introduce new requirements for security issues with these systems. In this article we present a solution for protection agent from other agents attacks with loging patterns of malicious agent and useing this log for communication. We implemented our resolution by JADE.
Bounds on Locally Recoverable Codes with Multiple Recovering Sets
Venue: arXiv cs.IT 2014
Year: 2014

A locally recoverable code (LRC code) is a code over a finite alphabet such that every symbol in the encoding is a function of a small number of other symbols that form a recovering set. Bounds on the rate and distance of such codes have been extensively studied in the literature. In this paper we derive upper bounds on the rate and distance of codes in which every symbol has $t\geq 1$ disjoint recovering sets.
On robustly asymmetric graphs
Venue: arXiv cs.DM 2014
Year: 2014

O'Donnell, Wright, Wu and Zhou [SODA 2014] introduced the notion of robustly asymmetric graphs. Roughly speaking, these are graphs in which for every $0 \le ρ\le 1$, every permutation that permutes a $ρ$ fraction of the vertices maps a $Θ(ρ)$ fraction of the edges to non-edges. We show that there are graphs for which the constant hidden in the $Θ$ notation is roughly~1.
Breaking a monad-comonad symmetry between computational effects
Venue: arXiv cs.LO 2014
Year: 2014

Computational effects may often be interpreted in the Kleisli category of a monad or in the coKleisli category of a comonad. The duality between monads and comonads corresponds, in general, to a symmetry between construction and observation, for instance between raising an exception and looking up a state. Thanks to the properties of adjunction one may go one step further: the coKleisli-on-Kleisli category of a monad provides a kind of observation with respect to a given construction, while dually the Kleisli-on-coKleisli category of a comonad provides a kind of construction with respect to a given observation. In the previous examples this gives rise to catching an exception and updating a state. However, the interpretation of computational effects is usually based on a category which is not self-dual, like the category of sets. This leads to a breaking of the monad-comonad duality. For instance, in a distributive category the state effect has much better properties than the exception effect. This remark provides a novel point of view on the usual mechanism for handling exceptions. The aim of this paper is to build an equational semantics for handling exceptions based on the coKleisli-on-Kleisli category of the monad of exceptions. We focus on n-ary functions and conditionals. We propose a programmer's language for exceptions and we prove that it has the required behaviour with respect to n-ary functions and conditionals.
Symblicit algorithms for optimal strategy synthesis in monotonic Markov decision processes (extended version)
Venue: arXiv cs.DS 2014
Year: 2014

When treating Markov decision processes (MDPs) with large state spaces, using explicit representations quickly becomes unfeasible. Lately, Wimmer et al. have proposed a so-called symblicit algorithm for the synthesis of optimal strategies in MDPs, in the quantitative setting of expected mean-payoff. This algorithm, based on the strategy iteration algorithm of Howard and Veinott, efficiently combines symbolic and explicit data structures, and uses binary decision diagrams as symbolic representation. The aim of this paper is to show that the new data structure of pseudo-antichains (an extension of antichains) provides another interesting alternative, especially for the class of monotonic MDPs. We design efficient pseudo-antichain based symblicit algorithms (with open source implementations) for two quantitative settings: the expected mean-payoff and the stochastic shortest path. For two practical applications coming from automated planning and LTL synthesis, we report promising experimental results w.r.t. both the run time and the memory consumption.
Quantum Cybernetics and Complex Quantum Systems Science - A Quantum Connectionist Exploration
Venue: arXiv cs.NE 2014
Year: 2014

Quantum cybernetics and its connections to complex quantum systems science is addressed from the perspective of complex quantum computing systems. In this way, the notion of an autonomous quantum computing system is introduced in regards to quantum artificial intelligence, and applied to quantum artificial neural networks, considered as autonomous quantum computing systems, which leads to a quantum connectionist framework within quantum cybernetics for complex quantum computing systems. Several examples of quantum feedforward neural networks are addressed in regards to Boolean functions' computation, multilayer quantum computation dynamics, entanglement and quantum complementarity. The examples provide a framework for a reflection on the role of quantum artificial neural networks as a general framework for addressing complex quantum systems that perform network-based quantum computation, possible consequences are drawn regarding quantum technologies, as well as fundamental research in complex quantum systems science and quantum biology.
On Designing Better Tools for Learning APIs
Venue: arXiv cs.SE 2014
Year: 2014

Modern software development requires a large investment in learning application programming interfaces (APIs). Recent research found that the learning materials themselves are often inadequate: developers struggle to find answers beyond simple usage scenarios. Solving these problems requires a large investment in tool and search engine development. To understand where further investment would be most useful, we ran a study with 19 professional developers to understand what a solution might look like, free of technical constraints. In this paper, we report on design implications of tools for API learning, grounded in the reality of the professional developers themselves. The reoccurring themes in the participants' feedback were trustworthiness, confidentiality, information overload and the need for code examples as first-class documentation artifacts.
An Improved AIS Based E-mail Classification Technique for Spam Detection
Venue: arXiv cs.CR 2014
Year: 2014

An improved email classification method based on Artificial Immune System is proposed in this paper to develop an immune based system by using the immune learning, immune memory in solving complex problems in spam detection. An optimized technique for e-mail classification is accomplished by distinguishing the characteristics of spam and non-spam that is been acquired from trained data set. These extracted features of spam and non-spam are then combined to make a single detector, therefore reducing the false rate. (Non-spam that were wrongly classified as spam). Effectiveness of our technique in decreasing the false rate shall be demonstrated by the result that will be acquired.
A Survey on Delay-Aware Network Structure for Wireless Sensor Networks with Consecutive Data Collection Processes
Venue: arXiv cs.NI 2014
Year: 2014

A Wireless Sensor Network (WSN) consists of spatially distributed autonomous sensors to monitor physical or environmental conditions, such as temperature, sound, pressure,etc. In sensing applications, data packets are flowing from sensor nodes to base station. In data collection processes, bottom up approach is used. In bottom up approach, all nodes send their sensed data packets to base station directly. In this approach will lead to increased delay, which will lead to higher energy consumption. To reduce the energy consumption of sensor nodes,Clustering Algorithm and Low-Energy Adaptive Clustering Hierarchy (LEACH) are being used. Efficient gathering in Wireless Sensor information systems, Power Efficient Gathering in Sensor Information System (PEGASIS) is being used. There are lot of research issues in Wireless Sensor Networks such as delay, lifetime of network, energy dissipation which needs to be resolved.
A Survey on an Effective Defense Mechanism against Reactive Jamming Attacks in WSN
Venue: arXiv cs.NI 2014
Year: 2014

A Wireless Sensor Network (WSN) is a self-configure network of sensor nodes communicate among themselves using radio signals and deployed in quantity to sense, monitor and to understand the physical world. A jammer is an entity which interferes with the physical transmission and reception of wireless communications. Reactive jamming attack is a major security problem in the wireless sensor network. The reactive jammer stays quiet when the channel is idle. The jammer starts transmitting a radio signal as soon as it senses activity on the channel. The reactive jammer nodes will be deactivated by identifying all the trigger nodes, at the same time a jammer node is localized by exploiting the changes in the neighbor nodes. The affected node can be identified, by analyzing the changes in its communication range, compared to its neighbors. The paper proposes a survey on trigger node identification and a detailed survey on techniques to identify trigger nodes and highly concentrated on the reactive jammer.
Towards High Performance Computing (Hpc) Through Parallel Programming Paradigms and Their Principles
Venue: arXiv cs.PL 2014
Year: 2014

Nowadays, we are to find out solutions to huge computing problems very rapidly. It brings the idea of parallel computing in which several machines or processors work cooperatively for computational tasks. In the past decades, there are a lot of variations in perceiving the importance of parallelism in computing machines. And it is observed that the parallel computing is a superior solution to many of the computing limitations like speed and density; non-recurring and high cost; and power consumption and heat dissipation etc. The commercial multiprocessors have emerged with lower prices than the mainframe machines and supercomputers machines. In this article the high performance computing (HPC) through parallel programming paradigms (PPPs) are discussed with their constructs and design approaches.
On-line secret sharing
Venue: arXiv cs.IT 2014
Year: 2014

In an on-line secret sharing scheme the dealer assigns shares in the order the participants show up, knowing only those qualified subsets whose all members she has seen. We assume that the overall access structure is known and only the order of the participants is unknown. On-line secret sharing is a useful primitive when the set of participants grows in time, and redistributing the secret is too expensive. In this paper we start the investigation of unconditionally secure on-line secret sharing schemes. The complexity of a secret sharing scheme is the size of the largest share a single participant can receive over the size of the secret. The infimum of this amount in the on-line or off-line setting is the on-line or off-line complexity of the access structure, respectively. For paths on at most five vertices and cycles on at most six vertices the on-line and offline complexities are equal, while for other paths and cycles these values differ. We show that the gap between these values can be arbitrarily large even for graph based access structures. We present a general on-line secret sharing scheme that we call first-fit. Its complexity is the maximal degree of the access structure. We show, however, that this on-line scheme is never optimal: the on-line complexity is always strictly less than the maximal degree. On the other hand, we give examples where the first-fit scheme is almost optimal, namely, the on-line complexity can be arbitrarily close to the maximal degree. The performance ratio is the ratio of the on-line and off-line complexities of the same access structure. We show that for graphs the performance ratio is smaller than the number of vertices, and for an infinite family of graphs the performance ratio is at least constant times the square root of the number of vertices.
Reconstruction Models for Attractors in the Technical and Economic Processes
Venue: arXiv cs.CE 2014
Year: 2014

The article discusses building models based on the reconstructed attractors of the time series. Discusses the use of the properties of dynamical chaos, namely to identify the strange attractors structure models. Here is used the group properties of differential equations, which consist in the symmetry of particular solutions. Examples of modeling engineering systems are given.
Co-clustering of Fuzzy Lagged Data
Venue: arXiv cs.AI 2014
Year: 2014

The paper focuses on mining patterns that are characterized by a fuzzy lagged relationship between the data objects forming them. Such a regulatory mechanism is quite common in real life settings. It appears in a variety of fields: finance, gene expression, neuroscience, crowds and collective movements are but a limited list of examples. Mining such patterns not only helps in understanding the relationship between objects in the domain, but assists in forecasting their future behavior. For most interesting variants of this problem, finding an optimal fuzzy lagged co-cluster is an NP-complete problem. We thus present a polynomial-time Monte-Carlo approximation algorithm for mining fuzzy lagged co-clusters. We prove that for any data matrix, the algorithm mines a fuzzy lagged co-cluster with fixed probability, which encompasses the optimal fuzzy lagged co-cluster by a maximum 2 ratio columns overhead and completely no rows overhead. Moreover, the algorithm handles noise, anti-correlations, missing values and overlapping patterns. The algorithm was extensively evaluated using both artificial and real datasets. The results not only corroborate the ability of the algorithm to efficiently mine relevant and accurate fuzzy lagged co-clusters, but also illustrate the importance of including the fuzziness in the lagged-pattern model.