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

  • Emeritus Faculty, Acad Council, Electrical Engineering

Professional Education

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

Contact

  • Academic
    gill@stanford.edu
    University - Emeritus faculty Department: Electrical Engineering Position: Emeritus Faculty, Acad Council
    • David Packard Electrical Engineering #275
    • Stanford,  California  94305-9510 

Additional Info

Links

2021-22 Courses

All Publications

  • Fused Fibonacci Like (p,q)-Sequences with Compression and Barcoding Applications Conference on Multimedia on Mobile Devices and Multimedia Content Access - Algorithms and Systems VI Agaian, S., Garcia, J., Abdul-Kafi, S., Gill, J. T. SPIE-INT SOC OPTICAL ENGINEERING. 2012

    View details for DOI 10.1117/12.905353

    View details for Web of Science ID 000303344200012

  • Low-Complexity Non-Uniform Demand Multicast Network Coding Problems 47th Annual Allerton Conference on Communication, Control, and Computing Koo, J. C., Gill, J. T. IEEE. 2009: 228–235

    View details for Web of Science ID 000279627100032

  • Lagrangian vector quantization with combined entropy and codebook size constraints IEEE TRANSACTIONS ON INFORMATION THEORY Gray, R. M., Linder, T., Gill, J. T. 2008; 54 (5): 2220-2242

    View details for DOI 10.1109/TIT.2008.920205

    View details for Web of Science ID 000255505700022

  • Computation Complexity of Comparing Real Numbers Sohangir, S., Gill, J., T. 2007
  • Quantization with joint entropy/memory constraints 16th Data Compression Conference Gray, R. M., Gill, J. T. IEEE COMPUTER SOC. 2006: 223–232

    View details for Web of Science ID 000236995300023

  • 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
  • A new upper bound on the data expansion of Huffman codes IEEE International Symposium on Information Theory Shen, J. P., Gill, J. IEEE. 2000: 372–372

    View details for Web of Science ID 000168322900368

  • Analysis on a hidden Markov channel model IEEE Global Communications Conference (GLOBECOM 99) Shen, J. P., Gill, J. IEEE. 1999: 437–441

    View details for Web of Science ID 000089882700080

  • Smart photonic networks and computer security for image data Conference on Multimedia Networks - Security, Displays, Terminals, and Gateways Campello, J., GILL, J. T., Morf, M., Flynn, M. J. SPIE - INT SOC OPTICAL ENGINEERING. 1998: 272–279

    View details for Web of Science ID 000072275600027

  • TERSE, SUPERTERSE, AND VERBOSE SETS INFORMATION AND COMPUTATION Beigel, R., Gasarch, W. I., Gill, J., OWINGS, J. C. 1993; 103 (1): 68-85

    View details for Web of Science ID A1993KW35700003

  • Computation-Rate-Distortion in Transform Coders for Image Compression Gormish, M., J., Gill, J., T. 1993
  • 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 7TH ANNUAL SYMP ON THEORETICAL ASPECTS OF COMPUTER SCIENCE ( STACS 90 ) Beigel, R., Gill, J. ELSEVIER SCIENCE BV. 1992: 3–23

    View details for Web of Science ID A1992JJ69400002

  • 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
  • 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 LECTURE NOTES IN COMPUTER SCIENCE Beigel, R., Gill, J., Hertrampf, U. 1990; 415: 49-57

    View details for Web of Science ID A1990CZ43600005

  • Counting Classes: Thresholds, Parity, Mods, and Fewness Beigel, R., Gill, J., T., Hertrampf, U. 1990
  • Sorting n Objects with a k-Sorter IEEE Transactions on Computers Beigel, R., Gill, J., T. 1990; 39: 714–716
  • 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
  • NEWTONS METHOD AND RATIOS OF FIBONACCI NUMBERS FIBONACCI QUARTERLY Gill, J., Miller, G. 1981; 19 (1): 1-4

    View details for Web of Science ID A1981LG18300001

  • 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
  • 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
  • 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 NOT-EQUAL NPA NOT-EQUAL CO-NPA WITH PROBABILITY-1 SIAM JOURNAL ON COMPUTING Bennett, C. H., Gill, J. 1981; 10 (1): 96-113

    View details for Web of Science ID A1981LG91500008

  • Deterministic Simulation of Tape-Bounded Probabilistic Turing Machine Transducers Theoretical Computer Science Gill, J., T., Hunt, J., Simon, J. 1980; 12: 333–338
  • Exact and Approximate Membership Testers Carter, L., Floyd, R., Gill, J., T., Markowsky, G., Wegman, M. 1978
  • COMPUTATIONAL COMPLEXITY OF PROBABILISTIC TURING MACHINES SIAM JOURNAL ON COMPUTING Gill, J. 1977; 6 (4): 675-695

    View details for Web of Science ID A1977EC60000006

  • Computational Complexity of Probabilistic Turing Machines SIAM Journal on Computing Gill, J., T. 1977; 6: 675–695
  • Bounds on the Cost of Optimal Uniquely Decipherable Codes Cot, N., Gill, J., T. 1977
  • Polynomial Reducibilities and Upward Diagonalizations Simon, I., Gill, J., T. 1977
  • The Enumeration of Comparative Probability Relations The Annals of Probability Fine, T., Gill, J., T. 1976; 4: 667–673
  • Ink, Dirty-Tape Turing Machines, and Quasicomplexity Measures Gill, J., T., Simon, I. 1976
  • 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
  • Relativizations of the P =? NP Question SIAM Journal on Computing Baker, T., Gill, J., T., Solovay, R. 1975; 4: 431–442
  • SUBCREATIVE SETS AND S-REDUCIBILITY JOURNAL OF SYMBOLIC LOGIC GILL, J. T., Morris, P. H. 1974; 39 (4): 669-677

    View details for Web of Science ID A1974V176900007

  • On Subcreative Sets and S-Reducibility Journal of Symbolic Logic Gill, J., T., Morris, P. 1974; 39: 669–677
  • Probabilistic Turing Machines and Computational Complexity Gill, J., T. 1974
  • Relativizations of the P =?NP Question Baker, T., Gill, J., T., Solovay, R. 1974
  • On Almost Everywhere Complex Recursive Functions Journal of the Association for Computing Machinery Gill, J., T., Blum, M. 1974; 21: 425–435
  • Computational Complexity of Probabilistic Turing Machines Gill, J., T. 1974
  • ALMOST EVERYWHERE COMPLEX RECURSIVE FUNCTIONS JOURNAL OF THE ACM Gill, J., Blum, M. 1974; 21 (3): 425-435

    View details for Web of Science ID A1974T573100008

  • Conjectures on Uniquely Decipherable Codes IEEE Transactions on Information Theory Carter, L., Gill, J., T. 1973; IT-20: 394–396
  • 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 Computational Complexity Blum, M., Gill, J., T. edited by Rustin, R. Algorithmics Press, New York. 1973: 23–36
  • Some Fruitful Areas for Research into Complexity Theory Gill, J., T., Blum, M. 1971
https://orcid.org/0000-0001-6200-0872