Many proposed applications of neural networks in machine learning, cognitive/brain science, and society hinge on the feasibility of inner interpretability via circuit discovery. This calls for empirical and theoretical explorations of viable algorithmic options. Despite advances in the design and testing of heuristics, there are concerns about their scalability and faithfulness at a time when we lack understanding of the complexity properties of the problems they are deployed to solve. To address this, we study circuit discovery with classical and parameterized computational complexity theory: (1) we describe a conceptual scaffolding to reason about circuit finding queries in terms of affordances for description, explanation, prediction and control; (2) we formalize a comprehensive set of queries for mechanistic explanation, and propose a formal framework for their analysis; (3) we use it to settle the complexity of many query variants and relaxations of practical interest on multi-layer perceptrons. Our findings reveal a challenging complexity landscape. Many queries are intractable, remain fixed-parameter intractable relative to model/circuit features, and inapproximable under additive, multiplicative, and probabilistic approximation schemes. To navigate this landscape, we prove there exist transformations to tackle some of these hard problems with better-understood heuristics, and prove the tractability or fixed-parameter tractability of more modest queries which retain useful affordances. This framework allows us to understand the scope and limits of interpretability queries, explore viable options, and compare their resource demands on existing and future architectures.

Over the last 20 years, human interaction with robot swarms has been investigated as a means to mitigate problems associated with the control and coordination of such swarms by either human teleoperation or completely autonomous swarms. Ongoing research seeks to characterize those situations in which such interaction is both viable and preferable. In this article, we contribute to this effort by giving the first computational complexity analyses of problems associated with algorithm, environmental influence, and leader selection methods for the control of swarms performing distributed construction tasks. These analyses are done relative to a simple model in which swarms of deterministic finite-state robots operate in a synchronous error-free manner in 2D grid-based environments. We show that all three of our problems are polynomial-time intractable in general and remain intractable under a number of plausible restrictions (both individually and in many combinations) on robot controllers, environments, target structures, and sequences of swarm control commands. We also give the first restrictions relative to which these problems are tractable, as well as discussions of the implications of our results for both the design and deployment of swarm control assistance software tools and the human control of swarms.

Designing teams of autonomous robots that can create target structures or repair damage to those structures on either a one-off or ongoing basis is an important problem in distributed robotics. However, it is not known if a team design algorithm for any of these tasks can both have low runtime and produce teams that will always perform their specified tasks quickly and correctly. In this article, we give the first computational and parameterized complexity analyses of several robot team design problems associated with creating, repairing, and maintaining target structures in given environments. Our goals are to establish whether efficient design algorithms exist that operate reliably on all possible inputs and, if not, under which restrictions such algorithms are and are not possible. We prove that all of our design problems are not efficiently solvable in general for heterogeneous robot teams and remain so under a number of plausible restrictions on robot controllers, environments, and target structures. We also give the first restrictions relative to which some of these problems may be efficiently solvable and discuss how theoretical results like those derived here can be combined with physical experiments to derive the best possible algorithms for real-world robot team design.

A central problem in swarm robotics is to design a controller that will allow the member robots of the swarm to collectively perform a given task. Of particular interest in massively distributed applications are reactive controllers with severely limited computational and sensory abilities. In this article, we give the results of the first computational complexity analysis of the reactive swarm design problem. Our core results are derived relative to a generalization of what is arguably the simplest possible type of reactive controller, the so-called computation-free controller proposed by Gauci et al., which operates in grid-based environments in a noncontinuous manner. We show that the design of a generalized computation-free swarm for an arbitrary given task in an arbitrary given environment is not polynomial-time solvable either in general or by the most desirable types of approximation algorithms (including evolutionary algorithms with high probabilities of producing correct solutions) but is solvable in effectively polynomial time relative to several types of restrictions on swarms, environments, and tasks. All of our results hold for the design of several more complex types of generalized computation-free swarms. Moreover, all of our intractability and inapproximability results hold for the design of any type of reactive swarm (including those based on the popular feed-forward neural network and Brooks-style subsumption controllers) operating in grid-based environments in a noncontinuous manner whose member robots satisfy two simple conditions. As such, our results give the first theoretical survey of the types of efficient exact and approximate solution algorithms that are and are not possible for designing several types of reactive swarms.

The main purpose in influence maximization, which is motivated by the idea of viral marketing in social networks, is to find a subset of key users that maximize influence spread under a certain propagation model. A number of studies have been done over the past few years that try to solve this problem by considering a non-adversarial environment in which there exists only one player with no competitor. However, in real world scenarios, there is always more than one player competing with other players to influence the most nodes. This is called competitive influence maximization. Motivated by this, we try to solve the competitive influence maximization problem by proposing a new propagation model which is an extension of the Linear Threshold model and gives decision-making ability to nodes about incoming influence spread. We also propose an efficient algorithm for finding the influential nodes in a given social graph under the proposed propagation model which exploits the community structure of this graph to compute the spread of each node locally within its own community. The aim of our algorithm is to find the minimum number of seed nodes which can achieve higher spread in comparison with the spread achieved by nodes selected by other competitor. Our experiments on real world and synthetic datasets show that our approach can find influential nodes in an acceptable running time.

In cognitive science, natural cognitive processes are generally conceptualized as computational processes: they serve to transform sensory and mental inputs into mental and action outputs. At the highest level of abstraction, computational models of cognitive processes aim at specifying the computational problem computed by the process under study. Because computational problems are realistic cognitive models only insofar as they can plausibly be computed by the human brain given its limited resources for computation, computational tractability provides a useful constraint on cognitive models. In this paper, we consider the particular benefits of the parameterized complexity framework for identifying sources of intractability in cognitive models. We review existing applications of the parameterized framework to this end in the domains of perception, action and higher cognition. We further identify important opportunities and challenges for future research. These include the development of new methods for complexity analyses specifically tailored to the reverse engineering perspective underlying cognitive science.

Abstract Motivation: Reconstructing evolutionary trees is an important problem in biology. A response to the computational intractability of most of the traditional criteria for inferring evolutionary trees has been a focus on new criteria, particularly quartet-based methods that seek to merge trees derived on subsets of four species from a given species-set into a tree for that entire set. Unfortunately, most of these methods are very sensitive to errors in the reconstruction of the trees for individual quartets of species. A recently developed technique called quartet cleaning can alleviate this difficulty in certain cases by using redundant information in the complete set of quartet topologies for a given species-set to correct such errors. Results: In this paper, we describe two new local vertex quartet cleaning algorithms which have optimal time complexity and error-correction bound, respectively. These are the first known local vertex quartet cleaning algorithms that are optimal with respect to either of these attributes. Contact: [email protected]@cs.mun.ca * To whom correspondence should be addressed.

Many computational problems in biology involve parameters for which a small range of values cover important applications. We argue that for many problems in this setting, parameterized computational complexity rather than NP-completeness is the appropriate tool for studying apparent intractability. At issue in the theory of parameterized complexity is whether a problem can be solved in time O(n alpha) for each fixed parameter value, where alpha is a constant independent of the parameter. In addition to surveying this complexity framework, we describe a new result for the Longest Common Subsequence problem. In particular, we show that the problem is hard for W[t] for all t when parameterized by the number of strings and the size of the alphabet. Lower bounds on the complexity of this basic combinatorial problem imply lower bounds on more general sequence alignment and consensus discovery problems. We also describe a number of open problems pertaining to the parameterized complexity of problems in computational biology where small parameter values are important.