Research Interests
My research involves applying various theories of computational complexity
(NP-completeness, parameterized complexity, polynomial-time approximation)
to the analysis of problems from various disciplines, both as an aid to
characterizing the sources of intractability in these problems and designing
the most efficient algorithms possible for these problems. Problem-areas I have
worked on in the last five years are as follows:
-
Cognitive Science: I have used classical and parameterized complexity results to
diagnose the sources of intractability in various theories of cognitive abilities such as
analogy derivation, Bayesian-based reasoning, problem solving, and decision
making; these sources are then used as a guide to revisions of those theories.
I have co-authored the following publications in this area:
-
Adolfi, F., Wareham, T., and van Rooij, I. (2023) "A Computational
Complexity Perspective on Segmentation as a Cognitive Subcomputation."
Topics in Cognitive Science, 15(2), 255-273.
-
Adolfi, F., Wareham, T., and van Rooij, I. (2022) "Computational
Complexity of Segmentation." In the Proceedings of the 44th Annual Meeting
of the Cognitive Science Society (CogSci 2022).
-
Adolfi, F., Wareham, T., and van Rooij, I. (2022) "Computational
Complexity of Segmentation." CoRR abs/2201.13106 (8 pages).
[PDF]
-
Rich, P., Blokpoel, M., de Haan, R., Otworowska, M., Sweers, M., Wareham, T., and
van Rooij, I. (2021) "Naturalism, Tractability and the Adaptive Toolbox",
Synthese, 198(6), 5749-5784.
-
Rich, P., de Haan, R., Wareham, T., and van Rooij, I. (2021) "How hard
is Cognitive Science?" In the Proceedings of the 43rd Annual Meeting of the
Cognitive Science Society (CogSci 2021). 3034-3040.
-
Woensdregt, M., Spike, M., de Haan, R., Wareham, T., van Rooij, I., and
Blokpoel, M. (2021) "Why is scaling up models of language evolution
hard?" In the Proceedings of the 43rd Annual Meeting of the
Cognitive Science Society (CogSci 2021). 209-215.
-
van Rooij, I., Blokpoel, M., de Haan, R., and Wareham, T. (2019)
"Tractable embodied cognition needs embeddedness".
Italian Journal of Cognitive Sciences, 8(15), 25-38.
-
van Rooij, I., Blokpoel, M., Kwisthout, J., and Wareham, T. (2019)
Cognition and Intractability: A Guide to Classical and Parameterized
Complexity Analysis. Cambridge University Press.
-
Robotics: I have used classical and parameterized complexity
results to diagnose the sources of intractability in various problems associated with
the design of groups of one or more reactive robots.
I have co-authored the following publications in this area:
-
Wareham, T., de Haan, R., Vardy, A., and van Rooij, I. (2023)
"Swarm Control for Distributed Construction: A Computational Complexity
Perspective." ACM Transactions on Human-Robot Interaction, 12(1), 6:1-6:45.
-
Wareham, T. (2022) "Creating Teams of Simple Agents for Specified
Tasks: A Computational Complexity Perspective."
CoRR abs/2205.02061 (20 pages).
[PDF]
-
Wareham, T. and Vardy, A. (2022) "Environmental Sensing Options for
Robot Teams: A Computational Complexity Perspective."
CoRR abs/2205.05034 (77 pages).
[PDF]
-
Wareham, T. and Vardy, A. (2021) "The Computational Complexity of
Designing Scalar-field Sensing Robot Teams and Environments for Distributed
Construction (Extended Abstract)." In the Proceedings of the 4th
International Workshop on Self-Organised Construction (SOCO 2021).
2021 IEEE International Conference on Autonomic Computing and
Self-Organizing Systems Companion (ACSOS-C). IEEE Computer Society;
Los Alamitos, CA. 232-237.
-
Wareham, T. (2019) "Designing Robot Teams for Distributed Construction, Repair, and
Maintenance." ACM Transactions on Autonomous and Adaptive Systems, 14(1), 2:1-2:29.
-
Timmar, M. and Wareham, T. (2019) "The Computational Complexity of
Controller-Environment Co-design using Library Selection for Distributed
Construction." In N. Correll, M. Schwager, and M. Otte (Eds.) Distributed
Autonomous Robotic Systems: The 14th International Symposium. Springer
Proceedings in Advance Robotics vol. 9. Springer Nature Switzerland AG.
51-63.
-
Software Engineering: I have used classical and parameterized complexity
results to diagnose the sources of intractability in various problems associated with
the design, reconfiguration, and (re)modularization of software systems.
I have co-authored the following publications in this area:
-
Wareham, T. and de Haan, R. (2022) "Viable Algorithmic Options for Creating
and Adapting Emergent Software Systems.'' CoRR abs/2205.06097 (76 pages)
[PDF]
-
Wareham, T. and Sweers, M. (2022) "Exploring Viable Algorithmic Options for
Automatically Creating and Reconfiguring Component-based Software Systems:
A Computational Complexity Approach (Full Version)."
CoRR abs/2205.05001 (38 pages).
[PDF]
-
Machine Learning: I have used classical and parameterized complexity
to assess the computational difficulty of Learning from Demonstration
(LfD). I have co-authored the following publications in this area:
-
Wareham, T. (2022) "Exploring Viable Algorithmic Options for Learning
from Demonstration (LfD): A Parameterized Complexity Approach."
CoRR abs/2205.04989 (38 pages).
[PDF]
Created: December 5, 2007
Last Modified: January 1, 2024