Computer Science 6789, Fall '26
Course Diary

---

Copyright 2026 by Todd Wareham
All rights reserved

---

Week 1, Week 2, Week 3, Week 4, Week 5, Week 6,
Week 7, Week 8, Week 9, Week 10, Week 11, (end of diary)

Tuesday, September 15 (Lecture #1)

• Review: Classical Computational Complexity Analysis (6789W14, Lectures #1-5; vR+19, Chapers 2-4; Wareham (To Appear), Section 3)
  • Prologue: 3D Robot Motion Planning
  • Elements of Classical Computational Complexity Analysis
    • Computational Problems
    • Algorithm Efficiency: Polynomial-time Tractability
      • The 4 Necessary Lies of Asymptotic Worst-case time Complexity
    • Polynomial-time Reductions
    • Problem Classes: P, NP, and EXPTIME
    • Proving Polynomial-time Intractability

Tuesday, September 22 (Lecture #2)

• Parameterized Complexity Analysis (6789W14, Lectures #5-9; vR+19, Chapers 5-7; Wareham (To Appear), Section 3)
  • Potential Algorithms for Polynomial-time Intractable Problems
  • The Road to Parameterized Complexity
  • Elements of Parameterized Computational Complexity Analysis
    • Parameterized Problems
    • Algorithm Efficiency: Fixed-parameter and XP Tractability
    • Fixed-parameter Reductions

Tuesday, September 29 (Lecture #3)

• Parameterized Complexity Analysis (Cont'd) (6789W14, Lectures #5-9; vR+19, Chapers 5-7; Wareham (To Appear), Section 3)
  • Elements of Parameterized Computational Complexity Analysis (Cont'd)
    • Problem Classes: TLFPT, LFPT, FPT, W[i] (i >= 1), XP
    • Proving Fixed-parameter and XP Intractability
      • 3D Robot Motion Planning (Cesati and Wareham (1995))
    • Styles of Parameterized Complexity Analysis
      • Single-parameter
      • Multi-parameter / Systematic
        • Leveraging Parameterized Results
          Subset / superset
          • Numerical

Tuesday, October 6 (Lecture #4)

• Examples of Parameterized Complexity Analysis
  • Analogy as Structure Mapping (vr+19, Chapter 11; van Rooij et al (2008))
  • Communication as Bayesian Inference (vr+19, Chapter 12; van Rooij et al (2011))

Tuesday, October 13

• Midterm break; no lecture

Tuesday, October 20 (Lecture #5)

• Examples of Parameterized Complexity Analysis (Cont'd)
  • Phonological Processing (Wareham (1999))
  • Designing finite-state robot swarms for distributed construction in 2D environments (Wareham and Vardy (2018))
  • Designing finite-state robot swarms for distributed structure repair and maintenance in 2D environments (Wareham (2019))

Tuesday, October 27

• Student Presentations I

Tuesday, November 3 (Lecture #6)

• Examples of Parameterized Complexity Analysis (Cont'd)
  • Designing and recpnfiguring component-based software systems (Wareham and Sweers (2015))
  • Artificial neural network reverse-engineering (Adolfi, Vilas, and Wareham (2024))

Tuesday, November 10 (Lecture #7)

• Examples of Parameterized Complexity Analysis (Cont'd)
  • Syntax-guided Program Synthesis

Tuesday, November 17

• No lecture

Tuesday, November 24

• Student Presentations II

References

• Adolfi, F., Vilas, M., and Wareham, T. (2024) ``Complexity-Theoretic Limits on the Promises of Artificial Neural Network Reverse-Engineering.'' In the Proceedings of the 46th Annual Meeting of the Cognitive Science Society (CogSci 2024). (PDF)
• Cesati, M. and Wareham, H.T. (1995) "Parameterized Complexity Analysis in Robot Motion Planning." In Proceedings of the 25th IEEE International Conference on Systems, Man, and Cybernetics: Volume 1. IEEE Press; Los Alamitos, CA. 880-885. (PDF)
• Cygan, M., Fomin, F.V., Kowalik, T., Lokshtanov, D., Marx, D., Pilipczuk, M., and Cygan, M. (2015) Parameterized Algorithms. Springer.
• Downey, R.G. and Fellows, M.R. (1999) Parameterized Complexity. Springer; Berlin.
• Downey, R.G., and Fellows, M.R. (2013) Fundamentals of Parameterized
• Flum, J. and Grohe, M. (2006) Parameterized Complexity Theory. Springer; Berlin.
• Flum, J. and Grohe, M. (2006) Parameterized Complexity Theory. Springer; Berlin.
• Fomin, F. V., Lokshtanov, D., Saurabh, S., and Zehavi, M. (2019) Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press.
• Garey, M.R. and Johnson, D.S. (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman; San Francisco.
• Niedermeier, R. (2006) Invitation to Fixed-Parameter Algorithms. Oxford University Press.
• 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.
• van Rooij, I., Evans, P., Muller, M., Gedge, J., and Wareham, T. (2008) "Identifying Sources of Intractability in Cognitive Models: An Illustration using Analogical Structure Mapping." In B.C. Love, K. McRae, and V.M. Sloutsky (eds.) Proceedings of the 30th Annual Meeting of the Cognitive Science Society. Cognitive Science Society; Austin, TX. 915-920. (PDF | Supplementary Materials)
• van Rooij, I., Kwisthout, J., Blokpoel, M., Szymanik, J., Wareham, T., and Toni, I. (2011) "Intentional Communication: Computationally Easy or Difficult?" Frontiers in Human Neuroscience, 5. DOI: 10.3389/fnhum.2011.00052. (PDF)
• Wareham, T. (1999) Systematic Parameterized Complexity Analysis in Computational Phonology. Ph.D. thesis, Department of Computer Science, University of Victoria. (PDF)
• Wareham, T. (2012) "Flyby: life before, during, and after graduate studies with mike fellows. In The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday. Springer; Berlin. 51-55. [PDF]
• 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. (PDF)
• Wareham, T. (To appear) "Viable Algorithmic Options for Problem Solving by State-space Search: A Computational Complexity Perspective." In Sebastien Helie (Ed.) The Innovative Mind: Cognitive Foundations of Problem Solving, Creativity, and Engineering Design. Springer. (PDF)
• Wareham, T. and Sweers, M. (2016) "On the Computational Complexity of Designing and Reconfiguring Component-based Software Systems." EAI Endorsed Transactions on Self-Adaptive Systems, 16(5): e4. (PDF)
• Wareham, T. and Vardy, A. (2018) "Putting It Together: The Computational Complexity of Designing Robot Controllers and Environments for Distributed Construction." Swarm Intelligence, 12(2), 111-128. (PDF | Supplementary Materials)