Publications

Journals

• Addario-Berry, L., Chor, B., Hallett, M., Lagergren, J., Panconesi, A., and Wareham, T. (2004) "Ancestral Maximum Likelihood of Evolutionary Trees is Hard." Journal of Bioinformatics and Computational Biology, 2(2), 257-271.
• Bodlaender, H., Downey, R.G., Fellows, M.R., Hallett, M.T., and Wareham, H.T. (1995) "Parameterized Complexity Analysis in Computational Biology." Computer Applications in the Biosciences, 11(1), 49-57. (PostScript/16 pages)
• Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hallett, M.T., Wareham, H.T., and Warnow, T.J. (2000) "The Hardness of Perfect Phylogeny, Feasible Register Assignment and Other Problems on Thin Colored Graphs." Theoretical Computer Science, 244, 167-188.
• Bodlaender, H., Downey, R.G., Fellows, M.R., and Wareham, H.T. (1995) "The Parameterized Complexity of Sequence Alignment and Consensus." Theoretical Computer Science, 147(1-2), 31-54. (PostScript/26 pages)
• Della Vedova, G. and Wareham, H.T. (2002) "Optimal Algorithms for Local Vertex Quartet Cleaning." Bioinformatics, 18(10), 1297-1304.
• Evans, P.A., Smith, A.D., and Wareham, H.T. (2003) "On the Complexity of Finding Common Approximate Substrings." Theoretical Computer Science, 306(1-3), 407-430.
• Evans, P.A., Wareham, H.T., and Chaytor, R. (2009) "Fixed-Parameter Tractability of Anonymizing Data by Suppressing Entries." Journal of Combinatorial Optimization, 18(4), 362-375.
• Kwisthout, J., Wareham, T., and van Rooij, I. (2011) "Bayesian Intractability is not an Ailment that Approximation can Cure." Cognitive Science, 35(5), 779-784.
• 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.
• van Rooij, I. and Wareham, T. (2008) "Parameterized Complexity in Cognitive Modeling: Foundations, Applications, and Opportunities." Computer Journal, 51(3), 385-404.
• van Rooij, I, Wright, C.D., and Wareham, T. (2012) "Intractability and the Use of Heuristics in Psychological Explanation." To appear, Synthese.
• Wareham, H.T. (1995) "A Simplified Proof of the NP- and MAX SNP-hardness of Multiple Sequence Tree Alignment." Journal of Computational Biology, 2(4), 509-514. (PostScript/7 pages)
• Wareham, T., Evans, P., and van Rooij, I. (2011) ``What Does (and Doesn't) Make Analogical Problem Solving Easy? A Complexity-Theoretic Investigation.'' Journal of Problem Solving, 3(2), 30-71.
• Wareham, T. and van Rooij, I (2011) "On the Computational Challenges of Analogy-based Generalization." Cognitive Systems Research, 12, 266-280.
• Wareham, T., van Rooij, I., and Muller, M. (2008) "Commentary: Computational complexity analysis can help, but first we need a theory." Behavioral & Brain Sciences, 31(4), 399-400.

Conference Proceedings (refereed by full paper)

• Addario-Berry, L., Chor, B., Hallett, M., Lagergren, J., Panconesi, A., and Wareham, T. (2003) "Ancestral Maximum Likelihood of Evolutionary Trees is Hard." In Gary Benson and Roderic D.M. Page (eds.) Proceedings of the Third International Workshop on Algorithms in Bioinformatics (WABI'03). Lecture Notes in Computer Science no. 2812. Springer-Verlag; Berlin. 202-215. Appeared as Addario-Berry et al. (2004), Journal of Bioinformatics and Computational Biology.
• Berry, V., Jiang, T., Kearney, P., Li, M., and Wareham, H.T. (1999) "Quartet Cleaning: Improved Algorithms and Simulations." In Jaroslav Nesteril (ed.) Proceedings: ESA'99 - 7th Annual European Symposium on Algorithms. Lecture Notes in Computer Science no. 1643. Springer-Verlag; Berlin. 313-324.
• Blokpoel, M., Kwisthout, J., Wareham, T., Haselager, P., and van Rooij, I. (2011) "The computational costs of recipient design and intention recognition in communication." In L. Carlson, C. Hoelscher, and T.F. Shipley (eds.) Proceedings of the 33rd Annual Meeting of the Cognitive Science Society. Cognitive Science Society; Austin, TX. 465-470.
• Bodlaender, H., Downey, R.G., Fellows, M.R., Hallett, M.T., and Wareham, H.T. (1994) "Parameterized Complexity Analysis in Computational Biology." In the Proceedings of the First International Workshop on Shape and Pattern Matching in Computational Biology. Privately published by the steering committee for this workshop (Andrea Califano and Isidore Rigoutsos, IBM T.J. Watson Research Center, Yorktown Heights, NY). 99-116. Appeared as Bodlaender et al. (1995), Computer Applications in the Biosciences.
• Bodlaender, H., Downey, R.G., Fellows, M.R., and Wareham, H.T. (1994) "The Parameterized Complexity of Sequence Alignment and Consensus." In M. Crochemore and D. Gusfield (eds.) Proceedings of the Fifth Annual Symposium on Combinatorial Pattern Matching (CPM'94). Lecture Notes in Computer Science no. 807. Springer-Verlag; Berlin. 15-30. Appeared as Bodlaender et al. (1995), Theoretical Computer Science.
• Bryant, D., Berry, V., Jiang, T., Kearney, P., Li, M., Wareham, T., and Zhang, H. (2000) "A Practical Algorithm for Recovering the Best Supported Edges of an Evolutionary Tree." In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2000). ACM Press; New York. 287-296.
• 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. (PostScript/6 pages)
• Chaytor, R., Brown, E., and Wareham, T. (2006) "Privacy Advisors for Personal Information Management." Workshop Proceedings: Personal Information Management -- Now That We're Talking, What are We Learning?, Twenty-Ninth Annual International SIGIR Conference on Search and Development in Information Retrieval. 28-31.
• Chaytor, R., Evans, P., and Wareham, T. (2008) "Fixed-Parameter Tractability of Anonymizing Data by Suppressing Entries." In B. Yang, D.-Z. Du, and C.A. Wang (eds.) Proceedings of the 2nd International Conference on Combinatorial Optimization and Applications (COCOA 2008). Lecture Notes in Computer Science no. 5165. Springer-Verlag; Berlin. 23-31.
• Della Vedova, G. and Wareham, H.T. (2002) "Optimal Algorithms for Local Vertex Quartet Cleaning." In the Proceedings of the 17th ACM Symposium on Applied Computing (SAC 2002). ACM Press; New York. 173-177. Appeared as Della Vedova and Wareham (2002), Bioinformatics.
• Downey, R.G., Fellows, M.R., Kapron, B.M., Hallett, M.T., and Wareham, H.T. (1994) "Parameterized Complexity of Some Problems in Logic and Linguistics (Extended Abstract)." In A. Nerode and Y.V. Matiyasevich (eds.) Logical Foundations of Computer Science. Lecture Notes in Computer Science no. 813. Springer-Verlag; Berlin. 89-101.
• Evans, P.A. and Wareham, H.T. (2001) "Exact Algorithms for Computing Pairwise Alignments and 3-Medians from Structure-Annotated Sequences (Extended Abstract)." In the Proceedings of the Sixth Pacific Symposium on Biocomputing (PSB 2001). World Scientific Press; Singapore. 559-570. (PostScript/12 pages) [on-line proceedings]
• Fellows, M.R., Hallett, M.T., and Wareham, H.T. (1993) "DNA Physical Mapping: Three Ways Difficult." In T. Lengauer (ed.) Proceedings: ESA'93 - European Symposium on Algorithms. Lecture Notes in Computer Science no. 726. Springer-Verlag; Berlin. 157-168.
• Hamilton, M., Chaytor, R., and Wareham, T. (2006) "The Parameterized Complexity of Enumerating Frequent Itemsets." In H. Bodlaender and M. Langston (eds.) Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC'06). Lecture Notes in Computer Science no. 4169. Springer-Verlag; Berlin. 227-238.
• Muller, M., van Rooij, I., and Wareham, T. (2009) "Similarity as Tractable Transformation." In N.A. Taatgen and H. van Rijn (eds.) Proceedings of the 31st Annual Meeting of the Cognitive Science Society. Cognitive Science Society; Austin, TX. 49-55.
• Rose, Y., Hedlund, G.J., Byrne, R., Wareham, T. and MacWhinney, B. (2007) "Phon 1.2: A Computational Basis for Phonological Database Elaboration and Model Testing." In P. Buttery, A. Villavicencio and A. Korhonen (eds.) Proceedings of the Workshop on Cognitive Aspects of Computational Language Acquisition: 45th Annual Meeting of the Association for Computational Linguistics. ACL; Stroudsburg, PA. 17-24.
• Uddin, M., Yu, T., and Wareham, T. (2008) "A Cooperative Coevolutionary Algorithm for Haplotype Pattern Detection in Case-Control Data." Proceedings of the 3rd Annual Canadian Student Conference on Biomedical Computing (CSCBC 2008).
• 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.
• Wareham, H.T. (1996) "The Role of Parameterized Computational Complexity Theory in Cognitive Modeling." AAAI-96 Workshop Working Notes: Computational Cognitive Modeling: Source of the Power. (PostScript/ PDF [6 pages])
• Wareham, H.T. (2001) "The Parameterized Complexity of Intersection and Composition Operations on Sets of Finite-State Automata." In Proceedings of the Fifth International Conference on Implementation and Application of Automata. Lecture Notes in Computer Science no. 2088. Springer-Verlag; Berlin. 302-310. (PostScript/ PDF [9 pages])
• Wareham, H.T., Jiang, T., Zhang, X., and Trendall, C.G. (2000) "Stochastic Heuristic Algorithms for Target Motif Identification (Extended Abstract)." In the Proceedings of the Fifth Pacific Symposium on Biocomputing (PSB 2000). World Scientific Press; Singapore. 389-400, (PostScript/12 pages) [on-line proceedings]
• Wareham, T., Kwisthout, J., Haselager, W., and van Rooij, I. (2011) "Ignorance is Bliss: A Complexity Perspective on Adapting Reactive Architectures." In the Proceedings of the First Joint IEEE International Conference on Development and Learning and on Epigenetic Robotics (Volume 2). 1-5. DOI: 10.1109/DEVLRN.2011.6037337.
• Wareham, T., Robere, R., and van Rooij, I. (2012) "A Change for the Better? Assessing the Computational Cost of Re-Representation." In N. Russwinkel, U. Drewitz, and H. van Rijn (eds.) Proceedings of ICCM 2012: 11th International Conference on Cognitive Modeling. TU Berlin. 111-116.

Conference Proceedings (refereed by abstract)

• Chaytor, R., Gillard, P., and and Wareham, T. (2007) "High Performance Privacy Protection Hardware." Proceedings of the 17th Annual Newfoundland Electrical and Computer Engineering Conference (NECEC 2007).
• Churchill, D., Gillard, P., Hamilton, M., and Wareham, T. (2004) "Prototyping Parallel Sequence Edit-Distance Algorithms in FPGA Hardware." In Proceedings of the Fourteenth Annual Newfoundland Electrical and Computer Engineering Conference (NECEC 2004).
• Evans, P.A. and Wareham, H.T. (2001) "Practical Algorithms for Universal DNA Primer Design: An Exercise in Algorithm Engineering". In N. El-Mabrouk, T. Lengauer, and D. Sankoff (eds.) Currents in Computational Molecular Biology 2001. Les Publications CRM; Montreal, PQ. 25-26. (PostScript/2 pages)
• Gedge, J., Hedlund, G.J., Rose, Y., and Wareham, T. (2007) "Natural Language Process Detection: From Conception to Implementation." Proceedings of the 17th Annual Newfoundland Electrical and Computer Engineering Conference (NECEC 2007).
• Hamilton, M., Muller, M., van Rooij, I., and Wareham, T. (2007) "Approximating Solution Structure." In E. Demaine, G.Z. Gutin, D. Marx, and U. Stege (eds.) Structure Theory and FPT Algorithmics for Graphs, Digraphs, and Hypergraphs. Dagstuhl Seminar Proceedings no. 07281. Internationales Begegnungs- und Forschungszentrum fur Informatik (IBFI), Schloss Dagstuhl, Germany. URL: http://drops.dagstuhl.de/portals/07281/
• Hamilton, R. and Wareham, T. (2012) "Practical Algorithms for Schema-based Analogy Mapping." In N. Russwinkel, U. Drewitz, and H. van Rijn (eds.) Proceedings of ICCM 2012: 11th International Conference on Cognitive Modeling. TU Berlin. 311-312.
• Hedlund, G.J., Maddocks, K., Rose, Y., and Wareham, T. (2005) "Natural Language Syllable Alignment: From Conception to Implementation." In Proceedings of the Fifteenth Annual Newfoundland Electrical and Computer Engineering Conference (NECEC 2005). (PDF/5 pages)
• Rose, Y., MacWhinney, B., Byrne, R., Hedlund, G., Maddocks, K., O'Brien, P., and Wareham, T. (2006) "Introducing Phon: A Software Solution for the Study of Phonological Acquisition." In D. Bamman, T. Magnitskaia, and C. Zaller (eds.) Proceedings of the 30th Annual Boston University Conference on Language Development. Cascadilla Press; Somerville, MA. 489-500.
• Wareham, T. (2012) "What Can (and Can't) Make Problem Solving by Insight Possible? A Complexity-Theoretic Investigation." In N. Russwinkel, U. Drewitz, and H. van Rijn (eds.) Proceedings of ICCM 2012: 11th International Conference on Cognitive Modeling. TU Berlin. 142-143.

Conference Abstracts (refereed)

• Uddin, M., Wareham, T., Rahman, P., Peddle, L., Maksymowych, W.P., Yoshikawa, T., and Yu, T. (2008) "A Robust Evolutionary Algorithm for Computing Significant Haplotype Patterns with Arbitrary Number and Distribution of Markers in Case-Control Data." Proceedings of the 10th International Meeting on Human Genome Variation (HGV2008) (p. 23).

Book Chapters

• Evans, P.A. and Wareham, H.T. (2011) ``Efficient Restricted-Case Algorithms for Problems in Computational Biology.'' In M. Elloumi and A.Y. Zomaya (eds.) Algorithms in Computational Molecular Biology: Techniques, Approaches and Applications. Wiley. 27-49.
• Rose, Y., Hedlund, G.J., Byrne, R., Wareham, T. and MacWhinney, B. (2012) ``Phon: A Computational Basis for Phonological Database Elaboration and Model Testing.'' To appear in Cognitive Aspects of Computational Language Acquisition. Springer

Books (Edited)

• Akl, S.G., Calude, C.S., Dinneen, M.J., Rozenberg, G. and Wareham. H.T. (eds.) (2007) Unconventional Computation: Proceedings of the 6th International Conference, UC 2007. Lecture Notes in Computer Science no. 4618. Springer; Heidelberg.

Newsletters

• Evans, P.A. and Wareham, H.T. (2000) "Conference Report: CPM'2000." SIGBIO Newsletter, 20(3), 25. ( browsable)
• Hallett, M.T. and Wareham, H.T. (1994) "A Compendium of Parameterized Complexity Results." SIGACT News, 25(3), 122-123. (Home Page)
• Wareham, H.T. (2000) "Conference Report: PSB'2000." SIGBIO Newsletter, 20(1), 27-28. ( browsable)
• Wareham, H.T. (2000) "Conference Report: RECOMB'2000." SIGBIO Newsletter, 20(2), 22. ( browsable)
• Wareham, H.T. (2001) "Conference Report: PSB'2001." SIGBIO Newsletter, 21(1). 27-28. ( browsable)

Book Notices / Reviews

• Wareham, H.T. (1996) "Book Notice: Eric Sven Ristad (ed.) Language Computations." Language, 72(1), 186-187. (PostScript/2 pages)
• Wareham, H.T. (1998) "Book Review: Jennifer Cole, Georgia M. Green and Jerry L. Morgan (eds.) Linguistics and Computation." Natural Language Engineering, 4(3), 277-279. (PostScript/4 pages)

Research Project Reports

• Brown, E., Johnston, R., Wareham, H., Farrell, G., and Hoekman, T. (2008) Private / Public Sharing of Personal Information: Lessons from the Health Care Sector. Research Project Report (Contributions Program), Office of the Privacy Commissioner of Canada, March 2008.
• Brown, E., Wareham, H., Farrell, G., Hoekman, T., Chaytor, R., Barrigar, J., Kosa, T., Barton, C., Barrett, N., Mercer, C., and Thoms, A. (2007) Technology Choices and Privacy Policy in Health Care. Research Project Report (Contributions Program), Office of the Privacy Commissioner of Canada, April 2007.

Technical Reports

• Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hallett, M.T., Wareham, H.T., and Warnow, T.J. (1995) "The Hardness of Problems on Thin Colored Graphs." Technical Report UU-CS-1995-36, Department of Computer Science, University of Utrecht.
• Evans, P., Gedge, J., Muller, M., van Rooij, I., and Wareham, T. (2008) "On the Computational Complexity of Analogy Derivation in the Strtucture-Mapping Framework." Technical Report 2008-03, Department of Computer Science, Memorial University of Newfoundland.
• Evans, P., Smith, A., and Wareham, T. (2001) "The Parameterized Complexity of p-Center Approximate Substring Problems." Technical report TR01-149, Faculty of Computer Science, University of New Brunswick.
• Hamilton, M., Muller, M., van Rooij, I., and Wareham, T. (2007) "Approximating Solution Structure." Technical Report 2007-02, Department of Computer Science, Memorial University of Newfoundland.
• Wareham, H.T. (1993) On the Computational Complexity of Inferring Evolutionary Trees. M.Sc. thesis. Technical Report no. 9301, Department of Computer Science, Memorial University of Newfoundland, March 1993. ( Abstract (text); Document (PostScript/101 pages) )
• Wareham, H.T. (1999) "Systematic Parameterized Complexity Analysis in Computational Phonology." Ph.D. thesis, Department of Computer Science, University of Victoria, April 1999. Technical Report ROA-318-0599, Rutgers Optimality Archive. (Abstract: PostScript/ PDF [1 page]; Thesis: PostScript/ PDF [215 pages])