Robert B. Ellis, Associate Professor

Applied Mathematics
Illinois Institute of Technology
10 W. 32nd Street
E1 Bldg., Rm. 208
Chicago, IL 60616

Phone: (312) 567-5336
Fax: (312) 567-3135
updated 2/8/2011

Publications and Preprints

Refereed Journals


1.     J. N. Cooper, R. B. Ellis, and A. B. Kahng, “Asymmetric binary covering codes," J. Combin. Th. A, 100 (2002), 232-249 (pdf).

2.     F. R. K. Chung and R. B. Ellis, “A chip-firing game and Dirichlet eigenvalues," Discrete Math. 257 (2002), 341-355 (pdf).

3.     R. B. Ellis and C. H. Yan, “Ulam's pathological liar game with one half-lie," Int. J. Math. Math. Sci. 29 (2004), 1523-1532 (pdf).

4.     R. B. Ellis, V. Ponomarenko, and C. H. Yan, “The Rényi-Ulam pathological liar game with a fixed number of lies," J. Combin. Theory Ser. A, 112 (2005), 328-336 (arXiv, pdf)

5.     R. B. Ellis, X. Jia, and C. H. Yan, “On random points in the unit disk," Random Structures Algorithms 29 (2006), 14-25 (pdf).

6.     R. B. Ellis, J. L. Martin, and C. H. Yan, “Random geometric graph diameter in the unit ball," Algorithmica 47 (2007), 421-438 (arXiV, pdf).  The original publication is available at

7.     R. B. Ellis, “Density of constant radius normal binary covering codes," Discrete Math., 308 (2008), 4446-4459 (special Simonovits issue) (arXiv pdf).

8.     R. B. Ellis, V. Ponomarenko, and C. H. Yan, “How to play the one-lie Rényi-Ulam game," Discrete Math. 308 (2008), 5805-5808 (pdf).

9.     R. B. Ellis and K. L. Nyman, “Two-batch liar games on a general bounded channel," J. Combin. Theory Ser. A 116 (2009), 1253-1270 (pdf, slides).

10.  R. B. Ellis and J. P. Ferry, “Variance of the subgraph count for sparse Erdős-Rényi graphs," Discrete Appl. Math. 158 (2010), 649-658 (pdf, slides).

11.  J. N. Cooper and R. B. Ellis, “Linearly bounded liars, adaptive covering codes, and deterministic random walks," J. Comb. 1 (2010), 307-334 (Joel Spencer special issue) (JoC, arXiv, pdf).

Refereed Conference Proceedings

  1. R. B. Ellis, A. B. Kahng, and Y. Zheng, “Compression algorithms for dummy fill layout data," Proc. SPIE, Vol. 5042, Design and Process Integration for Microelectronic Manufacturing, pp. 233-245, July 2003 (pdf).
  2. R. B. Ellis, J. L. Martin, and C. H. Yan, “Random geometric graph diameter in the unit disk with lp-metric," extended abstract, Lect. Notes Comput. Sc. 3383 (2005), 167-172 (pdf).
  3. J. Bagga, R. Ellis, and D. Ferrero, “The structure of super line graphs," in ISPAN '05: Proceedings of the 8th International Symposium on Parallel Architectures, Algorithms and Networks (2005), 468-471.  (See IEEE Explore for correction to author list posted on first page of the online article, which requires a subscription to view.)
  4. G. Calinescu and R. B. Ellis, “Monitoring schedules for randomly deployed sensor networks," in Proceedings of the DIALM-POMC Joint Workshop on Foundations of Mobile Computing (2008), pp. 3-12.
  5. J. Bagga, R. B. Ellis, and D. Ferrero, “The spectra of super line multigraphs." In: B.D. Acharya, G.O.H. Katona, and J. Nešetřil, eds., Advances in Discrete Mathematics and Applications (Proc. Int. Conf. Discrete Math., ICDM-2008, Mysore, India, 2008), to appear (pdf).

Manuscripts or Work in Progress

  • R. B. Ellis, “Discrete Green's functions for products of regular graphs," manuscript (arXiv, pdf).
  • R. B. Ellis, J. P. Ferry, D. P. Lo, and D. Mubayi, “The block-cutpoint tree characterization of a covering polynomial of a graph," preprint.
  • R. B. Ellis, “Optimal packings within coverings for radius 1 adaptive block codes," in preparation.


  • “Chip-firing games with Dirichlet eigenvalues and discrete Green's functions," Ph.D. Thesis, University of California at San Diego, June 2002 (pdf).
  • “A Kruskal-Katona Theorem for Cubical Complexes," Master's Thesis, Virginia Tech, June 1996 (ps).

Technical Reports

  • Y. DeWoody, R. Ellis, R. Klima, M. Minic, M. Sellers, and J.-M. Yuan, “Examining Randomness of Certain Sequences,” CRSC Industrial Mathematics Modeling Workshop for Graduate Students, Technical Report CRSC-TR97-8, 1997.
  • A. Cintron-Arias, N. Curet, L. Denogean, R. Ellis, C. Gonzalez, S. Oruganti, and P. Quillen, “A Network Diversion Vulnerability Problem,” IMA Mathematical Modeling in Industry Summer 2000 Program for Graduate Students, Technical Report 1752, February 2001 (pdf).
  • R. B. Ellis, A. B. Kahng, and Y. Zheng, “JBIG compression algorithms for `dummy fill' VLSI layout data," Technical Report #CS2002-0709, UCSD CSE Department, 31pp., June 2002 (ps, pdf).