Although trained as a mathematician and employed as a computer scientist, Willard's most highly cited publication is in
evolutionary biology. In 1973, with biologist
Robert Trivers, Willard published the
Trivers–Willard hypothesis, that female mammals could control the
sex ratio of their offspring, and that it would be evolutionally advantageous for healthier or higher-status females to have more male offspring and for less healthy or lower-status females to have more female offspring. Controversial at the time, especially because it proposed no mechanism for this control, this theory was later validated through observation, and it has been called "one of the most influential and highly cited papers of 20th century evolutionary biology". Willard's 1978 thesis work on
range searching data structures was one of the predecessors to the technique of
fractional cascading, and throughout the 1980s Willard continued to work on related data structure problems. As well as continuing to work on range searching, he did important early work on the
order-maintenance problem, and invented the
x-fast trie and
y-fast trie, data structures for storing and searching sets of small integers with low memory requirements. In computer science, Willard is best known for his work with
Michael Fredman in the early 1990s on
integer sorting and related data structures. Before their research, it had long been known that
comparison sorting required time \Theta(n\log n) to sort a set of n items, but that faster algorithms were possible if the keys by which the items were sorted could be assumed to be integers of moderate size. For instance, sorting keys in the range from 1 to N could be accomplished in time O(n(1+\tfrac{\log N}{\log n})) by
radix sorting. However, it was assumed that integer sorting algorithms would necessarily have a time bound depending on N, and would necessarily be slower than comparison sorting for sufficiently large values of N. In research originally announced in 1990, Fredman and Willard changed these assumptions by introducing the
transdichotomous model of computation. In this model, they showed that integer sorting could be done in time O(n\tfrac{\log n}{\log\log n}) by an algorithm using their
fusion tree data structure as a
priority queue. In a follow-up to this work, Fredman and Willard also showed that similar speedups could be applied to other standard algorithmic problems including
minimum spanning trees and
shortest paths. After 2000, Willard's publications primarily concerned
self-verifying theories: systems of logic that have been weakened sufficiently, compared to more commonly studied systems, to prevent
Gödel's incompleteness theorems from applying to them. Within these systems, it is possible to prove that the systems themselves are logically consistent, without this deduction leading to the self-contradiction that Gödel's theorem implies for stronger systems. In a preprint summarizing his oeuvre of work in this area, Willard speculated that these logical systems will be of importance in developing
artificial intelligences that can survive the potential extinction of mankind, reason consistently, and recognize their own consistency. ==Selected publications==