Daniel J. Rosenkrantz

AAMAS Conference 2025 Conference Paper

On Some Fundamental Problems for Multi-Agent Systems Over Multilayer Networks

• Daniel J. Rosenkrantz
• Madhav V. Marathe
• Zirou Qiu
• S. S. Ravi
• Richard E. Stearns

Many researchers have considered multi-agent systems over singlelayer networks as models for studying diffusion phenomena. Since real-world networks involve connections between agents with different semantics (e. g. , family member, friend, colleague), the study of multi-agent systems over multilayer networks has assumed increased importance. Our focus is on one class of multi-agent system models over multilayer networks, namely multilayer synchronous dynamical systems (MSyDSs). We study several fundamental problems for this model. We establish properties of the phase spaces of MSyDSs and bring out interesting differences between single-layer and multilayer dynamical systems. We show that, in general, the problem of determining whether two given MSyDSs are inequivalent is NP-complete. This hardness result holds even when the only difference between the two systems is the local function at just one node in one layer. We also present efficient algorithms for the equivalence problem for restricted versions of MSyDSs (e. g. , systems where each local function is a bounded-threshold function, and systems where the number of layers is fixed and each local function is symmetric). In addition, we investigate the expressive power of MSyDSs based on the number of layers. In particular, we examine conditions under which a system with 𝑘 ≥ 2 layers has an equivalent system with 𝑘 − 1 or fewer layers.

TCS Journal 2025 Journal Article

Theoretical foundations for parent divorcing transformations in Bayesian networks

• Daniel J. Rosenkrantz
• Madhav V. Marathe
• Zirou Qiu
• S.S. Ravi

Parent divorcing is a commonly used technique to reduce the complexity of Bayesian models. In particular, this transformation decreases the number of parents of some nodes in a given Bayesian Network (BN). Such transformations must be done in such a way that solutions to inference problems for the original BN can be readily obtained from the solutions to the new BN. Despite its wide use in practice, there have been no attempts to formally analyze these transformations. In this work, we present a first step towards the development of theoretical foundations for the use of divorce transformations in BNs and establish analytical results. Specifically, we develop a formalism that captures a structural relationship between the original BN and the new BN. Using this formalism, we present an algorithm for parent divorcing which ensures that the treewidth of the modified BN is within a constant factor of that of the original BN. We also present an algorithm that carries out parent divorcing while preserving the domain size of each node. Further, we present lower bound results to prove that there are BNs for which parent divorcing transformations can cause an exponential increase in the domain size or lead to an exponentially large new BN.

ICML Conference 2024 Conference Paper

Efficient PAC Learnability of Dynamical Systems Over Multilayer Networks

• Zirou Qiu
• Abhijin Adiga
• Madhav V. Marathe
• S. S. Ravi
• Daniel J. Rosenkrantz
• Richard Edwin Stearns
• V. S. Anil Kumar 0001

Networked dynamical systems are widely used as formal models of real-world cascading phenomena, such as the spread of diseases and information. Prior research has addressed the problem of learning the behavior of an unknown dynamical system when the underlying network has a single layer. In this work, we study the learnability of dynamical systems over multilayer networks, which are more realistic and challenging. First, we present an efficient PAC learning algorithm with provable guarantees to show that the learner only requires a small number of training examples to infer an unknown system. We further provide a tight analysis of the Natarajan dimension which measures the model complexity. Asymptotically, our bound on the Nararajan dimension is tight for almost all multilayer graphs. The techniques and insights from our work provide the theoretical foundations for future investigations of learning problems for multilayer dynamical systems.

AAAI Conference 2024 Conference Paper

Learning the Topology and Behavior of Discrete Dynamical Systems

• Zirou Qiu
• Abhijin Adiga
• Madhav V. Marathe
• S. S. Ravi
• Daniel J. Rosenkrantz
• Richard E. Stearns
• Anil Vullikanti

Discrete dynamical systems are commonly used to model the spread of contagions on real-world networks. Under the PAC framework, existing research has studied the problem of learning the behavior of a system, assuming that the underlying network is known. In this work, we focus on a more challenging setting: to learn both the behavior and the underlying topology of a black-box system. We show that, in general, this learning problem is computationally intractable. On the positive side, we present efficient learning methods under the PAC model when the underlying graph of the dynamical system belongs to certain classes. Further, we examine a relaxed setting where the topology of an unknown system is partially observed. For this case, we develop an efficient PAC learner to infer the system and establish the sample complexity. Lastly, we present a formal analysis of the expressive power of the hypothesis class of dynamical systems where both the topology and behavior are unknown, using the well-known Natarajan dimension formalism. Our results provide a theoretical foundation for learning both the topology and behavior of discrete dynamical systems.

AAMAS Conference 2023 Conference Paper

Assigning Agents to Increase Network-Based Neighborhood Diversity

• Zirou Qiu
• Andrew Yuan
• Chen Chen
• Madhav V. Marathe
• S. S. Ravi
• Daniel J. Rosenkrantz
• Richard E. Stearns
• Anil Vullikanti

Motivated by real-world applications such as the allocation of public housing, we examine the problem of assigning a group of agents to vertices (e. g. , spatial locations) of a network so that the diversity level is maximized. Specifically, agents are of two types (characterized by features), and we measure diversity by the number of agents who have at least one neighbor of a different type. This problem is known to be NP-hard, and we focus on developing approximation algorithms with provable performance guarantees. We first present a local-improvement algorithm for general graphs that provides an approximation factor of 1⇑2. For the special case where the sizes of agent subgroups are similar, we present a randomized approach based on semidefinite programming that yields an approximation factor better than 1⇑2. Further, we show that the problem can be solved efficiently when the underlying graph is treewidth-bounded and obtain a polynomial time approximation scheme (PTAS) for the problem on planar graphs. Lastly, we conduct experiments to evaluate the performance of the proposed algorithms on synthetic and real-world networks.

AAAI Conference 2023 Conference Paper

Networked Anti-coordination Games Meet Graphical Dynamical Systems: Equilibria and Convergence

• Zirou Qiu
• Chen Chen
• Madhav V. Marathe
• S. S. Ravi
• Daniel J. Rosenkrantz
• Richard E. Stearns
• Anil Vullikanti

Evolutionary anti-coordination games on networks capture real-world strategic situations such as traffic routing and market competition. Two key problems concerning evolutionary games are the existence of a pure Nash equilibrium (NE) and the convergence time. In this work, we study these two problems for anti-coordination games under sequential and synchronous update schemes. For each update scheme, we examine two decision modes based on whether an agent considers its own previous action (self essential) or not (self non-essential) in choosing its next action. Using a relationship between games and dynamical systems, we show that for both update schemes, finding an NE can be done efficiently under the self non-essential mode but is computationally intractable under the self essential mode. We then identify special cases for which an NE can be obtained efficiently. For convergence time, we show that the dynamics converges in a polynomial number of steps under the synchronous scheme; for the sequential scheme, the convergence time is polynomial only under the self non-essential mode. Through experiments, we empirically examine the convergence time and the equilibria for both synthetic and real-world networks.

AAAI Conference 2023 Conference Paper

Resource Sharing through Multi-Round Matchings

• Yohai Trabelsi
• Abhijin Adiga
• Sarit Kraus
• S. S. Ravi
• Daniel J. Rosenkrantz

Applications such as employees sharing office spaces over a workweek can be modeled as problems where agents are matched to resources over multiple rounds. Agents' requirements limit the set of compatible resources and the rounds in which they want to be matched. Viewing such an application as a multi-round matching problem on a bipartite compatibility graph between agents and resources, we show that a solution (i.e., a set of matchings, with one matching per round) can be found efficiently if one exists. To cope with situations where a solution does not exist, we consider two extensions. In the first extension, a benefit function is defined for each agent and the objective is to find a multi-round matching to maximize the total benefit. For a general class of benefit functions satisfying certain properties (including diminishing returns), we show that this multi-round matching problem is efficiently solvable. This class includes utilitarian and Rawlsian welfare functions. For another benefit function, we show that the maximization problem is NP-hard. In the second extension, the objective is to generate advice to each agent (i.e., a subset of requirements to be relaxed) subject to a budget constraint so that the agent can be matched. We show that this budget-constrained advice generation problem is NP-hard. For this problem, we develop an integer linear programming formulation as well as a heuristic based on local search. We experimentally evaluate our algorithms on synthetic networks and apply them to two real-world situations: shared office spaces and matching courses to classrooms.

ICML Conference 2022 Conference Paper

Efficiently Learning the Topology and Behavior of a Networked Dynamical System Via Active Queries

• Daniel J. Rosenkrantz
• Abhijin Adiga
• Madhav V. Marathe
• Zirou Qiu
• S. S. Ravi
• Richard Edwin Stearns
• V. S. Anil Kumar 0001

Using a discrete dynamical system model, many papers have addressed the problem of learning the behavior (i. e. , the local function at each node) of a networked system through active queries, assuming that the network topology is known. We address the problem of inferring both the topology of the network and the behavior of a discrete dynamical system through active queries. We consider two query models studied in the literature, namely the batch model (where all the queries must be submitted together) and the adaptive model (where responses to previous queries can be used in formulating a new query). Our results are for systems where the state of each node is from {0, 1} and the local functions are Boolean. We present algorithms to learn the topology and the behavior under both batch and adaptive query models for several classes of dynamical systems. These algorithms use only a polynomial number of queries. We also present experimental results obtained by running our query generation algorithms on synthetic and real-world networks.

AAAI Conference 2022 Conference Paper

Finding Nontrivial Minimum Fixed Points in Discrete Dynamical Systems: Complexity, Special Case Algorithms and Heuristics

• Zirou Qiu
• Chen Chen
• Madhav Marathe
• S.S. Ravi
• Daniel J. Rosenkrantz
• Richard Stearns
• Anil Vullikanti

Networked discrete dynamical systems are often used to model the spread of contagions and decision-making by agents in coordination games. Fixed points of such dynamical systems represent configurations to which the system converges. In the dissemination of undesirable contagions (such as rumors and misinformation), convergence to fixed points with a small number of affected nodes is a desirable goal. Motivated by such considerations, we formulate a novel optimization problem of finding a nontrivial fixed point of the system with the minimum number of affected nodes. We establish that, unless P = NP, there is no polynomial time algorithm for approximating a solution to this problem to within the factor n1−ϵ for any constant ϵ > 0. To cope with this computational intractability, we identify several special cases for which the problem can be solved efficiently. Further, we introduce an integer linear program to address the problem for networks of reasonable sizes. For solving the problem on larger networks, we propose a general heuristic framework along with greedy selection methods. Extensive experimental results on real-world networks demonstrate the effectiveness of the proposed heuristics. A full version of the manuscript, source code and data are available at: https: //github. com/bridgelessqiu/NMIN-FPE

JMLR Journal 2022 Journal Article

Using Active Queries to Infer Symmetric Node Functions of Graph Dynamical Systems

• Abhijin Adiga
• Chris J. Kuhlman
• Madhav V. Marathe
• S. S. Ravi
• Daniel J. Rosenkrantz
• Richard E. Stearns

Developing techniques to infer the behavior of networked social systems has attracted a lot of attention in the literature. Using a discrete dynamical system to model a networked social system, the problem of inferring the behavior of the system can be formulated as the problem of learning the local functions of the dynamical system. We investigate the problem assuming an active form of interaction with the system through queries. We consider two classes of local functions (namely, symmetric and threshold functions) and two interaction modes, namely batch (where all the queries must be submitted together) and adaptive (where the set of queries submitted at a stage may rely on the answers to previous queries). We establish bounds on the number of queries under both batch and adaptive query modes using vertex coloring and probabilistic methods. Our results show that a small number of appropriately chosen queries are provably sufficient to correctly learn all the local functions. We develop complexity results which suggest that, in general, the problem of generating query sets of minimum size is computationally intractable. We present efficient heuristics that produce query sets under both batch and adaptive query modes. Also, we present a query compaction algorithm that identifies and removes redundant queries from a given query set. Our algorithms were evaluated through experiments on over 20 well-known networks. [abs] [ pdf ][ bib ] &copy JMLR 2022. ( edit, beta )

AAAI Conference 2021 Conference Paper

Synchronous Dynamical Systems on Directed Acyclic Graphs: Complexity and Algorithms

• Daniel J. Rosenkrantz
• Madhav Marathe
• S. S. Ravi
• Richard E. Stearns

Discrete dynamical systems serve as useful formal models to study diffusion phenomena in social networks. Motivated by applications in systems biology, several recent papers have studied algorithmic and complexity aspects of diffusion problems for dynamical systems whose underlying graphs are directed, and may contain directed cycles. Such problems can be regarded as reachability problems in the phase space of the corresponding dynamical system. We show that computational intractability results for reachability problems hold even for dynamical systems on directed acyclic graphs (dags). We also show that for dynamical systems on dags where each local function is monotone, the reachability problem can be solved efficiently.

AAMAS Conference 2018 Conference Paper

Testing Phase Space Properties of Synchronous Dynamical Systems with Nested Canalyzing Local Functions

• Daniel J. Rosenkrantz
• Madhav V. Marathe
• S. S. Ravi
• Richard E. Stearns

Discrete graphical dynamical systems serve as effective formal models for simulations of agent-based models, propagation of contagions in social networks and study of biological phenomena. A class of Boolean functions, called nested canalyzing functions (NCFs), has been used as a good model of certain biological phenomena. Motivated by these biological applications, we study a variety of analysis problems for synchronous graphical dynamical systems (SyDSs) over the Boolean domain, where each local function is an NCF. We present intractability results for some properties as well as efficient algorithms for others. In several cases, our results clearly delineate intractable and efficiently solvable versions of problems.

TCS Journal 2017 Journal Article

Inferring local transition functions of discrete dynamical systems from observations of system behavior

• Abhijin Adiga
• Chris J. Kuhlman
• Madhav V. Marathe
• S.S. Ravi
• Daniel J. Rosenkrantz
• Richard E. Stearns

We consider the problem of inferring the local transition functions of discrete dynamical systems from observed behavior. Our focus is on synchronous systems whose local transition functions are threshold functions. We assume that the topology of the system is known and that the goal is to infer a threshold value for each node so that the system produces the observed behavior. We show that some of these inference problems are efficiently solvable while others are NP-complete, even when the underlying graph of the dynamical system is a simple path. We identify a fixed parameter tractable problem in this context. We also consider constrained versions of threshold inference problems where the input includes a set of equality or inequality constraints (which specify pairs of nodes which must have the same threshold value or different threshold values). We present algorithmic and complexity results for several constrained threshold inference problems.

UAI Conference 2014 Conference Paper

Bayesian Inference in Treewidth-Bounded Graphical Models Without Indegree Constraints

• Daniel J. Rosenkrantz
• Madhav V. Marathe
• Ravi Sundaram
• V. S. Anil Kumar 0001

We present new polynomial time algorithms for inference problems in Bayesian networks (BNs) when restricted to instances that satisfy the following two conditions: they have bounded treewidth and the conditional probability table (CPT) at each node is specified concisely using an r-symmetric function for some constant r. Our polynomial time algorithms work directly on the unmoralized graph. Our results significantly extend known results regarding inference problems on treewidth bounded BNs to a larger class of problem instances. We also show that relaxing either of the conditions used by our algorithms leads to computational intractability.

TCS Journal 2011 Journal Article

Modeling and analyzing social network dynamics using stochastic discrete graphical dynamical systems

• Chris Barrett
• Harry B. Hunt
• Madhav V. Marathe
• S.S. Ravi
• Daniel J. Rosenkrantz
• Richard E. Stearns

Motivated by applications such as the spread of epidemics and the propagation of influence in social networks, we propose a formal model for analyzing the dynamics of such networks. Our model is a stochastic version of discrete graphical dynamical systems. Using this model, we formulate and study the computational complexity of two fundamental problems (called reachability and predecessor existence problems) which arise in the context of social networks. We also address other problems that deal with the time evolution of such stochastic dynamical systems. Further, we point out the implications of our results to problems for other computational models such as Hopfield networks, communicating finite state machines and systolic arrays. In particular, our polynomial time algorithms for the predecessor existence problem for stochastic dynamical systems imply similar results for one-dimensional finite cellular automata.

TCS Journal 2008 Journal Article

Errata for the paper “Predecessor existence problems for finite discrete dynamical systems” [Theoret. Comput. Sci. 386 (1–2) (2007) 3–37]

• Chris Barrett
• Harry B. Hunt
• Madhav V. Marathe
• S.S. Ravi
• Daniel J. Rosenkrantz
• Richard E. Stearns
• Mayur Thakur

TCS Journal 2007 Journal Article

Predecessor existence problems for finite discrete dynamical systems

• Chris Barrett
• Harry B. Hunt
• Madhav V. Marathe
• S.S. Ravi
• Daniel J. Rosenkrantz
• Richard E. Stearns
• Mayur Thakur

We study the predecessor existence problem for finite discrete dynamical systems. Given a finite discrete dynamical system S and a configuration C, the Predecessor existence (or Pre) problem is to determine whether there is a configuration C ′ such that S has a transition from C ′ to C. In addition to the decision version, we also study the following variants: the #-Predecessor existence (or #Pre) problem–counting the number of predecessors, the Unique-Predecessor existence (or UPre) problem–deciding whether there is a unique predecessor and the Ambiguous-Predecessor existence (or APre) problem–given a configuration C and a predecessor C ′ of C, deciding whether there is a different predecessor C ″ of C. General techniques are presented for simultaneously characterizing the computational complexity of the Pre problem and its three variants. Our hardness results are based on the concept of simultaneous reductions: single transformations that can be used to simultaneously prove the hardness of the different variants of the Pre problem for their respective complexity classes. Our easiness results are based on dynamic programming and they extend the previous results on Pre problem for one-dimensional cellular automata. The hardness results together with the easiness results provide a tight separation between easy and hard instances. Further, the results imply similar bounds for other classes of finite discrete dynamical systems including discrete Hopfield and recurrent neural networks, concurrent state machines, systolic networks and one- and two-dimensional cellular automata. Our results extend the earlier results of Green, Sutner and Orponen on the complexity of the predecessor existence problem and its variants.

TCS Journal 2003 Journal Article

Reachability problems for sequential dynamical systems with threshold functions

• Chris Barrett
• Harry B. Hunt III
• Madhav V. Marathe
• S.S. Ravi
• Daniel J. Rosenkrantz
• Richard E. Stearns

A sequential dynamical system (SDS) over a domain D is a triple (G, F, π), where (i) G(V, E) is an undirected graph with n nodes with each node having a state value from D, (ii) F={f1, f2, …, fn} is a set of local transition functions with f i denoting the local transition function associated with node v i and (iii) π is a permutation of (i. e. , a total order on) the nodes in V. A single SDS transition is obtained by updating the states of the nodes in V by evaluating the function associated with each of them in the order given by π. We consider reachability problems for SDSs with restricted local transition functions. Our main intractability results show that the reachability problems for SDSs are PSPACE-complete when either of the following restrictions hold: (i) F consists of both simple-threshold-functions and simple-inverted-threshold functions, or (ii) F consists only of threshold-functions that use weights in an asymmetric manner. Moreover, the results hold even for SDSs whose underlying graphs have bounded node degree and bounded pathwidth. Our lower bound results also extend to reachability problems for Hopfield networks and communicating finite state machines. On the positive side, we show that when F consists only of threshold functions that use weights in a symmetric manner, reachability problems can be solved efficiently provided all the weights are strictly positive and the ratio of the largest to the smallest weight is bounded by a polynomial function of the number of nodes.

MFCS Conference 2001 Conference Paper

Analysis Problems for Sequential Dynamical Systems and Communicating State Machines

• Christopher L. Barrett
• Harry B. Hunt III
• Madhav V. Marathe
• S. S. Ravi
• Daniel J. Rosenkrantz
• Richard Edwin Stearns

Abstract Informally, a sequential dynamical system (SDS) consists of an undirected graph where each node v is associated with a state s v and a transition function f v. Given the state value s v and those of the neighbors of v, the function f v computes the next value of s v. The node transition functions are evaluated according to a specified total order. Such a computing device is a mathematical abstraction of a simulation system. We address the complexity of some state reachability problems for SDSs. Our main result is a dichotomy between classes of SDSs for which the state reachability problems are computationally intractable and those for which the problems are efficiently solvable. These results also allow us to obtain stronger lower bounds on the complexity of reachability problems for cellular automata and communicating state machines.

TCS Journal 2000 Journal Article

Alarm placement in systems with fault propagation

• K.B. Lakshmanan
• Daniel J. Rosenkrantz
• S.S. Ravi

In this paper, we consider systems that can be modeled as directed acyclic graphs such that nodes represent components of the system and directed edges represent fault propagation between components. Some components can be equipped with alarms that ring when they detect faulty (abnormal) behavior. We study algorithms that attempt to minimize the number of alarms to be placed so that a fault at any single component can be detected and uniquely diagnosed. We first show that the minimization problem is intractable, i. e. , NP-hard, even when restricted to three level graphs in which all nodes have outdegree two or less. We present optimal algorithms for three special classes of graphs – tree structured graphs, single-entry single-exit series–parallel graphs and two level graphs. We then present a polynomial-time approximation algorithm for the general case which guarantees that the ratio of the number of alarms placed to the optimum required is within a factor that is logarithmic in the number of nodes in the graph. Moreover, by showing a reduction from the minimum dominating set problem to the minimum alarm set problem, we argue that this performance guarantee is tight to within a constant factor. Finally, we demonstrate the connection between the minimum alarm set problem and the minimum test collection problem, and prove similar results.

SODA Conference 1994 Conference Paper

Spanning Trees Short or Small

• R. Ravi 0001
• Ravi Sundaram
• Madhav V. Marathe
• Daniel J. Rosenkrantz
• S. S. Ravi

STOC Conference 1993 Conference Paper

Many birds with one stone: multi-objective approximation algorithms

• R. Ravi 0001
• Madhav V. Marathe
• S. S. Ravi
• Daniel J. Rosenkrantz
• Harry B. Hunt III

FOCS Conference 1980 Conference Paper

The Complexity of Recursion Schemes and Recursive Programming Languages (Extended Abstract)

• Harry B. Hunt III
• Daniel J. Rosenkrantz

Deterministic exponential lower time bounds are obtained for analyzing monadic recursion schemes, multi-variable recursion schemes, and recursive programs. The lower bound for multivariable recursion schemes holds for any domain of interpretation with at least two elements. The lower bound for recursive programs holds for any recursive programming language with a nontrivial predicate test (i. e. a predicate test that is neither identically true nor identically false). Exponential lower bounds on depth of nesting of recursive function calls play an important role in the proofs of these bounds. In contrast, polynomial upper bounds on depth of nesting are obtained for total and linear monadic recursion schemes. As corollaries, several decision problems for these scheme classes are shown to have nondeterministic polynomially time-bounded algorithms.

FOCS Conference 1976 Conference Paper

Concurrency Control for Database Systems

• Richard Edwin Stearns
• Philip M. Lewis II
• Daniel J. Rosenkrantz

STOC Conference 1974 Conference Paper

Computational Parallels between the Regular and Context-Free Languages

• Harry B. Hunt III
• Daniel J. Rosenkrantz

STOC Conference 1973 Conference Paper

Attributed Translations

• Philip M. Lewis II
• Daniel J. Rosenkrantz
• Richard Edwin Stearns

STOC Conference 1969 Conference Paper

Properties of Deterministic Top Down Grammars

• Daniel J. Rosenkrantz
• Richard Edwin Stearns

The class of context free grammars that can be deterministically parsed in a top down manner with a fixed amount of look-ahead is investigated. These grammars, called LL(k) grammars where k is the amount of look-ahead are first defined and a procedure is given for determining if a context free grammar is LL(k) for a given value of k. It is shown that ε-rules can be eliminated from an LL(k) grammar, at the cost of increasing the value of k by one, and a description is given of a canonical pushdown machine for recognizing LL(k) languages. It is shown that for each value of k there are LL(k+l) languages that are not LL(k) languages. It is shown that the equivalence problem is decidable for LL(k) grammars. Additional properties are also given.