38:
200:
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,
547:
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
1024:"Is there a psychological proximate mechanism for inducing a Trivers–Willard effect in humans? Results of an internet experiment looking at the desired sex composition of children after mortality priming"
1174:
518:
407:
300:
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
278:
215:, 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
1159:
201:
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".
451:
431:
338:
318:
298:
1169:
528:. In a follow-up to this work, Fredman and Willard also showed that similar speedups could be applied to other standard algorithmic problems including
768:
728:
1164:
1144:
544:
1064:
152:(September 19, 1948 – January 21, 2023) was an American computer scientist and logician, and a professor of computer science at the
1084:
651:
1154:
927:
193:
688:
460:
184:
Although trained as a mathematician and employed as a computer scientist, Willard's most highly cited publication is in
952:
343:
1149:
797:
Willard, Dan E. (2001), "Self-verifying axiom systems, the incompleteness theorem and related reflection principles",
1085:"Computing 'fusion trees' to explode barriers: an algorithm that speeds up how fast computers can sort information"
799:
216:
552:
that can survive the potential extinction of mankind, reason consistently, and recognize their own consistency.
543:: systems of logic that have been weakened sufficiently, compared to more commonly studied systems, to prevent
453:. In research originally announced in 1990, Fredman and Willard changed these assumptions by introducing the
1106:
About the Chasm
Separating the Goals of Hilbert's Consistency Program From the Second Incompleteness Theorem
549:
540:
413:. However, it was assumed that integer sorting algorithms would necessarily have a time bound depending on
454:
165:
42:
Portrait of Dan E. Willard for the 2008 University at Albany
President’s Award for Excellence in Research.
766:; Willard, Dan E. (1994), "Trans-dichotomous algorithms for minimum spanning trees and shortest paths",
533:
529:
969:
Simpson, M. J. A.; Simpson, A. E. (1982), "Birth sex ratios and social rank in rhesus monkey mothers",
1023:
245:
1139:
1134:
980:
583:
572:; Willard, D. E. (1973), "Natural selection of parental ability to vary the sex ratio of offspring",
212:
185:
153:
1109:
1004:
832:
816:
664:
615:
599:
227:, data structures for storing and searching sets of small integers with low memory requirements.
172:, earning a master's degree in 1972 and a doctorate in 1978. After leaving Harvard, he worked at
169:
81:
37:
1060:
1054:
996:
607:
574:
988:
971:
808:
777:
737:
697:
656:
591:
132:
99:
69:
828:
749:
709:
433:, and would necessarily be slower than comparison sorting for sufficiently large values of
956:
824:
763:
745:
726:; Willard, Dan E. (1993), "Surpassing the information-theoretic bound with fusion trees",
723:
705:
682:
Willard, Dan E. (1983), "Log-logarithmic worst-case range queries are possible in space Θ(
239:
235:
231:
205:
984:
587:
1080:
649:
Willard, Dan E. (1982), "Maintaining dense sequential files in a dynamic environment",
569:
525:
436:
416:
323:
303:
283:
208:
189:
20:
904:
861:
782:
457:
of computation. In this model, they showed that integer sorting could be done in time
1128:
1050:
741:
701:
410:
54:
668:
619:
1089:
1008:
836:
137:
595:
521:
238:
and related data structures. Before their research, it had long been known that
224:
220:
109:
882:
949:
197:
173:
1000:
660:
611:
548:
speculated that these logical systems will be of importance in developing
820:
603:
168:, graduating in 1970. He went on to graduate studies in mathematics at
917:; birthdate sourced to Willard's doctoral dissertation copyright page.
992:
116:
812:
1114:
928:"Dan Willard Obituary (2023) - Albany, NY - Albany Times Union"
230:
In computer science, Willard is best known for his work with
652:
Proc. 14th ACM Symposium on Theory of
Computing (STOC '82)
176:
for four years before joining the Albany faculty in 1983.
164:
Willard did his undergraduate studies in mathematics at
539:
After 2000, Willard's publications primarily concerned
474:
366:
463:
439:
419:
346:
326:
306:
286:
248:
1175:
Harvard
Graduate School of Arts and Sciences alumni
1056:
Computational
Geometry: Algorithms and Applications
131:
115:
105:
95:
77:
62:
47:
28:
513:{\displaystyle O(n{\tfrac {\log n}{\log \log n}})}
512:
445:
425:
401:
332:
312:
292:
272:
402:{\displaystyle O(n(1+{\tfrac {\log N}{\log n}}))}
211:was one of the predecessors to the technique of
1059:(3rd ed.), Springer-Verlag, p. 116,
863:Predicate-Oriented Database Search Algorithms.
122:Predicate-oriented database search algorithms
635:Predicate-Oriented Database Search Algorithms
8:
36:
25:
1113:
781:
473:
462:
438:
418:
365:
345:
325:
305:
285:
247:
1160:American theoretical computer scientists
196:, that female mammals could control the
853:
769:Journal of Computer and System Sciences
729:Journal of Computer and System Sciences
561:
16:American computer scientist (died 2023)
1031:Society, Biology, & Human Affairs
7:
1170:University at Albany, SUNY faculty
637:, Ph.D. thesis, Harvard University
249:
14:
273:{\displaystyle \Theta (n\log n)}
19:For the railroad executive, see
887:, Mathematics Genealogy Project
545:Gödel's incompleteness theorems
1049:de Berg, M.; van Kreveld, M.;
689:Information Processing Letters
507:
467:
396:
393:
356:
350:
340:could be accomplished in time
267:
252:
204:Willard's 1978 thesis work on
1:
1165:Stony Brook University alumni
783:10.1016/S0022-0000(05)80064-9
1145:American computer scientists
742:10.1016/0022-0000(93)90040-4
702:10.1016/0020-0190(83)90075-3
520:by an algorithm using their
596:10.1126/science.179.4068.90
1191:
1053:; Schwarzkopf, O. (2008),
194:Trivers–Willard hypothesis
188:. In 1973, with biologist
18:
800:Journal of Symbolic Logic
217:order-maintenance problem
143:
88:
35:
1104:Willard, Dan E. (2018),
550:artificial intelligences
192:, Willard published the
633:Willard, D. E. (1978),
541:self-verifying theories
1155:Mathematical logicians
1022:Mathews, Paul (2011),
959:, accessed 2013-06-04.
530:minimum spanning trees
514:
455:transdichotomous model
447:
427:
403:
334:
314:
294:
274:
234:in the early 1990s on
166:Stony Brook University
909:, Library of Congress
661:10.1145/800070.802183
556:Selected publications
515:
448:
428:
404:
335:
315:
295:
275:
655:, pp. 114–121,
524:data structure as a
461:
437:
417:
344:
324:
304:
284:
246:
213:fractional cascading
186:evolutionary biology
160:Education and career
154:University at Albany
985:1982Natur.300..440S
764:Fredman, Michael L.
724:Fredman, Michael L.
588:1973Sci...179...90T
219:, and invented the
1150:American logicians
955:2009-05-09 at the
510:
505:
443:
423:
399:
391:
330:
310:
290:
270:
240:comparison sorting
170:Harvard University
150:Dan Edward Willard
82:Harvard University
51:September 19, 1948
30:Dan Edward Willard
1083:(June 29, 1991),
979:(5891): 440–441,
504:
446:{\displaystyle N}
426:{\displaystyle N}
390:
333:{\displaystyle N}
313:{\displaystyle 1}
293:{\displaystyle n}
280:to sort a set of
147:
146:
90:Scientific career
1182:
1119:
1118:
1117:
1101:
1095:
1093:
1077:
1071:
1069:
1046:
1040:
1038:
1028:
1019:
1013:
1011:
993:10.1038/300440a0
966:
960:
950:Curriculum vitae
947:
941:
940:
939:
938:
924:
918:
916:
915:
914:
901:
895:
894:
893:
892:
879:
873:
872:
871:
870:
858:
841:
839:
794:
788:
786:
785:
760:
754:
752:
720:
714:
712:
679:
673:
671:
646:
640:
638:
630:
624:
622:
566:
519:
517:
516:
511:
506:
503:
486:
475:
452:
450:
449:
444:
432:
430:
429:
424:
408:
406:
405:
400:
392:
389:
378:
367:
339:
337:
336:
331:
319:
317:
316:
311:
299:
297:
296:
291:
279:
277:
276:
271:
133:Doctoral advisor
127:
100:Computer Science
70:Albany, New York
66:January 23, 2023
57:, New York, U.S.
40:
26:
1190:
1189:
1185:
1184:
1183:
1181:
1180:
1179:
1125:
1124:
1123:
1122:
1103:
1102:
1098:
1081:Peterson, Ivars
1079:
1078:
1074:
1067:
1051:Overmars, M. H.
1048:
1047:
1043:
1026:
1021:
1020:
1016:
968:
967:
963:
957:Wayback Machine
948:
944:
936:
934:
926:
925:
921:
912:
910:
906:Willard, Dan E.
903:
902:
898:
890:
888:
881:
880:
876:
868:
866:
860:
859:
855:
850:
845:
844:
813:10.2307/2695030
796:
795:
791:
762:
761:
757:
722:
721:
717:
681:
680:
676:
648:
647:
643:
632:
631:
627:
568:
567:
563:
558:
487:
476:
459:
458:
435:
434:
415:
414:
379:
368:
342:
341:
322:
321:
302:
301:
282:
281:
244:
243:
236:integer sorting
232:Michael Fredman
209:data structures
206:range searching
182:
162:
125:
78:Alma mater
73:
67:
58:
52:
43:
31:
24:
17:
12:
11:
5:
1188:
1186:
1178:
1177:
1172:
1167:
1162:
1157:
1152:
1147:
1142:
1137:
1127:
1126:
1121:
1120:
1096:
1072:
1065:
1041:
1014:
961:
942:
919:
896:
874:
852:
851:
849:
846:
843:
842:
807:(2): 536–596,
789:
776:(3): 533–551,
755:
736:(3): 424–436,
715:
674:
641:
625:
582:(4068): 90–2,
570:Trivers, R. L.
560:
559:
557:
554:
534:shortest paths
526:priority queue
509:
502:
499:
496:
493:
490:
485:
482:
479:
472:
469:
466:
442:
422:
398:
395:
388:
385:
382:
377:
374:
371:
364:
361:
358:
355:
352:
349:
329:
309:
289:
269:
266:
263:
260:
257:
254:
251:
242:required time
190:Robert Trivers
181:
178:
161:
158:
145:
144:
141:
140:
135:
129:
128:
119:
113:
112:
107:
103:
102:
97:
93:
92:
86:
85:
79:
75:
74:
68:
64:
60:
59:
53:
49:
45:
44:
41:
33:
32:
29:
21:Daniel Willard
15:
13:
10:
9:
6:
4:
3:
2:
1187:
1176:
1173:
1171:
1168:
1166:
1163:
1161:
1158:
1156:
1153:
1151:
1148:
1146:
1143:
1141:
1138:
1136:
1133:
1132:
1130:
1116:
1111:
1107:
1100:
1097:
1092:
1091:
1086:
1082:
1076:
1073:
1068:
1066:9783540779735
1062:
1058:
1057:
1052:
1045:
1042:
1036:
1032:
1025:
1018:
1015:
1010:
1006:
1002:
998:
994:
990:
986:
982:
978:
974:
973:
965:
962:
958:
954:
951:
946:
943:
933:
929:
923:
920:
908:
907:
900:
897:
886:
885:
878:
875:
865:
864:
857:
854:
847:
838:
834:
830:
826:
822:
818:
814:
810:
806:
802:
801:
793:
790:
784:
779:
775:
771:
770:
765:
759:
756:
751:
747:
743:
739:
735:
731:
730:
725:
719:
716:
711:
707:
703:
699:
695:
691:
690:
685:
678:
675:
670:
666:
662:
658:
654:
653:
645:
642:
636:
629:
626:
621:
617:
613:
609:
605:
601:
597:
593:
589:
585:
581:
577:
576:
571:
565:
562:
555:
553:
551:
546:
542:
537:
535:
531:
527:
523:
500:
497:
494:
491:
488:
483:
480:
477:
470:
464:
456:
440:
420:
412:
411:radix sorting
386:
383:
380:
375:
372:
369:
362:
359:
353:
347:
327:
307:
287:
264:
261:
258:
255:
241:
237:
233:
228:
226:
222:
218:
214:
210:
207:
202:
199:
195:
191:
187:
180:Contributions
179:
177:
175:
171:
167:
159:
157:
155:
151:
142:
139:
136:
134:
130:
123:
120:
118:
114:
111:
108:
104:
101:
98:
94:
91:
87:
83:
80:
76:
71:
65:
61:
56:
55:New York City
50:
46:
39:
34:
27:
22:
1105:
1099:
1090:Science News
1088:
1075:
1055:
1044:
1034:
1030:
1017:
976:
970:
964:
945:
935:, retrieved
931:
922:
911:, retrieved
905:
899:
889:, retrieved
884:Willard, Dan
883:
877:
867:, retrieved
862:
856:
804:
798:
792:
773:
767:
758:
733:
727:
718:
696:(2): 81–84,
693:
687:
683:
677:
650:
644:
634:
628:
579:
573:
564:
538:
229:
203:
183:
163:
149:
148:
138:Gerald Sacks
121:
106:Institutions
89:
1140:2023 deaths
1135:1948 births
522:fusion tree
225:y-fast trie
221:x-fast trie
110:SUNY Albany
1129:Categories
1115:1807.04717
1037:(2): 11–23
937:2023-03-22
932:Legacy.com
913:2024-02-03
891:2024-02-04
869:2024-02-04
848:References
498:
492:
481:
384:
373:
262:
250:Θ
198:sex ratio
174:Bell Labs
953:Archived
669:15400034
620:29326420
1009:4234180
1001:7144897
981:Bibcode
837:2822314
829:1833464
821:2695030
750:1248864
710:0731126
612:4682135
604:1734960
584:Bibcode
575:Science
1063:
1007:
999:
972:Nature
835:
827:
819:
748:
708:
667:
618:
610:
602:
126:(1979)
124:
117:Thesis
96:Fields
72:, U.S.
1110:arXiv
1027:(PDF)
1005:S2CID
833:S2CID
817:JSTOR
665:S2CID
616:S2CID
600:JSTOR
84:(PhD)
1061:ISBN
997:PMID
686:)",
608:PMID
532:and
223:and
63:Died
48:Born
989:doi
977:300
809:doi
778:doi
738:doi
698:doi
657:doi
592:doi
580:179
495:log
489:log
478:log
409:by
381:log
370:log
320:to
259:log
1131::
1108:,
1087:,
1035:76
1033:,
1029:,
1003:,
995:,
987:,
975:,
930:,
831:,
825:MR
823:,
815:,
805:66
803:,
774:48
772:,
746:MR
744:,
734:47
732:,
706:MR
704:,
694:17
692:,
663:,
614:,
606:,
598:,
590:,
578:,
536:.
156:.
1112::
1094:.
1070:.
1039:.
1012:.
991::
983::
840:.
811::
787:.
780::
753:.
740::
713:.
700::
684:N
672:.
659::
639:.
623:.
594::
586::
508:)
501:n
484:n
471:n
468:(
465:O
441:N
421:N
397:)
394:)
387:n
376:N
363:+
360:1
357:(
354:n
351:(
348:O
328:N
308:1
288:n
268:)
265:n
256:n
253:(
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
