OpenRaiser/Intern-Atlas huggingface dataset:
Collective computation in a network with distributed information
Venue: arXiv cs.SI 2014
Year: 2014

We analyze a distributed information network in which each node has access to the information contained in a limited set of nodes (its neighborhood) at a given time. A collective computation is carried out in which each node calculates a value that implies all information contained in the network (in our case, the average value of a variable that can take different values in each network node). The neighborhoods can change dynamically by exchanging neighbors with other nodes. The results of this collective calculation show rapid convergence and good scalability with the network size. These results are compared with those of a fixed network arranged as a square lattice, in which the number of rounds to achieve a given accuracy is very high when the size of the network increases. The results for the evolving networks are interpreted in light of the properties of complex networks and are directly relevant to the diameter and characteristic path length of the networks, which seem to express "small world" properties.
How Many Topics? Stability Analysis for Topic Models
Venue: arXiv cs.LG 2014
Year: 2014

Topic modeling refers to the task of discovering the underlying thematic structure in a text corpus, where the output is commonly presented as a report of the top terms appearing in each topic. Despite the diversity of topic modeling algorithms that have been proposed, a common challenge in successfully applying these techniques is the selection of an appropriate number of topics for a given corpus. Choosing too few topics will produce results that are overly broad, while choosing too many will result in the "over-clustering" of a corpus into many small, highly-similar topics. In this paper, we propose a term-centric stability analysis strategy to address this issue, the idea being that a model with an appropriate number of topics will be more robust to perturbations in the data. Using a topic modeling approach based on matrix factorization, evaluations performed on a range of corpora show that this strategy can successfully guide the model selection process.
Do electromagnetic waves exist in a short cable at low frequencies? What does physics say?
Venue: arXiv cs.CR 2014
Year: 2014

We refute a physical model, recently proposed by Gunn, Allison and Abbott (GAA) [arXiv:1402.2709v2], to utilize electromagnetic waves for eavesdropping on the Kirchhoff-law-Johnson-noise (KLJN) secure key distribution. Their model, and its theoretical underpinnings, is found to be fundamentally flawed because their assumption of electromagnetic waves violates not only the wave equation but also the Second Law of Thermodynamics, the Principle of Detailed Balance, Boltzmann's Energy Equipartition Theorem, and Planck's formula by implying infinitely strong blackbody radiation. We deduce the correct mathematical model of the GAA scheme, which is based on impedances at the quasi-static limit. Mathematical analysis and simulation results confirm our approach and prove that GAA's experimental interpretation is incorrect too.
Knowledge-Driven Game Design by Non-Programmers
Venue: arXiv cs.SE 2014
Year: 2014

Game extension is an entertaining activity that offers an opportunity to test new design approaches by non-programmers. The real challenge is to enable this activity by means of a suitable infrastructure. We propose a knowledge-driven approach with natural game-player concepts. These concepts, found in game ontologies, include game abstractions and rules for game moves. The approach has been implemented and tested for board games. These include tic-tac-toe as a simplest example, enabling extensions of tic-tac- toe, say to a four-by-four board and Sudoku, a single player game of a very different nature.
Ontology as a Source for Rule Generation
Venue: arXiv cs.AI 2014
Year: 2014

This paper discloses the potential of OWL (Web Ontology Language) ontologies for generation of rules. The main purpose of this paper is to identify new types of rules, which may be generated from OWL ontologies. Rules, generated from OWL ontologies, are necessary for the functioning of the Semantic Web Expert System. It is expected that the Semantic Web Expert System (SWES) will be able to process ontologies from the Web with the purpose to supplement or even to develop its knowledge base.
A new combination approach based on improved evidence distance
Venue: arXiv cs.AI 2014
Year: 2014

Dempster-Shafer evidence theory is a powerful tool in information fusion. When the evidence are highly conflicting, the counter-intuitive results will be presented. To adress this open issue, a new method based on evidence distance of Jousselme and Hausdorff distance is proposed. Weight of each evidence can be computed, preprocess the original evidence to generate a new evidence. The Dempster's combination rule is used to combine the new evidence. Comparing with the existing methods, the new proposed method is efficient.
Polynomials Modulo Composite Numbers: Ax-Katz type theorems for the structure of their solution sets
Venue: arXiv cs.CC 2014
Year: 2014

We extend the Ax-Katz theorem for a single polynomial from finite fields to the rings Z_m with m composite. This extension not only yields the analogous result, but gives significantly higher divisibility bounds. We conjecture what computer runs suggest is the optimal result for any m, and prove a special case of it. The special case is for m = 2^r and polynomials of degree 2. Our results also yield further properties of the solution spaces. Polynomials modulo composites are the focus of some computational complexity lower bound frontiers, while those modulo 2^r arise in the simulation of quantum circuits. We give some prospective applications of this research.
(Semi-)External Algorithms for Graph Partitioning and Clustering
Venue: arXiv cs.DS 2014
Year: 2014

In this paper, we develop semi-external and external memory algorithms for graph partitioning and clustering problems. Graph partitioning and clustering are key tools for processing and analyzing large complex networks. We address both problems in the (semi-)external model by adapting the size-constrained label propagation technique. Our (semi-)external size-constrained label propagation algorithm can be used to compute graph clusterings and is a prerequisite for the (semi-)external graph partitioning algorithm. The algorithm is then used for both the coarsening and the refinement phase of a multilevel algorithm to compute graph partitions. Our algorithm is able to partition and cluster huge complex networks with billions of edges on cheap commodity machines. Experiments demonstrate that the semi-external graph partitioning algorithm is scalable and can compute high quality partitions in time that is comparable to the running time of an efficient internal memory implementation. A parallelization of the algorithm in the semi-external model further reduces running time.
Improved ESP-index: a practical self-index for highly repetitive texts
Venue: arXiv cs.DS 2014
Year: 2014

While several self-indexes for highly repetitive texts exist, developing a practical self-index applicable to real world repetitive texts remains a challenge. ESP-index is a grammar-based self-index on the notion of edit-sensitive parsing (ESP), an efficient parsing algorithm that guarantees upper bounds of parsing discrepancies between different appearances of the same subtexts in a text. Although ESP-index performs efficient top-down searches of query texts, it has a serious issue on binary searches for finding appearances of variables for a query text, which resulted in slowing down the query searches. We present an improved ESP-index (ESP-index-I) by leveraging the idea behind succinct data structures for large alphabets. While ESP-index-I keeps the same types of efficiencies as ESP-index about the top-down searches, it avoid the binary searches using fast rank/select operations. We experimentally test ESP-index-I on the ability to search query texts and extract subtexts from real world repetitive texts on a large-scale, and we show that ESP-index-I performs better that other possible approaches.
Transmit Antenna Selection in Underlay Cognitive Radio Environment
Venue: arXiv cs.IT 2014
Year: 2014

Cognitive radio (CR) technology addresses the problem of spectrum under-utilization. In underlay CR mode, the secondary users are allowed to communicate provided that their transmission is not detrimental to primary user communication. Transmit antenna selection is one of the low-complexity methods to increase the capacity of wireless communication systems. In this article, we propose and analyze the performance benefit of a transmit antenna selection scheme for underlay secondary system that ensures the instantaneous interference caused by the secondary transmitter to the primary receiver is below a predetermined level. Closed-form expressions of the outage probability, amount of fading, and ergodic capacity for the secondary network are derived. Monte-carlo simulations are also carried out to confirm various mathematical results presented in this article.
Probabilistic Bisimulation: Naturally on Distributions
Venue: arXiv cs.LO 2014
Year: 2014

In contrast to the usual understanding of probabilistic systems as stochastic processes, recently these systems have also been regarded as transformers of probabilities. In this paper, we give a natural definition of strong bisimulation for probabilistic systems corresponding to this view that treats probability distributions as first-class citizens. Our definition applies in the same way to discrete systems as well as to systems with uncountable state and action spaces. Several examples demonstrate that our definition refines the understanding of behavioural equivalences of probabilistic systems. In particular, it solves a long-standing open problem concerning the representation of memoryless continuous time by memory-full continuous time. Finally, we give algorithms for computing this bisimulation not only for finite but also for classes of uncountably infinite systems.
Spatiotemporal Sparse Bayesian Learning with Applications to Compressed Sensing of Multichannel Physiological Signals
Venue: arXiv cs.IT 2014
Year: 2014

Energy consumption is an important issue in continuous wireless telemonitoring of physiological signals. Compressed sensing (CS) is a promising framework to address it, due to its energy-efficient data compression procedure. However, most CS algorithms have difficulty in data recovery due to non-sparsity characteristic of many physiological signals. Block sparse Bayesian learning (BSBL) is an effective approach to recover such signals with satisfactory recovery quality. However, it is time-consuming in recovering multichannel signals, since its computational load almost linearly increases with the number of channels. This work proposes a spatiotemporal sparse Bayesian learning algorithm to recover multichannel signals simultaneously. It not only exploits temporal correlation within each channel signal, but also exploits inter-channel correlation among different channel signals. Furthermore, its computational load is not significantly affected by the number of channels. The proposed algorithm was applied to brain computer interface (BCI) and EEG-based driver's drowsiness estimation. Results showed that the algorithm had both better recovery performance and much higher speed than BSBL. Particularly, the proposed algorithm ensured that the BCI classification and the drowsiness estimation had little degradation even when data were compressed by 80%, making it very suitable for continuous wireless telemonitoring of multichannel signals.
Sparse Approximation, List Decoding, and Uncertainty Principles
Venue: arXiv cs.IT 2014
Year: 2014

We consider list versions of sparse approximation problems, where unlike the existing results in sparse approximation that consider situations with unique solutions, we are interested in multiple solutions. We introduce these problems and present the first combinatorial results on the output list size. These generalize and enhance some of the existing results on threshold phenomenon and uncertainty principles in sparse approximations. Our definitions and results are inspired by similar results in list decoding. We also present lower bound examples that bolster our results and show they are of the appropriate size.
Graph Kernels via Functional Embedding
Venue: arXiv cs.LG 2014
Year: 2014

We propose a representation of graph as a functional object derived from the power iteration of the underlying adjacency matrix. The proposed functional representation is a graph invariant, i.e., the functional remains unchanged under any reordering of the vertices. This property eliminates the difficulty of handling exponentially many isomorphic forms. Bhattacharyya kernel constructed between these functionals significantly outperforms the state-of-the-art graph kernels on 3 out of the 4 standard benchmark graph classification datasets, demonstrating the superiority of our approach. The proposed methodology is simple and runs in time linear in the number of edges, which makes our kernel more efficient and scalable compared to many widely adopted graph kernels with running time cubic in the number of vertices.
Sum-of-squares proofs and the quest toward optimal algorithms
Venue: arXiv cs.DS 2014
Year: 2014

In order to obtain the best-known guarantees, algorithms are traditionally tailored to the particular problem we want to solve. Two recent developments, the Unique Games Conjecture (UGC) and the Sum-of-Squares (SOS) method, surprisingly suggest that this tailoring is not necessary and that a single efficient algorithm could achieve best possible guarantees for a wide range of different problems. The Unique Games Conjecture (UGC) is a tantalizing conjecture in computational complexity, which, if true, will shed light on the complexity of a great many problems. In particular this conjecture predicts that a single concrete algorithm provides optimal guarantees among all efficient algorithms for a large class of computational problems. The Sum-of-Squares (SOS) method is a general approach for solving systems of polynomial constraints. This approach is studied in several scientific disciplines, including real algebraic geometry, proof complexity, control theory, and mathematical programming, and has found applications in fields as diverse as quantum information theory, formal verification, game theory and many others. We survey some connections that were recently uncovered between the Unique Games Conjecture and the Sum-of-Squares method. In particular, we discuss new tools to rigorously bound the running time of the SOS method for obtaining approximate solutions to hard optimization problems, and how these tools give the potential for the sum-of-squares method to provide new guarantees for many problems of interest, and possibly to even refute the UGC.
The Frobenius anatomy of word meanings I: subject and object relative pronouns
Venue: arXiv cs.CL 2014
Year: 2014

This paper develops a compositional vector-based semantics of subject and object relative pronouns within a categorical framework. Frobenius algebras are used to formalise the operations required to model the semantics of relative pronouns, including passing information between the relative clause and the modified noun phrase, as well as copying, combining, and discarding parts of the relative clause. We develop two instantiations of the abstract semantics, one based on a truth-theoretic approach and one based on corpus statistics.
CitNetExplorer: A new software tool for analyzing and visualizing citation networks
Venue: arXiv cs.DL 2014
Year: 2014

We present CitNetExplorer, a new software tool for analyzing and visualizing citation networks of scientific publications. CitNetExplorer can for instance be used to study the development of a research field, to delineate the literature on a research topic, and to support literature reviewing. We first introduce the main concepts that need to be understood when working with CitNetExplorer. We then demonstrate CitNetExplorer by using the tool to analyze the scientometric literature and the literature on community detection in networks. Finally, we discuss some technical details on the construction, visualization, and analysis of citation networks in CitNetExplorer.
Critique of J. Kim's "P is not equal to NP by Modus Tollens"
Venue: arXiv cs.CC 2014
Year: 2014

This paper is a critique of version three of Joonmo Kim's paper entitled "P is not equal to NP by Modus Tollens. [arXiv:1403.4143v3]" After summarizing Kim's proof, we note that the logic that Kim uses is inconsistent, which provides evidence that the proof is invalid. To show this, we will consider two reasonable interpretations of Kim's definitions, and show that "P is not equal to NP" does not seem to follow in an obvious way using any of them.
Morphological Analysis of the Bishnupriya Manipuri Language using Finite State Transducers
Venue: arXiv cs.CL 2014
Year: 2014

In this work we present a morphological analysis of Bishnupriya Manipuri language, an Indo-Aryan language spoken in the north eastern India. As of now, there is no computational work available for the language. Finite state morphology is one of the successful approaches applied in a wide variety of languages over the year. Therefore we adapted the finite state approach to analyse morphology of the Bishnupriya Manipuri language.
Games with a Weak Adversary
Venue: arXiv cs.LO 2014
Year: 2014

We consider multi-player graph games with partial-observation and parity objective. While the decision problem for three-player games with a coalition of the first and second players against the third player is undecidable, we present a decidability result for partial-observation games where the first and third player are in a coalition against the second player, thus where the second player is adversarial but weaker due to partial-observation. We establish tight complexity bounds in the case where player 1 is less informed than player 2, namely 2-EXPTIME-completeness for parity objectives. The symmetric case of player 1 more informed than player 2 is much more complicated, and we show that already in the case where player 1 has perfect observation, memory of size non-elementary is necessary in general for reachability objectives, and the problem is decidable for safety and reachability objectives. Our results have tight connections with partial-observation stochastic games for which we derive new complexity results.
Intersection Graphs: An Introduction
Venue: arXiv cs.DM 2014
Year: 2014

Intersection graphs are very important in both theoretical as well as application point of view. Depending on the geometrical representation, different type of intersection graphs are defined. Among them interval, circular-arc, permutation, trapezoid, chordal, disk, circle graphs are more important. In this article, a brief introduction of each of these intersection graphs is given. Some basic properties and algorithmic status of few problems on these graphs are cited. This article will help to the beginners to start work in this direction. Since the article contains a lot of information in a compact form it is also useful for the expert researchers too.
Optimal control of information epidemics modeled as Maki Thompson rumors
Venue: arXiv cs.SY 2014
Year: 2014

We model the spread of information in a homogeneously mixed population using the Maki Thompson rumor model. We formulate an optimal control problem, from the perspective of single campaigner, to maximize the spread of information when the campaign budget is fixed. Control signals, such as advertising in the mass media, attempt to convert ignorants and stiflers into spreaders. We show the existence of a solution to the optimal control problem when the campaigning incurs non-linear costs under the isoperimetric budget constraint. The solution employs Pontryagin's Minimum Principle and a modified version of forward backward sweep technique for numerical computation to accommodate the isoperimetric budget constraint. The techniques developed in this paper are general and can be applied to similar optimal control problems in other areas. We have allowed the spreading rate of the information epidemic to vary over the campaign duration to model practical situations when the interest level of the population in the subject of the campaign changes with time. The shape of the optimal control signal is studied for different model parameters and spreading rate profiles. We have also studied the variation of the optimal campaigning costs with respect to various model parameters. Results indicate that, for some model parameters, significant improvements can be achieved by the optimal strategy compared to the static control strategy. The static strategy respects the same budget constraint as the optimal strategy and has a constant value throughout the campaign horizon. This work finds application in election and social awareness campaigns, product advertising, movie promotion and crowdfunding campaigns.
The monoid of queue actions
Venue: arXiv cs.FL 2014
Year: 2014

We investigate the monoid of transformations that are induced by sequences of writing to and reading from a queue storage. We describe this monoid by means of a confluent and terminating semi-Thue system and study some of its basic algebraic properties, e.g., conjugacy. Moreover, we show that while several properties concerning its rational subsets are undecidable, their uniform membership problem is NL-complete. Furthermore, we present an algebraic characterization of this monoid's recognizable subsets. Finally, we prove that it is not Thurston-automatic.
Global Newton Iteration over Archimedean and non-Archimedean Fields
Venue: arXiv cs.NA 2014
Year: 2014

In this paper, we study iterative methods on the coefficients of the rational univariate representation (RUR) of a given algebraic set, called global Newton iteration. We compare two natural approaches to define locally quadratically convergent iterations: the first one involves Newton iteration applied to the approximate roots individually and then interpolation to find the RUR of these approximate roots; the second one considers the coefficients in the exact RUR as zeroes of a high dimensional map defined by polynomial reduction, and applies Newton iteration on this map. We prove that over fields with a p-adic valuation these two approaches give the same iteration function, but over fields equipped with the usual Archimedean absolute value, they are not equivalent. In the latter case, we give explicitly the iteration function for both approaches. Finally, we analyze the parallel complexity of the different versions of the global Newton iteration, compare them, and demonstrate that they can be efficiently computed. The motivation for this study comes from the certification of approximate roots of overdetermined and singular polynomial systems via the recovery of an exact RUR from approximate numerical data.
Hybrid Genetic Algorithm for Cloud Computing Applications
Venue: arXiv cs.DC 2014
Year: 2014

In this paper with the aid of genetic algorithm and fuzzy theory, we present a hybrid job scheduling approach, which considers the load balancing of the system and reduces total execution time and execution cost. We try to modify the standard Genetic algorithm and to reduce the iteration of creating population with the aid of fuzzy theory. The main goal of this research is to assign the jobs to the resources with considering the VM MIPS and length of jobs. The new algorithm assigns the jobs to the resources with considering the job length and resources capacities. We evaluate the performance of our approach with some famous cloud scheduling models. The results of the experiments show the efficiency of the proposed approach in term of execution time, execution cost and average Degree of Imbalance (DI).