IBM Victoria Software Lab (formerly PureEdge Solutions Inc.)
Email: j b o y e r "at" a c m . o r g
|
John M. Boyer |
| Senior Technical Staff Member IBM Victoria Software Lab (formerly PureEdge Solutions Inc.) Email: j b o y e r "at" a c m . o r g |
Ph.D. (Computer Science), University of Victoria, November 2001
One key area of interest for me is the design, analysis and implementation of efficient algorithms. My current research has focused on algorithms for graphs and networks, with a sprinkling of work in computational geometry, randomized algorithms, parallel algorithms, and combinatorial generation. While I enjoy many problems of purely theoretical interest, I tend to gravitate to problems for which a practical requirement can be defined. In part, this is because I enjoy creating software implementations that solve the problems on which I work. However, with requirements in hand, the mandate to implement (and debug, profile and maintain) imposes a healthy dose of realism on the design process. Specifically, a simplified, well-designed algorithm leads to increased understandability, better encapsulation, and many additional benefits typically attributed to good software engineering.
My guiding philosophy: Theory into Practice. It signifies the influence that software engineering can have on algorithm design, specifically that the tenets of software engineering are the basis for concluding that simplified algorithms are more valuable and creating them is worthwhile. It also signifies the influence of algorithms on software engineering, which is typically manifested by the application and augmentation of good discrete algorithms to solve interesting problems.
My future work in this area will typically span ACM categories F.2.2 (Non-numerical Algorithms and Problems; Computations on discrete structures), G.2 (Discrete Mathematics; Combinatorics, Graph theory, Graph algorithms, Applications), and G.3 (Probability and Statistics; Probabilistic algorithms). My shorter term work is focused on investigation of simplified solutions for subgraph homeomorphism problems, projective planarity, and improvements to other graph algorithms, esp. for planar and outerplanar graphs. While applications of discrete algorithms is covered by G.2.3, my publications and ongoing efforts in such applications to software engineering problems have arisen mainly from my involvement in the XML community.
The aftermath of creating XML as a syntax for representing any web data has been an explosion of inter-related tools and specifications. XML, XPath, XSLT, XML Schema, XML Canonicalization, XML Signature, and XForms (to name just a few) have all been created in the hope of achieving the XML promise of interoperable software. It is an interesting field rich in technologies worth studying, and I have been privileged to serve as a member of both the XML Signature and XForms working groups of the W3C. I am currently the W3C Forms Working Group Chair as well as Editor for XForms 1.1. I have served as editor and author of numerous W3C Recommendations, including:
My future work in this area includes further investigation of XML document security and more advanced XForms computation algorithms. In addition to G.2.3, typical ACM categories for these publications would be D.3 (Programming Languages; Non-procedural languages, Specialized application languages), I.7.2 (Document Preparation; Markup languages, Scripting languages, Standards) and K.4 (Computers and Society; Social issues, Organizational issues, Electronic Commerce Security).
"Interactive Office Documents: A New Face for Web 2.0 Applications". Proceedings of 2008 ACM Symposium on Document Engineering, pp. 8-17, Sept. 16--19, 2008. Sao Paulo, Brazil.
"An Office Document Mashup for Document-Centric Business Processes". Proceedings of 2008 ACM Symposium on Document Engineering, pp. 100-101, Sept. 16--19, 2008. Sao Paulo, Brazil.
"Applying XML Signatures to XForms-based Documents". Accepted to Proceedings of XML 2006 Conference & Exposition, December 5-7, 2006. Boston, MA, USA.
"A New Method for Efficiently Generating Planar Graph Visibility Representations". In P. Eades and P. Healy, editors, Proceedings of the 13th International Conference on Graph Drawing 2005, Lecture Notes Comput. Sci., Volume 3843, pp. 508-511, Springer-Verlag, 2006. PDF Version
"Enterprise-level Web Form Applications with XFDL and XForms". Proceedings of XML 2005 Conference & Exposition, November 14-18, 2005. Atlanta, GA, USA.
"Simple Constant Amortized Time Generation of Fixed Length Numeric Partitions".
Journal of Algorithms, Volume 54, pp. 31-39 (2005).
Local PDF Version, Local Postscript Version
(Some of these results were presented at Tenth SIAM Conference on Discrete Mathematics,
Minneapolis, MN, June 2000.)
"On the Cutting Edge: Simplified O(n) Planarity by Edge Addition" (with W. Myrvold). Journal of Graph Algorithms and Applications. Volume 8, No. 3, pp. 241-273, 2004. See also the Reference Implementation.
"Additional PC-tree Planarity Conditions". In J. Pach, editor, Proceedings of the 12th International Conference on Graph Drawing 2004, Lecture Notes Comput. Sci., Volume 3383, pp. 82-88, Springer-Verlag, 2005. PDF Version
"Lempel, Even, and Cederbaum Planarity Method". (with C. G. Fernandes, A. Noma and J.C. Pina). In C. C. Ribeiro and S. L. Martins, Eds., Third International Workshop in Experimental Algorithms (Angra dos Reis, 2004), Lecture Notes Comput. Sci., Volume 3059, pp. 129-144, Springer-Verlag, 2004.
"Stop Minding Your P's and Q's: Implementing a Fast and Simple DFS-based Planarity
Testing and Embedding Algorithm" (with P. F. Cortese, M. Patrignani, and G. Di Battista).
In G. Liotta, editor, Proceedings of the 11th International Conference on Graph Drawing 2003,
Lecture Notes Comput. Sci., Volume 2912, pages 25-36, Springer-Verlag 2004.
See also Technical Report RT-DIA-83-2003,
Dipartimento di Informatica e Automazione, Università di Roma Tre, Rome, Nov. 2003.
Note: This is a full exposition of the original `vertex addition' algorithm in the SODA extended abstract;
the journal paper above describes a newer `Edge Addition' algorithm.
"Bulletproof Business Process Automation: Securing XML Forms with Document Subset Signatures" Proceedings of the ACM Workshop on XML Security, October 31, 2003. Fairfax, VA, USA. PDF Version
"The XForms Computation Engine: Rationale, Theory and Implementation Experience" (with M. Honkala). Proceedings of the 6th IASTED International Conference on Internet and Multimedia Systems and Applications, Kauai, Hawaii, August 12-14, 2002.
"Improper Utilization of Digital Signature Technology", RSA 2000 Conference Proceedings, San Jose, California, January 2000.
"XFDL: Creating Electronic Commerce Transaction Records Using XML" (with B. Blair), Computer Networks: The International Journal of Computer and Telecommunications Networking, vol. 31, pp. 1611-1622, 1999.
"Stop Minding Your P's and Q's: A Simplified O(n) Planar Embedding Algorithm" (with W. Myrvold), Proceedings of The Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, Maryland, pp. 140-147, January 1999.
"XForms 1.1", W3C Candidate Recommendation, 2007. http://www.w3.org/TR/xforms11/
"XForms 1.0 Third Edition", W3C Recommendation, 2007. http://www.w3.org/TR/2007/REC-xforms-20071029/
"XForms 1.0 Second Edition" (with D. Landwehr, R. Merrick, and T. V. Raman), W3C Recommendation, 2006. http://www.w3.org/TR/2006/REC-xforms-20060314/
"XForms 1.1 Requirements" (with R. Merrick), W3C WG Note, 2004. http://www.w3.org/TR/xforms-11-req
"XForms 1.0" (eds. M. Dubinko, L. Klotz, R. Merrick, and T. V. Raman), W3C Recommendation, 2003. http://www.w3.org/TR/2003/REC-xforms-20031014/
"XPath Filter 2.0" (with J. Reagle and M. Hughes), W3C Recommendation, 2002. http://www.w3.org/TR/xmldsig-filter2/
"Exclusive XML Canonicalization Version 1.0" (with J. Reagle and D. Eastlake), W3C Recommendation, 2002. http://www.w3.org/TR/xml-exc-c14n
"XML Signature Syntax and Processing" (with D. Eastlake, J. Reagle, D. Solo, M. Bartel, B. Fox, B. LaMacchia and E. Simon), W3C Recommendation, 2002. http://www.w3.org/TR/xmldsig-core/
"Canonical XML Version 1.0", W3C Recommendation, 2001. http://www.w3.org/TR/2001/REC-xml-c14n-20010315 and http://www.ietf.org/rfc/rfc3076.txt
Rich Web Application Backplane. Annotated Presentation to W3C Track at the World Wide Web Conference, Banff, Canada, May 2007.
Designing XForms. Presentation to Developer's Track at the World Wide Web Conference, Banff, Canada, May 2007.
Rich Web Application Backplane (with M. Birbeck, A. Gilman, K. Kelly, S. Pemberton, and C. Wiecha). W3C Coordination Group Note, 16 November 2006.
Planarity by Edge Addition, Dr. Dobb's Journal, No. 372, May 2005.
Cause-and-effect Programming with XForms, Dr. Dobb's Journal, No. 371, April 2005.
Secure, Intelligent Business Process Agents: Compound Documents as Web Applications, The W3C Workshop on Compound Documents and Web Applications, June 2004.
"XML Digital Signatures", e-doc: The official magazine of AIIM International, Vol. 16, No. 6, December 2002.
"XML 101", e-doc: The official magazine of AIIM International, Vol. 16, No. 6, December 2002.
"XFDL: The Extensible Forms Description Language", Dr. Dobb's Journal, No. 306, December 1999.
Signed XML: Experiences from the Creation of XFDL, XML DSig '99: The W3C Signed XML Workshop, March 1999.
"Digital Signatures with the Microsoft CryptoAPI", Dr. Dobb's Journal, No. 286, June 1998.
"Sorting and Searching Linked Lists in Java", Dr. Dobb's Journal, No. 285, May 1998.
"Resizable Data Structures: Arrays, Heaps, and Hash Tables", Dr. Dobb's Journal, No. 281, January 1998.
"Fast Fibonacci Heaps", Dr. Dobb's Journal, No. 261, January 1997.
Last updated: October 2008