Dan Willard Ph.D., Harvard
Professor
dew@cs.albany.edu
Click here to see my Vitae.
Computer Science Department
University at Albany
Albany, NY 12222
(518) 442-4284
(518) 442-5638 (FAX)
Personal Statement of Research
My research has focused on the five areas of mathematical logic (with a concentration in proof theory), the complexity of retrieval algorithms, computational geometry and databases. My work on retrieval algorithms included the development of the fusion tree data structure, which beats the N log N lower bound for sorting and searching. This joint work with Micheal Fredman was the first of just six projects mentioned in the Mathematics and Computer Science section of the 1991 Annual Report of the National Science Foundation. In computational geometry, I have studied mostly range query algorithms, and my work on relational databases has studied applications of the range query formalism.

Recently, I have been doing research in proof theory, in considerable detail. I have developed a class of axiom systems which can verify their own consistency. Goedel's Incompleteness Theorem states such an axiom system can not prove all the theorems of Peano Arithmetic. However, my system can prove more theorems in the $ \Pi_1 $ class than Peano Arithmetic. It is designed to enable computers to recognize their consistency in the very distant future to the same limited extent to which people can recognize their self consistency. I have also developed generalizations of Goedel's Second Incompleteness Theorem that closely complement the boundary-case exceptions to it that I have discovered.

I have published more than 60 articles, most of which are sole-authored. At the bottom of this home page, there are two lists of publications that should give you an over-view of my research. The first list consists of my publications since 2000. The second list consists of my favorite ``older'' papers, published before the year 2000. Each article that I have published since 2000 has a button next to its name so that you can retrieve its pdf file. Also, if you wish to see my vitae, you can click here and retrieve a pdf copy of my resume.

Recent Publications since 2000. (All these articles are sole-authored. They are arranged in approximate order according to the prestige of the journal that they are published in.)
"On the Available Partial Respects in which an Axiomization for Real Valued Arithmetic Can Verify its Own Formal Consistency and Related Topics", Journal of Symbolic Logic 71 (2006) pp. 1189-1199. Click here to retrieve a pdf file
"An Exploration of the Partial Respects in which an Axiom System Recognizing Solely Addition as a Total Function Can Verify Its Own Consistency", Journal of Symbolic Logic 70 (2005) pp. 1171-1209. Click here to retrieve a pdf file
"How to Extend the Semantic Tableaux and Cut-Free Versions of the Second Incompleteness Theorem to Robinson's Arithmetic Q", Journal of Symbolic Logic 67 (2002) pp. 465-496. Click here to retrieve a pdf file
"Self Verifying Axiom Systems, the Incompleteness Theorem and the Tangibility Reflection Princible" , Journal of Symbolic Logic 66 (2001) pp. 536-596. Click here to retrieve a pdf file
"Passive Induction and a Solution to a Paris-Wilkie Open Question" , Annals of Pure and Applied Logic 146 (2007) pp. 124-149. Click here to retrieve a pdf file
"A Generalization of the Second Incompleteness Theorem and Some Exceptions to It" , invited paper in Annals of Pure and Applied Logic 141 (2006) pp. 473-496. Click here to retrieve a pdf file
"Examining Computational Geometry, Van Emde Boas Trees and Hashing from the Perspective of Fusion Trees" , SIAM Journal on Computing, 29 (2000), pp. 1030-1049. Click here to retrieve a pdf file
"An Algorithm for Handling Many Relational Calculus Queries Efficiently" , Journal of Computer and System Sciences 65 (2002) pp. 295-331. Click here to retrieve a pdf file
"Some Specially Formulated Axiomizations for I$\Sigma_0$ Manage to Evade the Herbrandized Version of the Second Incompleteness Theorem", invited paper by Information and Computation 207 (2009) pp. 1078-1093. Click here to retrieve a pdf file
"Some New Exceptions for the Semantic Tableaux Version of the Second Incompleteness Theorem", Automated Reasoning with Analytic Tableaux and Related Methods (2002 Proceedings), Springer-Verlag LNCS 2381, pp. 281-297. Click here to retrieve a pdf file
"The Semantic Tableaux Version of the Second Incompleteness Theorem Extends Almost to Robinson's Arithmetic Q ", Automated Reasoning with Analytic Tableaux and Related Methods (2000 Proceedings), Springer-Verlag LNCS 1847, pp. 415-430. Click here to retrieve a pdf file
"A Version of the Second Incompleteness Theorem For Axiom Systems that Recognize Addition But Not Multiplication as a Total Function", in First Order Logic Revisited, Logos Verlag (Berlin) 2004, pp. 337-368. Click here to retrieve a pdf file
"On the Partial Respects in Which an Axiomization for Real Valued Arithmetic Can Verify its Tableaux Consistency", Automated Reasoning with Analytic Tableaux and Related Methods (2005 Proceedings), Springer-Verlag LNCS 3702, pp. 292-306. Click here to retrieve a pdf file
"The Axiom System I$\Sigma_0$ Manages to Simultaneously Obey and Evade the Herbrandized Version of the Second Incompleteness Theorem", in the Proceedings of Wollics 2006, which are disseminated in Elsevier's Electronic Notes in Theoretical Computer Science 165 (2006) pp.213-226. Click here to retrieve a pdf file
"On the Results of a 14-Year Effort to Generalize Goedel's Second Incompleteness Theorem and Explore Its Partial Exceptions''", Collegium Logicum IX (2007) pp. 81-86 Click here to retrieve a pdf file

Selected List of Older Publications (These articles are arranged in approximate order according to the prestige of the journal that they are published in. Those among these articles, that have no explicit list of authors, are sole-authored papers.)
"Optimal Sampling Residues for Differentiable Data Base Query Problems" Journal of ACM 38 (1991), pp. 104-119.
"Multi-Dimensional Search Trees that Provide New Types of Memory Reduction," Journal of ACM 34 (1987), pp. 846-858.
D. E. Willard and G. S. Lueker, "A Transformation for Adding Range Restriction Capability to Data Structures" Journal of ACM, 32 (1985), pp. 597-618.
B.S. Baker, E.G. Coffman and D. E. Willard, "Algorithms for Resolving Conflicts in Dynamic Storage Allocation ", Journal of ACM, 32 (1985), pp. 327-343
"Log-logarithmic Selection Resolution Protocols in a Multiple Access Channel," SIAM Journal on Computing, 15(1986) 468-477
"New Data Structures for Orthogonal Range Queries," SIAM Journal on Computing, 14(1985) 232-253
"Searching Unindexed and Non-uniformly Generated Files in Log Log N Time," SIAM Journal on Computing, 14(1985) 1013-1029
"Polygon Retrieval," SIAM Journal on Computing, 11 (1982), pp. 149-166
M. L. Fredman and D. E. Willard, "Surpassing The Information Theoretic Barrier with Fusion Trees" (with M. L. Fredman), invited paper in Journal of Computer and System Sciences 47 (1993) pp. 424-433. (The research in this paper was the first of just six projects mentioned in the Mathematics and Computer Science section of the 1991 Annual Report of the National Science Foundation.)
M. L. Fredman and D. E. Willard, "Transdichotomous Algorithms for Minimum Spanning Trees and Shortest Paths" invited paper in Journal of Computer and Systems Sciences 48 (1994) pp. 533-551.
"Applications of Range Query Theory to Relational Database Selection and Join Operations", Journal of Computer and Systems Sciences 52 (1996) pp 157-169.
"New Fast Trie Data Structures Which Support Very Fast Search Operations", Journal of Computer and Systems Sciences 28 (1984) pp 379-395.
"`Log-Logarithmic Worst-Case Range Queries are Possible in Space O(N)", Information Processing Letters 17 (1983), pp. 81-84.
"Self-Verifying Axiom Systems", in Computational Logic and Proof Theory: The Third Kurt Goedel Colloquium Springer-Verlag LNCS 713 (1993), pp. 325-336. (This was my first paper about boundary-case exceptions for Goedel's Second Incompleteness Theorem. It was the predecessor to the more advanced work that I published about this subject in the Journal of Symbolic Logic and Annals of Pure and Applied Logic during the period 2001-2006.)
R. L. Trivers and D. E. Willard, " Natural Selection of Parental Ability to Vary Sex Ratio of Offspring " in Science, (Jan. 5, 1973), pp. 90-92.


Selected Citations to the Fredman-Willard Fusion Trees in the National News Media :
Byte Magazine, August 1991, p. 25.
Computer World, 27 May 1991 (p. 18).
Science News, 29 June 1991 (p. 406).
Information Week, 21 October 1991 (p. 60).
National Science Foundation 1991 Annual Report (page 12). This item was the first of only six topics mentioned in the section entitled ``Mathematics and Computer Science Research (during 1991)''.
NSF Press Release 91-32, 29 April 1991.