Curriculum Vitae
Jeffrey Outlaw Shallit
Citizenship: U. S. (Canadian permanent resident)
Employment
July 2000 - date, Professor, Department of Computer Science, University of Waterloo.
September 1990 - July 2000, Associate Professor (tenured), Department of Computer Science, University of Waterloo.
July 1988 - September 1990: Assistant Professor, Department of Mathematics and Computer Science, Dartmouth College.
September, 1983 - June, 1988: Assistant Professor, Department of Computer Science, University of Chicago.
Education
Ph.D., Mathematics, University of California, Berkeley, June 1983.
Advisor: Manuel Blum.
Dissertation: Metric Theory of Pierce Expansions.
A.B., Mathematics, Princeton University, June 1979, cum laude.
Books Published
(with Eric Bach), Algorithmic Number Theory, Vol. 1: Efficient Algorithms, MIT Press, 1996. Zbl 873.11070
Papers at Refereed Conferences
``An efficient algorithm for computing the ith letter of phi^n (a)'' (with D. Swart), SODA '99, Baltimore, Maryland.
``Polynomial automaticity, context-free languages, and fixed points of morphisms'' (with I. Glaister), MFCS '96, Krakow, Poland.
``Automaticity: Properties of a Measure of Descriptional Complexity'' (with Y. Breitbart), STACS '94, Caen, France.
``Numeration Systems, Linear Recurrences, and Regular Sets'', ICALP '92, Vienna, Austria.
``The ring of k-regular sequences'' (with J.-P. Allouche), STACS '90, Rouen, France.
``Factor Refinement'' (with E. Bach and J. Driscoll), SODA '90, San Francisco.
``A generalization of automatic sequences'', STACS '89, Paderborn, W. Germany.
``Factoring with cyclotomic polynomials'' (with E. Bach), FOCS '85, Portland, Oregon.
``Sums of divisors, perfect numbers, and factoring'' (with E. Bach and G. Miller), STOC '84, Washington, D. C.
Selected Invited Talks
July, 1994: ``Old and New Results on Continued Fractions'', CNTA '94, Halifax, Nova Scotia.
January 10, 1992: ``Real numbers with bounded partial quotients'', MAA Invited Lecture, Annual Joint Meeting of AMS/MAA, Baltimore, Maryland; November 15, 1991: West Virginia University, Mathematics Colloquium; January, 1991: Brown University, Number Theory Seminar; Dalhousie University, Mathematics Colloquium; May 1991: ``Thémate'' Conference, Luminy, France; June 25, 1991: Conference in honor of G. Szekeres, Sydney, Australia; April 1991: University of Vienna, Austria.
August, 1989: ``The ring of k-regular sequences'', Canadian Number Theory Meeting, Vancouver, BC.
August, 1989: ``On the worst case of three algorithms for computing the Jacobi symbol'', Special Session on Computational Number Theory, AMS Summer Meeting, Boulder, Colorado.
November, 1988: ``Fractals, Bitmaps, and APL: Some Intersections'', Toronto APL User's Group.
November, 1986: ``Automates, fractions continues, et pliage de fil de fer'', Séminaire d'Arithmétique et d'Informatique, Université de Bordeaux I.
November, 1985: ``Sur la complexité de fonctions arithmétiques'', Séminaire d'Arithmétique et d'Informatique, Université de Limoges I; December, 1985: Séminaire d'Informatique, INRIA, Rocquencourt, France; Séminaire d'Informatique, Université de Bordeaux I.
September, 1985: ``Sur certains produits liés aux sommes des chiffres'', Analytic Number Theory Conference, Marseille-Luminy.
April, 1985: ``Infinite Products Connected with Sums of Digits'', Number Theory Seminar, University of Illinois at Urbana-Champaign.
February, 1985: ``Cyclotomic Polynomials and Factoring'', Bell Communications Research.
Research Publications
1. ``Predictable regular continued cotangent expansions", J. Res. Nat. Bur. Standards - B. Math. Sciences, 80B (1976), 285-290. Zbl 375.10003
2. ``Simple continued fractions for some irrational numbers", J. Number Theory 11 (1979), 209-217. Zbl 404.10003
3. ``Explicit descriptions of some continued fractions", Fib. Quart. 20 (1982), 77-81. Zbl 472.10012
4. ``Simple continued fractions for some irrational numbers II", J. Number Theory, 14 (1982), 228-231. Zbl 481.10005
5. (with John Hughes) ``On the number of multiplicative partitions", Am. Math. Monthly 90 (1983), 468-471. Zbl 523.10007
6. (with Eric Bach and Gary Miller) ``Sums of divisors, perfect numbers, and factoring", 16th ACM Symp. Theor. Comput. (1984), 183-190; revised version appeared in SIAM J. Comput. 15 (1986), 1143-1154. Zbl 606.10003
7. (with Adi Shamir) ``Number-theoretic functions which are equivalent to number of divisors", Info. Proc. Letters 20 (1985), 151-153. Zbl 576.68028
8. ``On infinite products associated with sums of digits", J. Number Theory 21 (1985), 128-134. Zbl 573.10005
9. (with Eric Bach) ``Factoring with cyclotomic polynomials'', 26th Symposium on Foundations of Computer Science (1985), 443-450; revised version appeared in Mathematics of Computation 52 (1989), 201-219. Zbl 661.10008
10. ``Metric theory of Pierce expansions", Fib. Quart. 24 (1986), 22-40. Zbl 598.10057
11. (with Michael Rabin) ``Randomized algorithms in number theory'', Commun. Pure and Appl. Math. 39 (1986), S239-S256. Zbl 622.10002
12. (with Jean-Paul Allouche, Henri Cohen, and Michel Mendès France) ``De nouveaux curieux produits infinis'', Acta Arithmetica 49 (1987), 141-153. Zbl 584.10024
13. ``A generalization of automatic sequences'', University of Chicago Department of Computer Science Technical Report 87-006, (April 1987); revised version appeared in Theor. Comput. Sci. 61 (1988) 1-16. Zbl 662.68052
14. (with Jean-Paul Allouche) ``Infinite products associated with counting blocks in binary strings'', University of Chicago Department of Computer Science Technical Report 87-017, (November 1987); revised version, J. London Math. Soc., 39 (1989), 193-204. Zbl 629.05004
15. (with Jean-Paul Allouche and Peter Hajnal) ``Analysis of an infinite product algorithm'', University of Chicago Department of Computer Science Technical Report 87-018, (November 1987); revised version appeared in SIAM J. on Discrete Math. 2 (1989), 1-15. Zbl 677.68032
16. (with Michel Mendès France) ``Wire-bending'', J. Combinatorial Theory (Series A), 50 (1989), 1-23. Zbl 663.10056
17. (with Jean-Paul Allouche and J. Betrema) ``Sur des points fixes de morphismes du monoide libre'', RAIRO Informatique 23 (1989), 235-249. Zbl 691.68065
18. ``Appendix to the paper of Salon'', Séminaire de théorie des nombres de Bordeaux, 1986-7, Exposé 4, 4.29.A-4.36.A. Zbl 653.10049
19. ``Two methods for the generation of fractal images'', University of Chicago Department of Computer Science Technical Report 87-010, (June 1987); revised version (with Jorge Stolfi), Computers and Graphics 13 (1989), 185-191.
20. (with David Rubinstein and Mario Szegedy) ``A subset-coloring algorithm and its applications to computer graphics'', University of Chicago Department of Computer Science Technical Report 87-016 (September 1987); revised version appeared in Commun. ACM 31 (1988), 1228-1232.
21. (with John Hughes) ``Wire-bending in n dimensions'', in preparation.
22. (with Michel Mendès France) ``Some planar curves associated with sums of digits'', in preparation.
23. (with Jean-Paul Allouche) ``Sums of digits and the Hurwitz zeta function'', in K. Nagasaka and E. Fouvry, eds., Proc. Japanese-French Symposium Held in Tokyo, Japan, October 10-13, 1988, Lecture Notes in Mathematics #1434, Springer-Verlag, 1990, pp. 19-30. Zbl 711.11003
24. (with Eric Bach and James Driscoll) ``Factor refinement'', Proc. First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1990, pp. 201-211. Zbl 800.68492 Revised version, J. Algorithms 15 (1993), 199-222. Zbl 784.11058
25. ``On the worst case of three algorithms for computing the Jacobi symbol'', J. Symbolic Computation 10 (1990), 593-610. Zbl 715.11072
26. (with J.-P. Allouche and P. Morton) ``Pattern spectra, substring enumeration, and automatic sequences'', Theor. Comput. Sci. 94 (1992), 161-174. Zbl 753.11012
27. (with J.-P. Allouche) ``The ring of k-regular sequences'', Proceedings of STACS 1990, Lecture Notes in Computer Science #415, pp. 12-23. Zbl 742.11012 Revised version in Theor. Comput. Sci. 98 (1992), 163-197. Zbl 774.68072
28. (with A. J. van der Poorten) ``Folded continued fractions'', J. Number Theory 40 (1992), 237-250. Zbl 753.11005
29. (with J. L. Davison) ``Continued fractions for some alternating series'', Monatshefte Math. 111 (1991), 119-126. Zbl 719.11038
30. (with P. Erdös), ``New bounds on the length of finite Pierce and Engel series'', Séminaire de Théorie des Nombres de Bordeaux 3 (1991), 43-53. Zbl 727.11003
31. ``Real numbers with bounded partial quotients: a survey'', L'Enseignement Math. 38 (1992), 151-187. Zbl 753.11006
32. (with P. Enflo, A. Granville, and S. Yu) ``A weakly sparse language L such that LL = Sigma*'', Discrete Applied Mathematics 52 (1994), 275-285. Zbl 813.68124
33. (with A. J. van der Poorten) ``A specialised continued fraction'', University of Waterloo, Computer Science Department, Research Report CS-91-57, October 1991. Revised version in Canad. J. Math. 45 (1993), 1067-1079. Zbl 797.11007
34. (with J.-P. Allouche), ``Complexité des suites de Rudin-Shapiro généralisées'', Journal de Théorie des Nombres de Bordeaux 5 (1993), 283-302. Zbl 817.11014
35. ``Rational numbers with non-terminating, non-periodic modified Engel-type expansions'', University of Waterloo, Computer Science Department, Research Report CS-91-13, April 1991. Also in Fibonacci Quarterly 31 (1993), 37-40. Zbl 773.11045
36. ``Some facts about continued fractions that should be better known'', University of Waterloo, Computer Science Department, Research Report CS-91-30, July 1991.
37. ``Numeration systems, linear recurrences, and regular sets'', University of Waterloo, Computer Science Department, Research Report CS-91-32, July 1991. Extended abstract in Automata, Languages, and Programming: 19th International Colloquium, W. Kuich, ed., Lecture Notes in Computer Science, vol. 623, Springer-Verlag, 1992, pp. 89-100. Revised version in Information and Computation 113 (1994), 331-347. Zbl 810.11006
38. ``On the maximum number of distinct factors in a binary string'', University of Waterloo, Computer Science Department, Research Report CS-91-31, July 1991. Final version in Graphs and Combinatorics 9 (1993), 197-200. Zbl 779.05028
39. ``Description of generalized continued fractions by finite automata'', University of Waterloo, Computer Science Department, Research Report CS-91-44, September 1991.
40. (with D. Wilson), The ``3x+1'' problem and finite automata, Bulletin of the EATCS, No. 46 (February 1992), 182-185. Zbl 757.68084
41. ``Characteristic words as fixed points of homomorphisms'', University of Waterloo, Computer Science Department, Research Report CS-91-72, December 1991.
42. (with H. W. Lenstra, Jr.) ``Continued fractions and linear recurrences'', Math. Comp. 61 (1993), 351-354. Zbl 797.11006
43. (with H. C. Williams) ``Computational number theory before computers'', in Mathematics of Computation 1943-1993: A Half-Century of Computational Mathematics, Walter Gautschi, ed., Proc. Symp. Appl. Math. 48 (1994), 481-531.
44. ``Pierce expansions and rules for the determination of leap years'', Fibonacci Quart. 32 (1994), 416-423. Zbl 823.11043
45. (with J.-P. Allouche, D. Astoorian, and J. Randall), ``Morphisms, squarefree strings, and the Tower of Hanoi puzzle'', Amer. Math. Monthly 101 (1994), 651-658.
46. (with J. Sorenson), ``A binary algorithm for the Jacobi symbol'', ACM SIGSAM Bulletin, 27 (1) (January 1993), 4-11.
47. (with A. Szilard, S. Yu, and K. Zhang), ``Characterizing regular languages with polynomial densities'', Proc. 17th Int'l Symp. Math. Found. Comp. Sci. (MFCS), I. M. Havel and V. Koubek, eds., Lecture Notes in Computer Science, vol. 629, 1992, pp. 494-503.
48. (with J. Sorenson), ``Analysis of a left-shift binary GCD algorithm'', J. Symbolic Computation, 17 (1994), 473-486. Zbl 815.11064
49. (with Y. Breitbart), ``Automaticity: properties of a measure of descriptional complexity'', STACS '94: 11th Annual Symposium on Theoretical Aspects of Computer Science, P. Enjalbert et al., eds., Lecture Notes in Computer Science vol. 775, 1994, pp. 619-630. Revised version, J. Comput. System Sci. 53 (1996), 10-25. Zbl 859.68059
50. ``Origins of the analysis of algorithms'', Historia Mathematica, 21 (1994), 401-419. Zbl 859.01004
51. (with C. Pomerance and J. Robson), ``Automaticity II: Descriptional complexity in the unary case'', Theoret. Comput. Sci. 180 (1997), 181-201. Zbl 959.11015
52. (with F. Morain and H. C. Williams) ``Discovery of a lost factoring machine'', Math. Intelligencer 17(3) (Summer 1995), 41-47. Zbl 842.01006
53. (with S. Lehr and J. Tromp), ``On the vector space of the automatic reals'', in Formal Power Series and Algebraic Combinatorics, 7th Conference, 1995, pp. 351-362. Revised version, Theoret. Comput. Sci. 163 (1996), 193-210. Zbl 874.11029
54. (with I. Glaister), ``Polynomial automaticity, context-free languages, and fixed points of morphisms'', in W. Penczek and A. Szalas, eds., Mathematical Foundations of Computer Science (MFCS '96), Lecture Notes in Computer Science #1113, Springer-Verlag, 1996, pp. 382-393. Zbl 889.68093 Revised version in Computational Complexity 7 (1998), 371-387.
55. (with E. Bach, R. Lukes, and H. C. Williams), ``Results and estimates on pseudopowers'', Math. Comp. 65 (1996), 1737-1747. Zbl 853.11103
56. (with J. Tromp), ``Subword complexity of a generalized Thue-Morse word'', Info. Processing Letters 54 (1995), 313-316. Zbl 875.68596
57. (with I. Glaister), ``A lower bound technique for the size of nondeterministic finite automata'', Info. Proc. Letters 59 (1996), 75-77. Zbl 900.68313
58. ``Automaticity IV: Sets, sequences, and diversity'', J. Theorie des Nombres de Bordeaux 8 (1996), 347-367. Zbl 876.11010
59. (with J. Buss and G. Frandsen), ``Computational complexity of some problems of linear algebra'', BRICS Report Series, Department of Computer Science, University of Aarhus, Denmark, RS-96-33, September 1996. Extended abstract appeared in R. Reischuk and M. Morvan, eds., STACS 97: 14th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science #1200, Springer-Verlag, 1997, pp. 451-462. Final version in J. Comput. Syst. Sci. 58 (1999), 572-596. Zbl 941.68059
60. (with J.-P. Allouche, A. Lubiw, M. Mendès France, and A. van der Poorten) ``Convergents of folded continued fractions'', Acta Arithmetica 77 (1996), 77-96. Zbl 848.11004
61. (with F. Morain and H. C. Williams), ``La machine à congruences'', La Revue, Musée des Arts et Métiers (Paris), 14 (March 1996), 14-19.
62. (with J.-P. Allouche, E. Cateland, H.-O. Peitgen, and G. Skordev) ``Automatic maps on a semiring with digits'', Fractals 3 (1995), 663-677. Zbl 879.11010
63. (with J.-P. Allouche, E. Cateland, W. J. Gilbert, H.-O. Peitgen, and G. Skordev), ``Automatic maps in exotic numeration systems'', Theory Comput. Syst. 30 (1997), 285-331. Zbl 870.68105
63. ``Public networks and censorship'', in High Noon on the Electronic Frontier, Peter Ludlow, ed., MIT Press, 1996, pp. 275-289.
64. (with J. C. Lagarias) ``Linear fractional transformations of continued fractions with bounded partial quotients'', Journal de Théorie des Nombres de Bordeaux 9 (1997), 267-279. MR 99c:11088. Zbl 901.11024
65. (with J.-P. Allouche and J. Currie), ``Extremal infinite overlap-free binary words", Electronic Journal of Combinatorics 5(1) (1998), \#R27. Zbl 890.68107
66. (with M.-w. Wang) ``On minimal words with given subword complexity", Electronic Journal of Combinatorics 5 (1) (1998), \#R35. MR 99g:68159 Zbl 898.68058
67. (with D. Swart) ``An efficient algorithm for computing the ith letter of phi^n (a)'', Proc. 10th ACM-SIAM Symp. on Discrete Algorithms, 1999, pp. 768-775. Zbl 931.68141
68. (with Jean-Paul Allouche) ``Sums of digits, overlaps, and palindromes'', Disc. Math. Theoret. Comput. Sci. 4 (2000), 1-10.
69. (with Charles Lam and Scott Vanstone) ``Worst-case analysis of an algorithm for computing the greatest common divisor of n inputs'', in J. Buchmann, T. Hoholdt, H. Stichtentoth, and H. Tapia-Recillas, eds., Coding Theory, Cryptography and Related Areas, Springer-Verlag, 2000, 156-166.
70. ``Automaticity and rationality'', J. Automata, Languages, and Computation 5 (2000), 255-268.
71. (with James Currie, Holger Petersen, and J. M. Robson) ``Separating words with small grammars'',J. Autom. Lang. Comb. 4 (1999), 101-110. Zbl 937.68070
72. (with M.-w. Wang) ``An inequality for non-negative matrices'', Linear Algebra Appl. 290 (1999), 135-144. Zbl 930.15020
73. (with J.-P. Allouche) ``Generalized perturbed symmetry'', European J. Combinat. 19 (1998), 401-411. Zbl 918.11015
74. "Minimal primes", J. Recreational Math. 30 (2) (1999-2000), 113-117.
75. (with M. Mendes France and A. J. van der Poorten) ``On lacunary formal power series and their continued fraction expansion'', in Gyory and Kalman, eds., Number Theory in Progress, de Gruyter, 1999, pp. 321-326. Zbl 929.11011
76. (with H. C. Williams) "Factoring integers before computers", in W. Gautschi, editor, Mathematics of Computation, 1943-1993: a Half-Century of Computational Mathematics, pp. 481-531. Zbl 847.11002
77. (with G. Pighizzini), Unary language operations, state complexity, and Jacobsthal's function, Int'l. J. Found. Comput. Sci. 13 (2002), 145-159.
78. (with G. Pighizzini and M. Domaratzki) "Simulating finite automata with context-free grammars", Info. Proc. Letters 84 (2002), 339-344.
Technical Reports and Other Publications
1. ``A simple proof that phi is irrational", Fib. Quart., 13 (1975), 32. Zbl 295.10026
2. ``An interesting continued fraction", Math. Mag., 48 (1975), 207-211. Zbl 313.10009
3. ``Calculation of phi and sqrt(5) to 10,000 decimal places", reviewed in Math. Comp. 30 (1976), 377.
4. ``The prime factorization of 1", APL Quote Quad 6 (4) (Winter 1976), 36-37.
5. (with David Rosen) ``A continued fraction algorithm for approximating all real polynomial roots", Math. Mag. 51 (1978), 112-116. Zbl 403.65014
6. ``Table of Bell numbers to B(400)", reviewed in Math. Comp. 32 (1978), 656.
7. ``A triangle for the Bell numbers", in A Collection of Manuscripts Related to the Fibonacci Sequence, Verner E. Hoggatt, Jr. and Marjorie Bicknell-Johnson, eds., Fibonacci Association, Santa Clara, Ca. 1980, pp. 69-71. Zbl 515.10011
8. (with Eugene McDonnell) ``Extending APL to infinity", Proc. APL 80 Int'l Conf. North-Holland, Amsterdam, 1980, pp. 123-132.
9. ``Resolution of algebraic rational functions into partial fractions", Algorithm 140, APL Quote-Quad, 10 (3) (March 1980), 28-29.
10. ``Infinite arrays and diagonalization", Proc. APL 81 Conf., APL Quote-Quad 12 (1) (September 1981), 281-285.
11. ``V-partitions and permutations by inversions", APL Quote Quad 12 (3) (March 1982), 15-17.
12. ``Discriminant of a polynomial in one variable over the integers", APL Quote Quad 12 (4) (June 1982), 11-12.
13. ``Computational simplicial homology in APL", APL 82 Conf. Proc., APL Quote Quad, 13 (1) (September 1982), 332-338.
14. ``Merrily we roll along: some aspects of ?", APL 83 Conf. Proc., APL Quote Quad, 13 (3) (March 1983), 243-249.
15. ``Some predictable Pierce expansions", Fib. Quart. 22 (1984), 332-335. Zbl 546.10005
16. (with Jon Yamron) ``On linear recurrences and divisibility by primes", Fib. Quart. 22 (1984), 366-368. Zbl 547.10007
17. ``A simple proof of the Lucas-Lehmer primality test'', Univ. of Chicago Department of Computer Science, Technical Report 84-002, April 1984.
18. ``An application of the Lenstra-Lenstra-Lovász algorithm to the solution of a Diophantine equation'', Univ. of Chicago, Department of Computer Science, Technical Report 84-003, May 1984.
19. ``An exposition of Pollard's algorithm for quadratic congruences'', University of Chicago Technical Report 84-006, December, 1984.
20. (with Eric Bach) ``A class of functions equivalent to factoring'', University of Chicago Technical Report 84-008, December, 1984.
21. ``Random polynomial time algorithms for sums of squares'', University of Chicago Technical Report 85-001, January, 1985.
22. ``Sur certains produits infinis liés aux sommes des chiffres'', Groupe d'étude en théorie analytique des nombres, Institut Henri Poincaré, Paris, 1985/6, 3.01-3.05.
23. ``Sur la complexité de fonctions arithmétiques'', Seminaire de Théorie des Nombres, Université de Bordeaux I, 1985-6, 1.01-1.06. Zbl 606.10002
24. ``Automates finis, pliage de fil de fer, et fractions continues'', Séminaire de théorie des nombres de Bordeaux, 1986-7, pp. 1-13.
25. ``Fractals, bitmaps, and APL'', APL Quote-Quad 18 (3) (March 1988), 24-32.
26. ``A note on the relative complexity of sigmak(n) and d(n)'', University of Chicago, Department of Computer Science, Technical Report 88-001, January 1988.
27. Book review of Higher Superstition, in Skeptic 3 (1) (1994), 98-100.
28. Book review of God: The Evidence, in Skeptic 6 (2) (1998), 80-82.
Problems Proposed
Courses Taught
Introduction to Computer Science, Data Structures, Finite Automata and Formal Languages, Computer Graphics, Algorithmic Number Theory, Software Engineering, Formal Languages and Parsing, Formal Languages and Number Theory.
Professional Activities
Referee
SIGGRAPH '89
CNTA '91
International Journal of Algebra and Computation
Information Processing Letters
Mathematics of Computation
Discrete Mathematics
Journal of the Australian Mathematical Society
Journal of the American Mathematical Society
Proceedings of the American Mathematical Society
Theoretical Computer Science
IEEE Transactions on Information Theory
Mathematical Reviews
Journal of Number Theory
American Mathematical Monthly
SIAM Journal on Computing
Utilitas Mathematica
Pattern Recognition Letters
Fibonacci Quarterly
The Information Society
Assistant Editor, Problems Section, American Mathematical Monthly
Editorial Board, Séminaire de Théorie des Nombres de Bordeaux
Member: AMS, ACM, SIGACT, SIGAPL, EATCS, EFF.