OpenRaiser/Intern-Atlas huggingface dataset:
Modeling Cultural Dynamics
Venue: arXiv cs.MA 2019
Year: 2019

EVOC (for EVOlution of Culture) is a computer model of culture that enables us to investigate how various factors such as barriers to cultural diffusion, the presence and choice of leaders, or changes in the ratio of innovation to imitation affect the diversity and effectiveness of ideas. It consists of neural network based agents that invent ideas for actions, and imitate neighbors' actions. The model is based on a theory of culture according to which what evolves through culture is not memes or artifacts, but the internal models of the world that give rise to them, and they evolve not through a Darwinian process of competitive exclusion but a Lamarckian process involving exchange of innovation protocols. EVOC shows an increase in mean fitness of actions over time, and an increase and then decrease in the diversity of actions. Diversity of actions is positively correlated with population size and density, and with barriers between populations. Slowly eroding borders increase fitness without sacrificing diversity by fostering specialization followed by sharing of fit actions. Introducing a leader that broadcasts its actions throughout the population increases the fitness of actions but reduces diversity of actions. Increasing the number of leaders reduces this effect. Efforts are underway to simulate the conditions under which an agent immigrating from one culture to another contributes new ideas while still fitting in.
Cache Me If You Can: Capacitated Selfish Replication Games in Networks
Venue: arXiv cs.GT 2019
Year: 2019

In Peer-to-Peer (P2P) network systems, content (object) delivery between nodes is often required. One way to study such a distributed system is by defining games, which involve selfish nodes that make strategic choices on replicating content in their local limited memory (cache) or accessing content from other nodes for a cost. These Selfish Replication games have been introduced in [8] for nodes that do not have any capacity limits, leaving the capacitated problem, i.e. Capacitated Selfish Replication (CSR) games, open. In this work, we first form the model of the CSR games, for which we perform a Nash equilibria analysis. In particular, we focus on hierarchical networks, given their extensive use to model communication costs of content delivery in P2P systems. We present an exact polynomial-time algorithm for any hierarchical network, under two constraints on the utility functions: 1) "Nearer is better", i.e. the closest the content is to the node the less its access cost is, and 2) "Independence of irrelevant alternatives", i.e. aggregation of individual node preferences. This generalization represents a vast class of utilities and more interestingly allows each of the nodes to have simultaneously completely different functional forms of utility functions. In this general framework, we present CSR games results on arbitrary networks and outline the boundary between intractability and effective computability in terms of the network structure, object preferences, and the total number of objects. Moreover, we prove that the problem of equilibria existence becomes NP-hard for general CSR games.
A Linear Time Algorithm for Seeds Computation
Venue: arXiv cs.DS 2019
Year: 2019

A seed in a word is a relaxed version of a period in which the occurrences of the repeating subword may overlap. We show a linear-time algorithm computing a linear-size representation of all the seeds of a word (the number of seeds might be quadratic). In particular, one can easily derive the shortest seed and the number of seeds from our representation. Thus, we solve an open problem stated in the survey by Smyth (2000) and improve upon a previous O(n log n) algorithm by Iliopoulos, Moore, and Park (1996). Our approach is based on combinatorial relations between seeds and subword complexity (used here for the first time in context of seeds). In the previous papers, the compact representation of seeds consisted of two independent parts operating on the suffix tree of the word and the suffix tree of the reverse of the word, respectively. Our second contribution is a simpler representation of all seeds which avoids dealing with the reversed word. A preliminary version of this work, with a much more complex algorithm constructing the earlier representation of seeds, was presented at the 23rd Annual ACM-SIAM Symposium of Discrete Algorithms (SODA 2012).
k-Connectivity in Random Key Graphs with Unreliable Links
Venue: arXiv cs.IT 2019
Year: 2019

Random key graphs form a class of random intersection graphs and are naturally induced by the random key predistribution scheme of Eschenauer and Gligor for securing wireless sensor network (WSN) communications. Random key graphs have received much interest recently, owing in part to their wide applicability in various domains including recommender systems, social networks, secure sensor networks, clustering and classification analysis, and cryptanalysis to name a few. In this paper, we study connectivity properties of random key graphs in the presence of unreliable links. Unreliability of the edges are captured by independent Bernoulli random variables, rendering edges of the graph to be on or off independently from each other. The resulting model is an intersection of a random key graph and an Erdos-Renyi graph, and is expected to be useful in capturing various real-world networks; e.g., with secure WSN applications in mind, link unreliability can be attributed to harsh environmental conditions severely impairing transmissions. We present conditions on how to scale this model's parameters so that i) the minimum node degree in the graph is at least k, and ii) the graph is k-connected, both with high probability as the number of nodes becomes large. The results are given in the form of zeroone laws with critical thresholds identified and shown to coincide for both graph properties. These findings improve the previous results by Rybarczyk on the k-connectivity of random key graphs (with reliable links), as well as the zero-one laws by Yagan on the 1-connectivity of random key graphs with unreliable links.
Confusion of Tagged Perturbations in Forward Automatic Differentiation of Higher-Order Functions
Venue: arXiv cs.SC 2019
Year: 2019

Forward Automatic Differentiation (AD) is a technique for augmenting programs to compute derivatives. The essence of Forward AD is to attach perturbations to each number, and propagate these through the computation. When derivatives are nested, the distinct derivative calculations, and their associated perturbations, must be distinguished. This is typically accomplished by creating a unique tag for each derivative calculation, tagging the perturbations, and overloading the arithmetic operators. We exhibit a subtle bug, present in fielded implementations, in which perturbations are confused despite the tagging machinery. The essence of the bug is this: each invocation of a derivative creates a unique tag but a unique tag is needed for each derivative calculation. When taking derivatives of higher-order functions, these need not correspond! The derivative of a higher-order function $f$ that returns a function $g$ will be a function $f'$ that returns a function $\bar{g}$ that performs a derivative calculation. A single invocation of $f'$ will create a single fresh tag but that same tag will be used for each derivative calculation resulting from an invocation of $\bar{g}$. This situation arises when taking derivatives of curried functions. Two potential solutions are presented, and their serious deficiencies discussed. One requires eta expansion to delay the creation of fresh tags from the invocation of $f'$ to the invocation of $\bar{g}$, which can be difficult or even impossible in some circumstances. The other requires $f'$ to wrap $\bar{g}$ with tag renaming, which is difficult to implement without violating the desirable complexity properties of forward AD.
Meme and Variations: A Computer Model of Cultural Evolution
Venue: arXiv cs.MA 2019
Year: 2019

Holland's (1975) genetic algorithm is a minimal computer model of natural selection that made it possible to investigate the effect of manipulating specific parameters on the evolutionary process. If culture is, like biology, a form of evolution, it should be possible to similarly abstract the underlying skeleton of the process and develop a minimal model of it. Meme and Variations, or MAV, is a computational model, inspired by the genetic algorithm, of how ideas evolve in a society of interacting individuals (Gabora 1995). The name is a pun on the classical music form 'theme and variations', because it is based on the premise that novel ideas are variations of old ones; they result from tweaking or combining existing ideas in new ways (Holland et al. 1981). MAV explores the impact of biological phenomena such as over-dominance and epistasis as well as cognitive and social phenomena such as the ability to learn generalizations or imitate others on the fitness and diversity of cultural transmissible actions.
An Agent-based Model of the Cognitive Mechanisms Underlying the Origins of Creative Cultural Evolution
Venue: arXiv cs.MA 2019
Year: 2019

Human culture is uniquely cumulative and open-ended. Using a computational model of cultural evolution in which neural network based agents evolve ideas for actions through invention and imitation, we tested the hypothesis that this is due to the capacity for recursive recall. We compared runs in which agents were limited to single-step actions to runs in which they used recursive recall to chain simple actions into complex ones. Chaining resulted in higher cultural diversity, open-ended generation of novelty, and no ceiling on the mean fitness of actions. Both chaining and no-chaining runs exhibited convergence on optimal actions, but without chaining this set was static while with chaining it was ever-changing. Chaining increased the ability to capitalize on the capacity for learning. These findings show that the recursive recall hypothesis provides a computationally plausible explanation of why humans alone have evolved the cultural means to transform this planet.
Partitioning Clustering algorithms for handling numerical and categorical data: a review
Venue: arXiv cs.DB 2019
Year: 2019

Clustering is widely used in different field such as biology, psychology, and economics. Most traditional clustering algorithms are limited to handling datasets that contain either numeric or categorical attributes. However, datasets with mixed types of attributes are common in real life data mining applications. In this paper, we review partitioning based algorithm such as K-prototype, Extension of K-prototype, K-histogram, Fuzzy approaches, genetic approaches, etc. These algorithm works on both numerical and categorical data. The approaches has been proposed to handle mixed data are based on four different perceptive: i) split data set into two part such that each part contain either numerical or categorical data, then apply separate clustering algorithm on each data set, finally combined the result of both clustering algorithm, ii) converting categorical attribute into numerical attribute and apply numerical attribute clustering algorithm; iii) discrimination of numerical attribute and apply categorical based clustering algorithm; iv) Conversion of the categorical attributes into binary ones and apply any numerical based clustering algorithm
Updating Neighbour Cell List via Crowdsourced User Reports: a Framework for Measuring Time Performance
Venue: arXiv cs.NI 2019
Year: 2019

In this paper we introduce the idea of estimating local topology in wireless networks by means of crowdsourced user reports. In this approach each user periodically reports to the serving basestation information about the set of neighbouring basestations observed by the user. We show that, by mapping the local topological structure of the network onto states of increasing knowledge, a crisp mathematical framework can be obtained, which allows in turn for the use of a variety of user mobility models. Using a simplified mobility model we show how obtain useful upper bounds on the expected time for a basestation to gain full knowledge of its local neighbourhood, answering the fundamental question about which classes of network deployments can effectively benefit from a crowdsourcing approach.
Multi-agent Inverse Reinforcement Learning for Two-person Zero-sum Games
Venue: arXiv cs.GT 2019
Year: 2019

The focus of this paper is a Bayesian framework for solving a class of problems termed multi-agent inverse reinforcement learning (MIRL). Compared to the well-known inverse reinforcement learning (IRL) problem, MIRL is formalized in the context of stochastic games, which generalize Markov decision processes to game theoretic scenarios. We establish a theoretical foundation for competitive two-agent zero-sum MIRL problems and propose a Bayesian solution approach in which the generative model is based on an assumption that the two agents follow a minimax bi-policy. Numerical results are presented comparing the Bayesian MIRL method with two existing methods in the context of an abstract soccer game. Investigation centers on relationships between the extent of prior information and the quality of learned rewards. Results suggest that covariance structure is more important than mean value in reward priors.
Computing the dimension of ideals in group algebras, with an application to coding theory
Venue: arXiv cs.IT 2019
Year: 2019

The problem of computing the dimension of a left/right ideal in a group algebra F[G] of a finite group G over a field F is considered. The ideal dimension is related to the rank of a matrix originating from a regular left/right representation of G; in particular, when F[G] is semisimple, the dimension of a principal ideal is equal to the rank of the matrix representing a generator. From this observation, a bound and an efficient algorithm to compute the dimension of an ideal in a group ring are established. Since group codes are ideals in finite group rings, the algorithm allows efficient computation of their dimension.
Structure of conflict graphs in constraint alignment problems and algorithms
Venue: arXiv cs.DS 2019
Year: 2019

We consider the constrained graph alignment problem which has applications in biological network analysis. Given two input graphs $G_1=(V_1,E_1), G_2=(V_2,E_2)$, a pair of vertex mappings induces an {\it edge conservation} if the vertex pairs are adjacent in their respective graphs. %In general terms The goal is to provide a one-to-one mapping between the vertices of the input graphs in order to maximize edge conservation. However the allowed mappings are restricted since each vertex from $V_1$ (resp. $V_2$) is allowed to be mapped to at most $m_1$ (resp. $m_2$) specified vertices in $V_2$ (resp. $V_1$). Most of results in this paper deal with the case $m_2=1$ which attracted most attention in the related literature. We formulate the problem as a maximum independent set problem in a related {\em conflict graph} and investigate structural properties of this graph in terms of forbidden subgraphs. We are interested, in particular, in excluding certain wheals, fans, cliques or claws (all terms are defined in the paper), which corresponds in excluding certain cycles, paths, cliques or independent sets in the neighborhood of each vertex. Then, we investigate algorithmic consequences of some of these properties, which illustrates the potential of this approach and raises new horizons for further works. In particular this approach allows us to reinterpret a known polynomial case in terms of conflict graph and to improve known approximation and fixed-parameter tractability results through efficiently solving the maximum independent set problem in conflict graphs. Some of our new approximation results involve approximation ratios that are function of the optimal value, in particular its square root; this kind of results cannot be achieved for maximum independent set in general graphs.
Regular Substitution Sets: A Means of Controlling E-Unification
Venue: arXiv cs.FL 2019
Year: 2019

A method for selecting solution constructors in narrowing is presented. The method is based on a sort discipline that describes regular sets of ground constructor terms as sorts. It is extended to cope with regular sets of ground substitutions, thus allowing different sorts to be computed for terms with different variable bindings. An algorithm for computing signatures of equationally defined functions is given that allows potentially infinite overloading. Applications to formal program development are sketched.
Projection Algorithms for Non-Convex Minimization with Application to Sparse Principal Component Analysis
Venue: arXiv cs.NA 2019
Year: 2019

We consider concave minimization problems over non-convex sets.Optimization problems with this structure arise in sparse principal component analysis. We analyze both a gradient projection algorithm and an approximate Newton algorithm where the Hessian approximation is a multiple of the identity. Convergence results are established. In numerical experiments arising in sparse principal component analysis, it is seen that the performance of the gradient projection algorithm is very similar to that of the truncated power method and the generalized power method. In some cases, the approximate Newton algorithm with a Barzilai-Borwein (BB) Hessian approximation can be substantially faster than the other algorithms, and can converge to a better solution.
On the Efficiency of Solving Boolean Polynomial Systems with the Characteristic Set Method
Venue: arXiv cs.SC 2019
Year: 2019

An improved characteristic set algorithm for solving Boolean polynomial systems is proposed. This algorithm is based on the idea of converting all the polynomials into monic ones by zero decomposition, and using additions to obtain pseudo-remainders. Three important techniques are applied in the algorithm. The first one is eliminating variables by new generated linear polynomials. The second one is optimizing the strategy of choosing polynomial for zero decomposition. The third one is to compute add-remainders to eliminate the leading variable of new generated monic polynomials. By analyzing the depth of the zero decomposition tree, we present some complexity bounds of this algorithm, which are lower than the complexity bounds of previous characteristic set algorithms. Extensive experimental results show that this new algorithm is more efficient than previous characteristic set algorithms for solving Boolean polynomial systems.
The Parameterized Complexity of k-Biclique
Venue: arXiv cs.CC 2019
Year: 2019

Given a graph $G$ and a parameter $k$, the $k$-biclique problem asks whether $G$ contains a complete bipartite subgraph $K_{k,k}$. This is the most easily stated problem on graphs whose parameterized complexity is still unknown. We provide an fpt-reduction from $k$-clique to $k$-biclique, thus solving this longstanding open problem. Our reduction use a class of bipartite graphs with a threshold property of independent interest. More specifically, for positive integers $n$, $s$ and $t$, we consider a bipartite graph $G=(A\;\dot\cup\;B, E)$ such that $A$ can be partitioned into $A=V_1\;\dot\cup \;V_2\;\dot\cup\cdots\dot\cup\; V_n$ and for every $s$ distinct indices $i_1\cdots i_s$, there exist $v_{i_1}\in V_{i_1}\cdots v_{i_s}\in V_{i_s}$ such that $v_{i_1}\cdots v_{i_s}$ have at least $t+1$ common neighbors in $B$; on the other hand, every $s+1$ distinct vertices in $A$ have at most $t$ common neighbors in $B$. Using the Paley-type graphs and Weil's character sum theorem, we show that for $t=(s+1)!$ and $n$ large enough, such threshold bipartite graphs can be computed in $n^{O(1)}$. One corollary of our reduction is that there is no $f(k)\cdot n^{o(k)}$ time algorithm to decide whether a graph contains a subgraph isomorphic to $K_{k!,k!}$ unless the ETH(Exponential Time Hypothesis) fails. We also provide a probabilistic construction with better parameters $t=Θ(s^2)$, which indicates that $k$-biclique has no $f(k)\cdot n^{o(\sqrt{k})}$-time algorithm unless 3-SAT with $m$ clauses can be solved in $2^{o(m)}$-time with high probability. Our result also implies the dichotomy classification of the parameterized complexity of cardinality constrain satisfaction problem and the inapproximability of maximum $k$-intersection problem.
Persistent Homology Over Directed Acyclic Graphs
Venue: arXiv cs.CG 2019
Year: 2019

We define persistent homology groups over any set of spaces which have inclusions defined so that the corresponding directed graph between the spaces is acyclic, as well as along any subgraph of this directed graph. This method simultaneously generalizes standard persistent homology, zigzag persistence and multidimensional persistence to arbitrary directed acyclic graphs, and it also allows the study of more general families of topological spaces or point-cloud data. We give an algorithm to compute the persistent homology groups simultaneously for all subgraphs which contain a single source and a single sink in $O(n^4)$ arithmetic operations, where $n$ is the number of vertices in the graph. We then demonstrate as an application of these tools a method to overlay two distinct filtrations of the same underlying space, which allows us to detect the most significant barcodes using considerably fewer points than standard persistence.
Higher Lower Bounds from the 3SUM Conjecture
Venue: arXiv cs.DS 2019
Year: 2019

The 3SUM conjecture has proven to be a valuable tool for proving conditional lower bounds on dynamic data structures and graph problems. This line of work was initiated by Pǎtraşcu (STOC 2010) who reduced 3SUM to an offline SetDisjointness problem. However, the reduction introduced by Pǎtraşcu suffers from several inefficiencies, making it difficult to obtain tight conditional lower bounds from the 3SUM conjecture. In this paper we address many of the deficiencies of Pǎtraşcu's framework. We give new and efficient reductions from 3SUM to offline SetDisjointness and offline SetIntersection (the reporting version of SetDisjointness) which leads to polynomially higher lower bounds on several problems. Using our reductions, we are able to show the essential optimality of several algorithms, assuming the 3SUM conjecture. - Chiba and Nishizeki's $O(mα)$-time algorithm (SICOMP 1985) for enumerating all triangles in a graph with arboricity/degeneracy $α$ is essentially optimal, for any $α$. - Bjørklund, Pagh, Williams, and Zwick's algorithm (ICALP 2014) for listing $t$ triangles is essentially optimal (assuming the matrix multiplication exponent is $ω=2$). - Any static data structure for SetDisjointness that answers queries in constant time must spend $Ω(N^{2-o(1)})$ time in preprocessing, where $N$ is the size of the set system. These statements were unattainable via Pǎtraşcu's reductions. We also introduce several new reductions from 3SUM to pattern matching problems and dynamic graph problems. Of particular interest are new conditional lower bounds for dynamic versions of Maximum Cardinality Matching, which introduce a new technique for obtaining amortized lower bounds.
Classification of the Z2Z4-linear Hadamard codes and their automorphism groups
Venue: arXiv cs.IT 2019
Year: 2019

A $Z_2Z_4$-linear Hadamard code of length $α+2β=2^t$ is a binary Hadamard code which is the Gray map image of a $Z_2Z_4$-additive code with $α$ binary coordinates and $β$ quaternary coordinates. It is known that there are exactly $[(t-1)/2]$ and $[t/2]$ nonequivalent $Z_2Z_4$-linear Hadamard codes of length $2^t$, with $α=0$ and $α\not=0$, respectively, for all $t\geq 3$. In this paper, it is shown that each $Z_2Z_4$-linear Hadamard code with $α=0$ is equivalent to a $Z_2Z_4$-linear Hadamard code with $α\not=0$; so there are only $[t/2]$ nonequivalent $Z_2Z_4$-linear Hadamard codes of length $2^t$. Moreover, the order of the monomial automorphism group for the $Z_2Z_4$-additive Hadamard codes and the permutation automorphism group of the corresponding $Z_2Z_4$-linear Hadamard codes are given.