Joseph Douglas (Joe) HORTON Professor
Address :       Tel : Fax : office : email :	Faculty of Computer Science, University of New Brunswick P.O. Box 4400, Fredericton, N.B. CANADA (506) 447-3336 (506) 453-3566 E12c, Head Hall jdh@unb.ca

Research Interests:Design and analysis of algorithms, graph theory, combinatorics, automated reasoning, network scheduling, complexity .... My most recent research interest is the Simulation Of Consciousness In Artifical Life : the SOCIAL project. Here is the tech-report which I wrote to start the project. I now (2011) have three graduate students working on it.

Topics for CS4997: An incomplete list 2010:

• Develop an artificial universe inhabited by "bugs" that evolve new attributes. This may require working as part of a team with graduate students.
• Enumerate all "pedigrees" (family trees) with specified characteristics. We would like to be able to generate such pedigrees with equal probability to use in running experiments of haplotype determination algorithms and finding mutations/crossovers, given genotype data of the individuals.
• Consider how to find the minimum cycle base of a directed graph.
• Implement a new algorithm to solve the SAT problem, or rather the UNSAT problem. The algorithm I have in mind is related to the merge depth of proofs (see below). If it works well, maybe we could enter the SAT competition.
• Develop some interactive game that explores some unusual physical universe, such as: four dimensions, special relativity (ie slow speed of light), or a universe in which quantum mechanics is apparent.

Clause trees: Work with Bruce Spencer. We have developed a new data structure for automated reasoning, the clause tree. Many old algorithms for automated reasoning become easier to understand when viewed as manipulating clause trees. Moreover new tighter algorithms can be defined. The method is useful in solving any problem to which automated reasoning can be applied, from an improved automated theorem proving tool to aid mathematicians (probable), to helping prove programs correct (a long shot). It may be beneficial in proving the security levels of computer systems.

An introduction to clause trees is given in our 1997 paper in Artificial Intelligence. Some details about how to implement them are given in our 2000 paper in the Journal of Automated Reasoning. Implementation seems to be a big problem; we do not have a good efficient implementation.

Complexity:I have a incomplete paper using clause trees. The main results so far are:

• Define merge depth for clause trees and unsatisfiable sets of clauses. A clause tree has merge depth d if the longest chain of merge paths that precede one another is length d. A set of clauses has merge depth d if the closed clause tree on the set with the smallest merge depth has merge depth d.
• Exact exponential bounds on the size of the smallest clause tree on a minimal unsatisfiable set of clauses, given the number of variables and the merge depth of the set.
• The merge depth of clauses can be linear in the number of variables plus number of clauses, using results from Chvatal-Szemeredi, JACM vol.35 pp759-768, 1988. This gives a somewhat different proof that treelike resolution is exponential.
• A simple observation is that the length of the smallest treelike extended resolution proof is polynomial in the length of the smallest extended resolution proof.

The ambitious goal is to show that the size of the smallest proof using extended resolution is exponential (or not).

Haplotype determination: My most recent paper is joint work with my colleague Patricia Evans, and her doctoral student Duong Doan. We have a fast implemented algorithm to determine the haplotypes given the genotype data for the members of an extended family of dyploid individuals. There are many ways in which this research can be extended.

Cycle bases: I have had several results on finding the minimum cycle bases of graphs. The directed case problem has also been considered, but I think that the extension to directed graphs should be done differently than what is in the literature.

Other Research Interests

My original field of research was combinatorial design, an area in which I rarely publish anymore. Three of my papers were published in 1991 in this area.

After completing my Ph.D., I became very interested in graph theory. I found the first known non-hamilton bipartite cubic graph, which was called the Horton graph in the textbook by Bondy and Murty, and the first hypotraceable graph. Perhaps my best work in this area was with Izak Bouwer on symmetric graphs. The joint work with my masters student Kyriakos Kilakos on minimum edge dominating sets is cited more often.

After coming to UNB in 1981, I became interested in Algorithm Analysis. The most important result here, and the paper that has generated the most citations for me, has been the discovery of a polynomial-time algorithm to find the shortest cycle basis of graph. This result has applications in many areas of Mathematics, Engineering and the Sciences.

The other paper of mine that has generated a large number of citations was a partial solution to an old combinatorial geometry problem. I constructed an infinite set of points in the plane in which any set of seven points that formed a convex 7-gon must contain other points inside the 7-gon. This set of points is now often called the horton set.

Selected Publications

• J.D. Horton, R.C. Mullin, and R.G. Stanton, 1971, "A Recursive Construction for Room Designs", Aequationes Mathematicae 6, 39-45.
• J.D. Horton, 1974, "Sublatin Squares and Incomplete Orthogonal Arrays", J. Combinatorial Theory A 16, 23-33.
• J.D. Horton, 1981, "Room Designs and One-Factorizations", Aequationes Mathematicae 22, 56-63.
• J.D. Horton, 1983, "Sets with no empty convex 7-gons", Canadian Mathematical Bulletin, 26, 482-484.
• J.D. Horton, 1987, "A Polynomial Time Algorithm to Find the Shortest Cycle Basis of a Graph", SIAM J. on Computing, 16, 358-366.
• J.D. Horton and I. Z. Bouwer, 1991, "Symmetric Y-graphs and H-graphs", J. Combinatorial Theory B, 53, 114-129.
• J. D. Horton and K. Kilakos, 1993, "Minimum Edge Dominating Sets", SIAM J. Discrete Math, 6, 375-387.
• J. D. Horton, R. Harland, E. Ashby, R. H. Cooper, W. F. Hyslop, B. G. Nickerson, W. M. Stewart, O. K. Ward, 1993,"The Cascade Vulnerability Problem", J. Computer Security, 2, 279-290.
• J. D. Horton and Bruce Spencer, 1997, "Clause trees: a tool for understanding and implementing resolution in automated reasoning", Artificial Intelligence, 92, 25-89.
• Bruce Spencer and J. D. Horton, 2000, Efficient Algorithms to Detect and Restore Minimality, an Extension of the Regular Restriction of Resolution, Journal of Automated Reasoning, 25(2000), 1-34.
• Joseph D. Horton, Alejandro Lopez-Ortiz, 2003, On the Number of Distributed Measurement Points for Network Tomography, IMC-03, Proceedings ACM SIGCOMM Conference on Internet Measurement held in Miami, Florida, October 27-29, 2003, 204-209.
• Duong Doan, Patricia Evans, and Joseph D. Horton, A Near-Linear Time Algorithm for Haplotype Determination on General Pedigrees, submitted June 15, 2009 (41 pages).
• List of Publications

• In the Fall term 2011, I am teaching CS4935/6991, advanced algorithms
• In the winter of 2012 I will be teaching MATH3343, Networks and graphs.
• Intersession 2012 I teach CS2333 Computability and Formal Languages.

• The Canadian Mathematical Society (life member)
• Association for Computing Machinery - SIGACT
• Foundation Fellow of the Institute of Combinatorics and its Applications
• Association for the Advancement of Artificial Intelligence (life member)

• Hold the rank of FIDE Master at chess (Atlantic Canada Champion 1984, 1992, 1996). In terms of quality of play, my best tournament was in the Canadian Closed Championship 1984, although I ended with a slightly negative score (6-8). My best result was in 1992 when I scored fifty percent, but had two lucky wins. I was totally crushed in 1996.
• I sing in choirs and a barbershop chorus.
• I used to play the piano and recorder.

Document: http://www.cs.unb.ca/profs/horton/
Last Revision: Nov. 15, 2011.