Richard E. Stearns

Theory Comput. Syst., October, 2024

Synchronous Dynamical Systems on Directed Acyclic Graphs: Complexity and Algorithms.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2024

Efficient PAC Learnability of Dynamical Systems Over Multilayer Networks.

[BibT_eX]

[DOI]

Anil Kumar S. Vullikanti

Proceedings of the Forty-first International Conference on Machine Learning, 2024

Learning the Topology and Behavior of Discrete Dynamical Systems.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence, 2024

2023

Finding Nontrivial Minimum Fixed Points in Discrete Dynamical Systems.

[BibT_eX]

[DOI]

CoRR, 2023

Assigning Agents to Increase Network-Based Neighborhood Diversity.

[BibT_eX]

[DOI]

Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, 2023

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

[BibT_eX]

[DOI]

Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence, 2023

2022

Fundamental limitations on efficiently forecasting certain epidemic measures in network models.

[BibT_eX]

[DOI]

Simon A. Levin

H. Vincent Poor

Proc. Natl. Acad. Sci. USA, 2022

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

[BibT_eX]

[DOI]

J. Mach. Learn. Res., 2022

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

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2022

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

[BibT_eX]

[DOI]

Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, 2022

2020

Evolution of Similar Configurations in Graph Dynamical Systems.

[BibT_eX]

[DOI]

Joshua D. Priest

Proceedings of the Complex Networks & Their Applications IX, 2020

Bounds and Complexity Results for Learning Coalition-Based Interaction Functions in Networked Social Systems.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, 2020

2019

Symmetry Properties of Nested Canalyzing Functions.

[BibT_eX]

[DOI]

Discret. Math. Theor. Comput. Sci., 2019

Validating Agent-Based Models of Large Networked Systems.

[BibT_eX]

[DOI]

Abhijin Adiga

Samarth Swarup

Proceedings of the 2019 Winter Simulation Conference, 2019

2018

A characterization of nested canalyzing functions with maximum average sensitivity.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2018

Computational Aspects of Fault Location and Resilience Problems for Interdependent Infrastructure Networks.

[BibT_eX]

[DOI]

Proceedings of the Complex Networks and Their Applications VII, 2018

Using Active Queries to Learn Local Stochastic Behaviors in Social Networks.

[BibT_eX]

[DOI]

Proceedings of the Complex Networks and Their Applications VII, 2018

Inferring Probabilistic Contagion Models Over Networks Using Active Queries.

[BibT_eX]

[DOI]

Abhijin Adiga

Vanessa Cedeno-Mieles

Chris J. Kuhlman

Proceedings of the 27th ACM International Conference on Information and Knowledge Management, 2018

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

[BibT_eX]

[DOI]

Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, 2018

Learning the Behavior of a Dynamical System Via a "20 Questions" Approach.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, 2018

2017

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

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2017

2015

Complexity of Inferring Local Transition Functions of Discrete Dynamical Systems.

[BibT_eX]

[DOI]

Proceedings of the Implementation and Application of Automata, 2015

Analysis Problems for Graphical Dynamical Systems: A Unified Approach Through Graph Predicates.

[BibT_eX]

[DOI]

Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, 2015

2013

Sums-of-Products and Subproblem Independence.

[BibT_eX]

[DOI]

Proceedings of the Fundamental Problems in Computing, 2013

2012

The Turing Computational Model.

[BibT_eX]

[DOI]

Stephen Cook

William Kahan

Andrew C. Yao

Proceedings of the ACM Turing Centenary Celebration, 2012

2011

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

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2011

2008

Errata for the paper "Predecessor existence problems for finite discrete dynamical systems" [TCS 386 (1-2) (2007) 3-37].

[BibT_eX]

[DOI]

Mayur Thakur

Theor. Comput. Sci., 2008

2007

Predecessor existence problems for finite discrete dynamical systems.

[BibT_eX]

[DOI]

Mayur Thakur

Theor. Comput. Sci., 2007

Computational Aspects of Analyzing Social Network Dynamics.

[BibT_eX]

[DOI]

Mayur Thakur

Proceedings of the IJCAI 2007, 2007

2006

Complexity of reachability problems for finite discrete dynamical systems.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2006

Towards a Predictive Computational Complexity Theory.

[BibT_eX]

Proceedings of the Computational Complexity and Statistical Physics., 2006

2005

Resource Bounds and Subproblem Independence.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2005

Mechanism design for software agents with complete information.

[BibT_eX]

[DOI]

Thomas C. O'Connell

Decis. Support Syst., 2005

2003

Reachability problems for sequential dynamical systems with threshold functions.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2003

Deterministic versus nondeterministic time and lower bound problems.

[BibT_eX]

[DOI]

J. ACM, 2003

On finite strategy sets for finitely repeated zero-sum games.

[BibT_eX]

[DOI]

Thomas C. O'Connell

Games Econ. Behav., 2003

Predecessor and Permutation Existence Problems for Sequential Dynamical Systems.

[BibT_eX]

[DOI]

Proceedings of the Discrete Models for Complex Systems, 2003

2002

Exploiting structure in quantified formulas.

[BibT_eX]

[DOI]

J. Algorithms, 2002

Parallel Approximation Schemes for a Class of Planar and Near Planar Combinatorial Optimization Problems.

[BibT_eX]

[DOI]

Inf. Comput., 2002

2001

Complexity and Approximability of Quantified and Stochastic Constraint Satisfaction Problems.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2001

Analysis Problems for Sequential Dynamical Systems and Communicating State Machines.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2001, 2001

Strongly-local reductions and the complexity/efficient approximability of algebra and optimization on abstract algebraic structures.

[BibT_eX]

[DOI]

Proceedings of the 2001 International Symposium on Symbolic and Algebraic Computation, 2001

Gardens of Eden and Fixed Points in Sequential Dynamical Systems.

[BibT_eX]

[DOI]

Predrag T. Tosic

Proceedings of the Discrete Models: Combinatorics, Computation, and Geometry, 2001

1998

Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 1998

The Complexity of Planar Counting Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 1998

NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs.

[BibT_eX]

[DOI]

J. Algorithms, 1998

Theory of Periodically Specified Problems: Complexity and Approximability.

[BibT_eX]

[DOI]

Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

1996

An Algebraic Model for Combinatorial Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 1996

I/O Automata Based Verification of Finite State Distributed Systems: Complexity Issues (Abstract).

[BibT_eX]

[DOI]

Sandeep K. Shukla

Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, 1996

On the Complexity of Relational Problems for Finite State Processes (Extended Abstract).

[BibT_eX]

[DOI]

Sandeep K. Shukla

Proceedings of the Automata, Languages and Programming, 23rd International Colloquium, 1996

The polynomial time decidability of simulation relations for finite processes: A HORNSAT based approach.

[BibT_eX]

[DOI]

Sandeep K. Shukla

Proceedings of the Satisfiability Problem: Theory and Applications, 1996

Complexity of hierarchically and 1-dimensional periodically specified problems I: Hardness results.

[BibT_eX]

[DOI]

Proceedings of the Satisfiability Problem: Theory and Applications, 1996

1995

Refined Single-Threading for Parallel Functional Programming.

[BibT_eX]

[DOI]

George Becker

Neil V. Murray

Proceedings of the Languages, 1995

1994

Turing Award Lecture: It's Time to Reconsider Time.

[BibT_eX]

[DOI]

Commun. ACM, 1994

Approximation schemes for PSPACE-complete problems for succinct specifications (preliminary version).

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Approximation Schemes Using L-Reductions.

[BibT_eX]

[DOI]

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1994

A Unified Approach to Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 1994

Generalized CNF Satisfiability Problems and Non-Efficient.

[BibT_eX]

[DOI]

Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

1992

Efficient Algorithms for Solving Systems of Linear Equations and Path Problems.

[BibT_eX]

[DOI]

Proceedings of the STACS 92, 1992

1990

The Complexity of Very Simple Boolean Formulas with Applications.

[BibT_eX]

[DOI]

SIAM J. Comput., 1990

Power Indices and Easier Hard Problems.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1990

The Complexity of Equivalence for Commutative Rings.

[BibT_eX]

[DOI]

J. Symb. Comput., 1990

1988

Juris Hartmanis: the beginnings of computational complexity.

[BibT_eX]

[DOI]

Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

On the Complexity of Satisfiability Problems for Algebraic Structures (Preliminary Report).

[BibT_eX]

[DOI]

Proceedings of the Applied Algebra, 1988

1987

Nonlinear Algebra and Optimization on Rings are "Hard".

[BibT_eX]

[DOI]

SIAM J. Comput., 1987

1986

Monotone Boolean Formulas, Distributive Lattices, and the Complexities of Logics, Algebraic Structures, and Computation Structures (Preliminary Report).

[BibT_eX]

[DOI]

Proceedings of the STACS 86, 1986

1985

On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata.

[BibT_eX]

[DOI]

SIAM J. Comput., 1985

1984

Consistency and Serializability in Concurrent Database Systems.

[BibT_eX]

[DOI]

SIAM J. Comput., 1984

1981

Distributed Database Concurrency Controls Using Before-Values.

[BibT_eX]

[DOI]

Proceedings of the 1981 ACM SIGMOD International Conference on Management of Data, Ann Arbor, Michigan, USA, April 29, 1981

On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Grammars, and Automata

[BibT_eX]

[DOI]

Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

1978

System Level Concurrency Control for Distributed Database Systems.

[BibT_eX]

[DOI]

ACM Trans. Database Syst., 1978

1977

An Analysis of Several Heuristics for the Traveling Salesman Problem.

[BibT_eX]

[DOI]

SIAM J. Comput., 1977

1976

Concurrency Control for Database Systems

[BibT_eX]

[DOI]

Proceedings of the 17th Annual Symposium on Foundations of Computer Science, 1976

1974

Attributed Translations.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1974

Approximate Algorithms for the Traveling Salesperson Problem

[BibT_eX]

[DOI]

Proceedings of the 15th Annual Symposium on Switching and Automata Theory, 1974

1970

Properties of Deterministic Top-Down Grammars

[BibT_eX]

[DOI]

Inf. Control., October, 1970

1969

Property Grammars and Table Machines

[BibT_eX]

[DOI]

Inf. Control., June, 1969

Automata-based computational complexity.

[BibT_eX]

[DOI]

Inf. Sci., 1969

Table Machine Simulation

[BibT_eX]

[DOI]

Proceedings of the 10th Annual Symposium on Switching and Automata Theory, 1969

1968

Syntax-Directed Transduction.

[BibT_eX]

[DOI]

J. ACM, 1968

1967

A Regularity Test for Pushdown Machines

[BibT_eX]

[DOI]

Inf. Control., September, 1967

1966

Two-Tape Simulation of Multitape Turing Machines.

[BibT_eX]

[DOI]

F. C. Hennie

J. ACM, 1966

1965

Hierarchies of memory limited computations

[BibT_eX]

[DOI]

Proceedings of the 6th Annual Symposium on Switching Circuit Theory and Logical Design, 1965

Memory bounds for recognition of context-free and context-sensitive languages

[BibT_eX]

[DOI]

Proceedings of the 6th Annual Symposium on Switching Circuit Theory and Logical Design, 1965

1964

Pair Algebra and Its Application to Automata Theory

[BibT_eX]

[DOI]

Inf. Control., December, 1964

On the application of pair algebra to automata theory

[BibT_eX]

[DOI]

Proceedings of the 5th Annual Symposium on Switching Circuit Theory and Logical Design, 1964

Computational complexity of recursive sequences

[BibT_eX]

[DOI]

Proceedings of the 5th Annual Symposium on Switching Circuit Theory and Logical Design, 1964

1963

Regularity Preserving Modifications of Regular Expressions

[BibT_eX]

[DOI]

Inf. Control., March, 1963

A Study of Feedback and Errors in Sequential Machines.

[BibT_eX]

[DOI]

IEEE Trans. Electron. Comput., 1963

1962

Some Dangers in State Reduction of Sequential Machines

[BibT_eX]

[DOI]

Inf. Control., September, 1962

1961

On the State Assignment Problem for Sequential Machines II.

[BibT_eX]

[DOI]