OpenRaiser/Intern-Atlas huggingface dataset:
A Framework for Validating IS Research Based on a Pluralist Account of Truth and Correctness
Venue: arXiv cs.CY 2016
Year: 2016

Research in information systems includes a wide range of approaches which make a contribution in terms of knowledge, understanding, or practical developments. The measure of any research is, ultimately, its validity: are its finding true, or its recommendations correct? However, empirical studies show that discussion of validity in research is often weak. In this paper we examine the nature of truth and correctness in order to construct a validation framework that can encompass all the varied forms of research. Within philosophy, there has been much debate about truth, is it correspondence, coherence, consensual or pragmatic, and in fact current views revolve around the idea of a pluralist view of truth: it is one and many. Related to truth is the concept of correctness, and in particular the necessity of both internal correctness and external correctness. The framework we develop based on these concepts of truth and correctness has been applied to a range of research forms including positivist, mathematical, interpretive, design science, critical and action oriented. The benefits are: i) that a greater and more explicit focus on validity criteria will produce better research; ii) having a single framework can unite what at times seem conflicting approaches to research; iii) having criteria made explicit should encourage debate and further development.
A Novel Architecture for Computing Approximate Radon Transform
Venue: arXiv cs.CV 2016
Year: 2016

Radon transform is a type of transform which is used in image processing to transfer the image into intercept-slope coordinate. Its diagonal properties made it appropriate for some applications which need processes in different degrees. Radon transform computation needs a lot of arithmetic operations which makes it a compute-intensive algorithm. In literature an approximate algorithm for computing Radon transform is introduces which reduces the complexity of computations. But this algorithm is complex and need arbitrary accesses to memory. In this paper we proposed an algorithm which accesses to memory sequentially. In the following an architecture is introduced which uses pipeline to reduce the time complexity of algorithm.
On the Parametric Study of Lubricating Oil Production using an Artificial Neural Network (ANN) Approach
Venue: arXiv cs.LG 2016
Year: 2016

In this study, an Artificial Neural Network (ANN) approach is utilized to perform a parametric study on the process of extraction of lubricants from heavy petroleum cuts. To train the model, we used field data collected from an industrial plant. Operational conditions of feed and solvent flow rate, Temperature of streams and mixing rate were considered as the input to the model, whereas the flow rate of the main product was considered as the output of the ANN model. A feed-forward Multi-Layer Perceptron Neural Network was successfully applied to capture the relationship between inputs and output parameters.
Modeling news spread as an SIR process over temporal networks
Venue: arXiv cs.SI 2016
Year: 2016

News spread in internet media outlets can be seen as a contagious process generating temporal networks representing the influence between published articles. In this article we propose a methodology based on the application of natural language analysis of the articles to reconstruct the spread network. From the reconstructed network, we show that the dynamics of the news spread can be approximated by a classical SIR epidemiological dynamics upon the network. From the results obtained we argue that the methodology proposed can be used to make predictions about media repercussion, and also to detect viral memes in news streams.
A Robust Asynchronous Newton Method for Massive Scale Computing Systems
Venue: arXiv cs.DC 2016
Year: 2016

Volunteer computing grids offer super-computing levels of computing power at the relatively low cost of operating a server. In previous work, the authors have shown that it is possible to take traditionally iterative evolutionary algorithms and execute them on volunteer computing grids by performing them asynchronously. The asynchronous implementations dramatically increase scalability and decrease the time taken to converge to a solution. Iterative and asynchronous optimization algorithms implemented using MPI on clusters and supercomputers, and BOINC on volunteer computing grids have been packaged together in a framework for generic distributed optimization (FGDO). This paper presents a new extension to FGDO for an asynchronous Newton method (ANM) for local optimization. ANM is resilient to heterogeneous, faulty and unreliable computing nodes and is extremely scalable. Preliminary results show that it can converge to a local optimum significantly faster than conjugate gradient descent does.
NP - P is not empty
Venue: arXiv cs.CC 2016
Year: 2016

We present the MEoP problem that decides the existence of solutions to certain modular equations over prime numbers and show how this separates the complexity class NP from its subclass P
Response to Refutation of Aslam's Proof that NP = P
Venue: arXiv cs.CC 2017
Year: 2017

This paper provides a further refinement to the previous response by introducing new structures and algorithms for counting VMPs of common \emph{Edge Requirement} (ER) and hence for counting the perfect matchings.
The assembly modes of rigid 11-bar linkages
Venue: arXiv cs.RO 2017
Year: 2017

Designing an m-bar linkage with a maximal number of assembly modes is important in robot kinematics, and has further applications in structural biology and computational geometry. A related question concerns the number of assembly modes of rigid mechanisms as a function of their nodes n, which is uniquely defined given m. Rigid 11-bar linkages, where n=7, are the simplest planar linkages for which these questions were still open. It will be proven that the maximal number of assembly modes of such linkages is exactly 56. The rigidity of a linkage is captured by a polynomial system derived from distance, or Cayley-Menger, matrices. The upper bound on the number of assembly modes is obtained as the mixed volume of a 5x5 system. An 11-bar linkage admitting 56 configurations is constructed using stochastic optimisation methods. This yields a general lower bound of $Ω(2.3^n)$ on the number of assembly modes, slightly improving the current record of $Ω(2.289^n)$, while the best known upper bound is roughly $4^n$. Our methods are straightforward and have been implemented in Maple. They are described in general terms illustrating the fact that they can be readily extended to other planar or spatial linkages. The main results have been reported in conference publication [EM11]. This version (2017) typesets correctly the last Figure 5 so as to include all 28 configurations modulo reflection.
Sound and complete axiomatizations of coalgebraic language equivalence
Venue: arXiv cs.LO 2017
Year: 2017

Coalgebras provide a uniform framework to study dynamical systems, including several types of automata. In this paper, we make use of the coalgebraic view on systems to investigate, in a uniform way, under which conditions calculi that are sound and complete with respect to behavioral equivalence can be extended to a coarser coalgebraic language equivalence, which arises from a generalised powerset construction that determinises coalgebras. We show that soundness and completeness are established by proving that expressions modulo axioms of a calculus form the rational fixpoint of the given type functor. Our main result is that the rational fixpoint of the functor $FT$, where $T$ is a monad describing the branching of the systems (e.g. non-determinism, weights, probability etc.), has as a quotient the rational fixpoint of the "determinised" type functor $\bar F$, a lifting of $F$ to the category of $T$-algebras. We apply our framework to the concrete example of weighted automata, for which we present a new sound and complete calculus for weighted language equivalence. As a special case, we obtain non-deterministic automata, where we recover Rabinovich's sound and complete calculus for language equivalence.
An adjusted payoff-based procedure for normal form games
Venue: arXiv cs.GT 2017
Year: 2017

We study a simple adaptive model in the framework of an N -player normal form game. The model consists of a repeated game where the players only know their own action space and their own payoff scored at each stage, not those of the other agents. Each player, in order to update her mixed action, computes the average vector payoff she has obtained by using the number of times she has played each pure action. The resulting stochastic process is analyzed via the ODE method from stochastic approximation theory. We are interested in the convergence of the process to rest points of the related continuous dynamics. Results concerning almost sure convergence and convergence with positive probability are obtained and applied to a traffic game. We also provide some examples where convergence occurs with probability zero.
Wireless Network Coding with Local Network Views: Coded Layer Scheduling
Venue: arXiv cs.IT 2017
Year: 2017

One of the fundamental challenges in the design of distributed wireless networks is the large dynamic range of network state. Since continuous tracking of global network state at all nodes is practically impossible, nodes can only acquire limited local views of the whole network to design their transmission strategies. In this paper, we study multi-layer wireless networks and assume that each node has only a limited knowledge, namely 1-local view, where each S-D pair has enough information to perform optimally when other pairs do not interfere, along with connectivity information for rest of the network. We investigate the information-theoretic limits of communication with such limited knowledge at the nodes. We develop a novel transmission strategy, namely Coded Layer Scheduling, that solely relies on 1-local view at the nodes and incorporates three different techniques: (1) per layer interference avoidance, (2) repetition coding to allow overhearing of the interference, and (3) network coding to allow interference neutralization. We show that our proposed scheme can provide a significant throughput gain compared with the conventional interference avoidance strategies. Furthermore, we show that our strategy maximizes the achievable normalized sum-rate for some classes of networks, hence, characterizing the normalized sum-capacity of those networks with 1-local view.
On the Complexity of Recognizing S-composite and S-prime Graphs
Venue: arXiv cs.CC 2017
Year: 2017

S-prime graphs are graphs that cannot be represented as nontrivial subgraphs of nontrivial Cartesian products of graphs, i.e., whenever it is a subgraph of a nontrivial Cartesian product graph it is a subgraph of one the factors. A graph is S-composite if it is not S-prime. Although linear time recognition algorithms for determining whether a graph is prime or not with respect to the Cartesian product are known, it remained unknown if a similar result holds also for the recognition of S-prime and S-composite graphs. In this contribution the computational complexity of recognizing S-composite and S-prime graphs is considered. Klav{ž}ar \emph{et al.} [\emph{Discr.\ Math.} \textbf{244}: 223-230 (2002)] proved that a graph is S-composite if and only if it admits a nontrivial path-$k$-coloring. The problem of determining whether there exists a path-$k$-coloring for a given graph is shown to be NP-complete even for $k=2$. This in turn is utilized to show that determining whether a graph is S-composite is NP-complete and thus, determining whether a graph is S-prime is CoNP-complete. Many other problems are shown to be NP-hard, using the latter results.
P = NP
Venue: arXiv cs.CC 2017
Year: 2017

The present work proves that P=NP. The proof, presented in this work, is a constructive one: the program of a polynomial time deterministic multi-tape Turing machine M_ExistsAcceptingPath, that determines if there exists an accepting computational path of a polynomial time non-deterministic single-tape Turing machine M_NP, is constructed (machine M_ExistsAcceptingPath is different for each Turing machine M_NP). Machine M_ExistsAcceptingPath is based on reduction to problem LP (linear programming) instead of reduction to problem 3-CNF-SAT which is commonly used. In more detail, machine M_AcceptingPath uses a reduction of the initial string problem to another string problem TCPE (defined in the paper) that is NP-complete and decidable in polynomial time. The time complexity of machine M_ExistsAcceptingPath is O(t(n)^{272}) wherein t(n) is an upper bound of the time complexity of machine M_NP.
Joint Space Neural Probabilistic Language Model for Statistical Machine Translation
Venue: arXiv cs.CL 2017
Year: 2017

A neural probabilistic language model (NPLM) provides an idea to achieve the better perplexity than n-gram language model and their smoothed language models. This paper investigates application area in bilingual NLP, specifically Statistical Machine Translation (SMT). We focus on the perspectives that NPLM has potential to open the possibility to complement potentially `huge' monolingual resources into the `resource-constraint' bilingual resources. We introduce an ngram-HMM language model as NPLM using the non-parametric Bayesian construction. In order to facilitate the application to various tasks, we propose the joint space model of ngram-HMM language model. We show an experiment of system combination in the area of SMT. One discovery was that our treatment of noise improved the results 0.20 BLEU points if NPLM is trained in relatively small corpus, in our case 500,000 sentence pairs, which is often the case due to the long training time of NPLM.
Hybrid Mechanisms: Trading off Strategyproofness and Efficiency of Random Assignment Mechanisms
Venue: arXiv cs.GT 2017
Year: 2017

Severe impossibility results restrict the design of strategyproof random assignment mechanisms, and trade-offs are necessary when aiming for more demanding efficiency requirements, such as ordinal or rank efficiency. We introduce hybrid mechanisms, which are convex combinations of two component mechanisms. We give a set of conditions under which such hybrids facilitate a non-degenerate trade-off between strategyproofness (in terms of partial strategyproofness) and efficiency (in terms of dominance). This set of conditions is tight in the sense that trade-offs may become degenerate if any of the conditions are dropped. Moreover, we give an algorithm for the mechanism designer's problem of determining a maximal mixing factor. Finally, we prove that our construction can be applied to mix Random Serial Dictatorship with Probabilistic Serial, as well as with the adaptive Boston mechanism, and we illustrate the efficiency gains numerically.
MCMC sampling colourings and independent sets of G(n,d/n) near the uniqueness threshold
Venue: arXiv cs.DM 2017
Year: 2017

Sampling from Gibbs distribution is a central problem in computer science as well as in statistical physics. In this work we focus on the k-colouring model} and the hard-core model with fugacity λwhen the underlying graph is an instance of Erdos-Renyi random graph G(n,p), where p=d/n and d is fixed. We use the Markov Chain Monte Carlo method for sampling from the aforementioned distributions. In particular, we consider Glauber (block) dynamics. We show a dramatic improvement on the bounds for rapid mixing in terms of the number of colours and the fugacity for the corresponding models. For both models the bounds we get are only within small constant factors from the conjectured ones by the statistical physicists. We use Path Coupling to show rapid mixing. For k and λin the range of our interest the technical challenge is to cope with the high degree vertices, i.e. vertices of degree much larger than the expected degree d. The usual approach to this problem is to consider block updates rather than single vertex updates for the Markov chain. Taking appropriately defined blocks the effect of high degree vertices somehow diminishes. However, devising such a construction of blocks is a highly non trivial task. We develop for a first time a weighting schema for the paths of the underlying graph. Vertices which belong to "light" paths, only, can be placed at the boundaries of the blocks. Then the tree-like local structure of G(n,d/n) allows the construction of simple structured blocks.
Somoclu: An Efficient Parallel Library for Self-Organizing Maps
Venue: arXiv cs.DC 2017
Year: 2017

Somoclu is a massively parallel tool for training self-organizing maps on large data sets written in C++. It builds on OpenMP for multicore execution, and on MPI for distributing the workload across the nodes in a cluster. It is also able to boost training by using CUDA if graphics processing units are available. A sparse kernel is included, which is useful for high-dimensional but sparse data, such as the vector spaces common in text mining workflows. Python, R and MATLAB interfaces facilitate interactive use. Apart from fast execution, memory use is highly optimized, enabling training large emergent maps even on a single computer.
Random crossings in dependency trees
Venue: arXiv cs.CL 2017
Year: 2017

It has been hypothesized that the rather small number of crossings in real syntactic dependency trees is a side-effect of pressure for dependency length minimization. Here we answer a related important research question: what would be the expected number of crossings if the natural order of a sentence was lost and replaced by a random ordering? We show that this number depends only on the number of vertices of the dependency tree (the sentence length) and the second moment about zero of vertex degrees. The expected number of crossings is minimum for a star tree (crossings are impossible) and maximum for a linear tree (the number of crossings is of the order of the square of the sequence length).
The Query Complexity of Correlated Equilibria
Venue: arXiv cs.GT 2017
Year: 2017

We consider the complexity of finding a correlated equilibrium of an $n$-player game in a model that allows the algorithm to make queries on players' payoffs at pure strategy profiles. Randomized regret-based dynamics are known to yield an approximate correlated equilibrium efficiently, namely, in time that is polynomial in the number of players $n$. Here we show that both randomization and approximation are necessary: no efficient deterministic algorithm can reach even an approximate correlated equilibrium, and no efficient randomized algorithm can reach an exact correlated equilibrium. The results are obtained by bounding from below the number of payoff queries that are needed.
Learning from networked examples in a k-partite graph
Venue: arXiv cs.LG 2017
Year: 2017

Many machine learning algorithms are based on the assumption that training examples are drawn independently. However, this assumption does not hold anymore when learning from a networked sample where two or more training examples may share common features. We propose an efficient weighting method for learning from networked examples and show the sample error bound which is better than previous work.
Approximating Minimum Cost Connectivity Orientation and Augmentation
Venue: arXiv cs.DS 2017
Year: 2017

We investigate problems addressing combined connectivity augmentation and orientations settings. We give a polynomial-time 6-approximation algorithm for finding a minimum cost subgraph of an undirected graph $G$ that admits an orientation covering a nonnegative crossing $G$-supermodular demand function, as defined by Frank. An important example is $(k,\ell)$-edge-connectivity, a common generalization of global and rooted edge-connectivity. Our algorithm is based on a non-standard application of the iterative rounding method. We observe that the standard linear program with cut constraints is not amenable and use an alternative linear program with partition and co-partition constraints instead. The proof requires a new type of uncrossing technique on partitions and co-partitions. We also consider the problem setting when the cost of an edge can be different for the two possible orientations. The problem becomes substantially more difficult already for the simpler requirement of $k$-edge-connectivity. Khanna, Naor, and Shepherd showed that the integrality gap of the natural linear program is at most $4$ when $k=1$ and conjectured that it is constant for all fixed $k$. We disprove this conjecture by showing an $Ω(|V|)$ integrality gap even when $k=2$.
The Vectorial $λ$-Calculus
Venue: arXiv cs.LO 2017
Year: 2017

We describe a type system for the linear-algebraic $λ$-calculus. The type system accounts for the linear-algebraic aspects of this extension of $λ$-calculus: it is able to statically describe the linear combinations of terms that will be obtained when reducing the programs. This gives rise to an original type theory where types, in the same way as terms, can be superposed into linear combinations. We prove that the resulting typed $λ$-calculus is strongly normalising and features weak subject reduction. Finally, we show how to naturally encode matrices and vectors in this typed calculus.
Genetic Algorithm for Solving Simple Mathematical Equality Problem
Venue: arXiv cs.NE 2017
Year: 2017

This paper explains genetic algorithm for novice in this field. Basic philosophy of genetic algorithm and its flowchart are described. Step by step numerical computation of genetic algorithm for solving simple mathematical equality problem will be briefly explained
Algorithmic Data Analytics, Small Data Matters and Correlation versus Causation
Venue: arXiv cs.CE 2017
Year: 2017

This is a review of aspects of the theory of algorithmic information that may contribute to a framework for formulating questions related to complex highly unpredictable systems. We start by contrasting Shannon Entropy and Kolmogorov-Chaitin complexity epitomizing the difference between correlation and causation to then move onto surveying classical results from algorithmic complexity and algorithmic probability, highlighting their deep connection to the study of automata frequency distributions. We end showing how long-range algorithmic predicting models for economic and biological systems may require infinite computation but locally approximated short-range estimations are possible thereby showing how small data can deliver important insights into important features of complex "Big Data".
An Overview of Nominal-Typing versus Structural-Typing in OOP
Venue: arXiv cs.PL 2017
Year: 2017

NOOP is a mathematical model of nominally-typed OOP that proves the identification of inheritance and subtyping in mainstream nominally-typed OO programming languages and the validity of this identification. This report gives an overview of the main notions in OOP relevant to constructing a mathematical model of OOP such as NOOP. The emphasis in this report is on defining nominality, nominal typing and nominal subtyping of mainstream nominally-typed OO languages, and on contrasting the three notions with their counterparts in structurally-typed OO languages, i.e., with structurality, structural typing and structural subtyping, respectively. An additional appendix demonstrates these notions and other related notions, and the differences between them, using some simple code examples. A detailed, more technical comparison between nominal typing and structural typing in OOP is presented in other publications.