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, databases and (once a long time ago in the early 1970's) sociobiology. 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.

Incidentally, you can gain an approximate understanding of the impact of this work by going to the web site of the Annals on Pure and Applied Logic. This journal is 38-year years old, having been founded in 1970. It maintains a quarterly list of its 25 most downloaded paper. My years 2006 and 2007 articles in APAL have been on this Top 25 List for five of the six most recent quarters. These two articles have usually occupied an upper part in this Top-25 list, having been ranked in position 4 (once), 6 (twice) and 7 (once).

Throughout my career, 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 fifteen favorite ``older'' papers, published before the year 2000. If you wish to gain a more detailed view of my publications, you can click here and retrieve a pdf copy of my resume.

The JSL-2001 article (in the first list) represents the first paper on the historical record to document a type of boundary-case exception for Goedel's Second Incompleteness Theorem. The two papers (with Fredman) were the aspects of my research that were mentioned as the first of six items in the Mathematics and Computer Science Section of the 1991 Annual Report of the National Science Foundation. The Science Magazine article (with Trivers) has had over 1,200 citations recorded in the Science and Social Science Citation Indices. If you wish to gain a general understanding into my research about boundary-case exceptions and generalizations for Goedel's Second Incompleteness Theorem, then I suggest you begin with my years 2002 and 2005 JSL articles. (At the bottom of this home page, I also list some citations to my research in the popular news media.)

Recent Publications during 2000-2007 (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.
"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.
"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.
"Self Verifying Axiom Systems, the Incompleteness Theorem and the Tangibility Reflection Princible" , Journal of Symbolic Logic 66 (2001) pp. 536-596.
"Passive Induction and a Solution to a Paris-Wilkie Open Question" , Annals of Pure and Applied Logic 146 (2007) pp. 124-149.
"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.
"Examining Computational Geometry, Van Emde Boas Trees and Hashing from the Perspective of Fusion Trees" , SIAM Journal on Computing, 29 (2000), pp. 1030-1049.
"An Algorithm for Handling Many Relational Calculus Queries Efficiently" , Journal of Computer and System Sciences 65 (2002) pp. 295-331.
"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.
"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.
"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.
"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.
"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.
"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

Selected List of Fifteen Older Publications (These articles are arranged in approximate order according to the prestige of the journal that they are published in. The ten among these fifteen 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 ", Science, (Jan. 5, 1973), pp. 90-92. (My co-author Robert Trivers, who is now a member of the American Acadmey of Sciences, has very generously made the following unsolicited and gracious remark about our joint paper in one of his books: ``The idea was Dan's''. I mention this fact because there have been over 1,200 citations recorded in the Science and Social Science Citation Indices to this article.) You can find a 5-paragraph laymen's summary about how Trivers-Willard used Darwinian Evolution to predict which parents are more likely to have male offspiring on page 93 of the August 2007 issue of Psychology Today.


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.