Bio


Gill's research interests are in the areas of computational complexity theory and information theory, including probabilistic computation, lossless data compression, and error correcting codes.

Academic Appointments


Professional Education


  • PhD, University of California, Berkeley, Mathematics (1972)
  • MA, University of California, Berkeley, Mathematics (1969)
  • BS, Georgia Institute of Technology, Applied Mathematics (1967)

2013-14 Courses


Journal Articles


  • Terse, Superterse, and Verbose Sets Information and Computation Beigel, R., Gasarch, W., I., Gill, J., T., Owings Jr., J., C. 1993; 103: 68–85
  • Counting Classes: Thresholds, Parity, Mods, and Fewness Theoretical Computer Science, Special issue devoted to the 1990 STACS. Beigel, R., Gill, J., T. 1992; 103: 3–23
  • Sorting n Objects with a k-Sorter IEEE Transactions on Computers Beigel, R., Gill, J., T. 1990; 39: 714–716
  • Newton’s Method and Ratios of Fibonacci Numbers The Fibonacci Quarterly Gill, J., T., Miller, G. 1981; 19: 1–4
  • Relative to a Random Oracle A, PA ≠ NPA ≠ co − NPA with Probability 1 SIAM Journal on Computing Bennett, C., Gill, J., T. 1981; 10: 96–113
  • Deterministic Simulation of Tape-Bounded Probabilistic Turing Machine Transducers Theoretical Computer Science Gill, J., T., Hunt, J., Simon, J. 1980; 12: 333–338
  • Computational Complexity of Probabilistic Turing Machines SIAM Journal on Computing Gill, J., T. 1977; 6: 675–695
  • The Enumeration of Comparative Probability Relations The Annals of Probability Fine, T., Gill, J., T. 1976; 4: 667–673
  • Relativizations of the P =? NP Question SIAM Journal on Computing Baker, T., Gill, J., T., Solovay, R. 1975; 4: 431–442
  • On Subcreative Sets and S-Reducibility Journal of Symbolic Logic Gill, J., T., Morris, P. 1974; 39: 669–677
  • On Almost Everywhere Complex Recursive Functions Journal of the Association for Computing Machinery Gill, J., T., Blum, M. 1974; 21: 425–435
  • Conjectures on Uniquely Decipherable Codes IEEE Transactions on Information Theory Carter, L., Gill, J., T. 1973; IT-20: 394–396

Books and Book Chapters


  • Ink, Dirty-Tape Turing Machines, and Quasicomplexity Measures Automata, Languages, and Programming Gill, J., T., Simon, I. edited by Michaelson, A., Milner, R. Edinburgh University Press, Edinburgh. 1976: 285–306
  • Some Fruitful Areas for Research into Complexity Theory Computational Complexity Blum, M., Gill, J., T. edited by Rustin, R. Algorithmics Press, New York. 1973: 23–36

Conference Proceedings


  • Computation Complexity of Comparing Real Numbers Sohangir, S., Gill, J., T. 2007
  • Quantization with Joint Entropy/Memory Constraints Gray, R., M., Gill, J., T. 2006
  • Improving Gallager’s Upper Bound on Huffman Codes Redundancy Shen, J., P., Gill, J., T. 2001
  • Computation-Rate-Distortion in Transform Coders for Image Compression Gormish, M., J., Gill, J., T. 1993
  • Upper Bounds on Huffman Codeword Lengths Chu, K., C., Gill, J., T. 1991
  • Codebook Compression for Alphabetic Codes Chu, K., C., Gill, J., T. 1991
  • Mixed-Radix Huffman Codes Chu, K., C., Gill, J., T. 1991
  • An Upper Bound on Huffman Codeword Lengths Chu, K., C., Gill, J., T. 1991
  • Counting Classes: Thresholds, Parity, Mods, and Fewness Beigel, R., Gill, J., T., Hertrampf, U. 1990
  • Semi-Custom VLSI Systems Gamal, A., El, Gill, J., T. 1989
  • On the Huffman Encoding of Infinite Source Alphabets Cot, N., Gill, J., T. 1982
  • Hardware/Software Tradeoffs for Increased Performance Hennessy, J., Jouppi, N., Baskett, F., Gross, T., Gill, J., T. 1982
  • The MIPS Machine Hennessy, J., Jouppi, N., Gill, J., T., Baskett, F., Strong, A., Gross, T. 1982
  • MIPS: A VLSI Processor Architecture Hennessy, J., Jouppi, N., Baskett, F., Gill, J., T. 1981
  • An Electronic Information System Usable by the Blind Fowler, G., Linvill, J., Gill, J., T., Morf, M. 1981
  • Exact and Approximate Membership Testers Carter, L., Floyd, R., Gill, J., T., Markowsky, G., Wegman, M. 1978
  • Polynomial Reducibilities and Upward Diagonalizations Simon, I., Gill, J., T. 1977
  • Bounds on the Cost of Optimal Uniquely Decipherable Codes Cot, N., Gill, J., T. 1977
  • Ink, Dirty-Tape Turing Machines, and Quasicomplexity Measures Gill, J., T., Simon, I. 1976
  • Computational Complexity of Probabilistic Turing Machines Gill, J., T. 1974
  • Probabilistic Turing Machines and Computational Complexity Gill, J., T. 1974
  • Relativizations of the P =?NP Question Baker, T., Gill, J., T., Solovay, R. 1974
  • A Joke about P =?NP Gill, J., T., Ladner, R. 1973
  • Speedups by Probabilistic Computation Gill, J., T. 1973
  • Some Fruitful Areas for Research into Complexity Theory Gill, J., T., Blum, M. 1971