Robert B. Ellis IIT Logo
Associate Professor, Applied Mathematics, IIT
Research Interests  

[spectral] graph theory, combinatorics,

    coding theory, liar games
Random geometric graphs, probabilistic

    methods, algorithm design & analysis

Teaching, Fall 2017

Math 100 Intro to Profession
Math 475 Probability
Math 583 Seminar
All Teaching (Project NExT)

Calakmul Structure I

Curriculum Vitae
(pdf papers)


Applied Mathematics
Illinois Institute of Technology
10 W. 32nd Street

E1 Bldg., Rm. 208

Chicago, IL 60616


Office: E1 105C
Ph.: (312)


Selected Research Papers (complete listing)

1. Linearly bounded liars, adaptive covering codes, and deterministic random walks (arXiv, pdf, slides), J. Comb. 1 (2010), 307-334 (Joel Spencer special issue) (w/Joshua Cooper). Hear Joshua talk about this paper on an episode of Strongly Connected Components (start time 16:04).

2. Variance of the subgraph count for sparse Erdős-Rényi graphs (pdf, slides), Discrete Appl. Math., 158 (2010), 649-658 (w/J.P. Ferry).

3. The spectra of super line multigraphs (pdf), to appear in Advances in Discrete Mathematics and Applications, Acharya, Katona, and Nesetril, eds. (with J. Bagga and D. Ferrero).

4. Two-batch liar games on a general bounded channel (pdf slides), J. Combin. Theory Ser. A 116 (2009), 1253-1270 (w/K. Nyman).

5.  Monitoring Schedules for randomly deployed sensor networks, Proceedings of the DIALM-POMC Joint Workshop on Foundations of Mobile Computing (2008), 3-12 (w/G. Calinescu)

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

Graduate Students

Gergely Balint (PhD S`14), Non-adaptive group testing, Steiner systems, and latin squares

James Panek (MS S`17), Graph partitioning with eigenvectors

Melinda Bulin Clardy (MS S`15), Disjunctness properties resulting from concatenation of group testing matrices

Daniel Tietzer (MS F`11) (Thesis: Adaptive covering codes in the q-ary hypercube, thesis errata, corrected thesis )

James Williamson (MS F`11) (Thesis: Analysis of the application of the liar machine to the q-ary pathological liar game with a focus on lower discrepancy bounds)

Samples of Research Interests

1. Error-correcting codes, covering codes, and liar games: a unified viewpoint (slides from Menger Day 2008)

2. Diameter, path length, and guidelines for routing in random geometric graphs (using probabilistic methods): see Random geometric graph diameter in the unit ball (arXiv pdf).

3. The Probabilistic Method meets combinatorial coding theory:

Asymmetric binary covering codes (ppt slides) (arXiv), JCTA 100, 2002 (with Joshua Cooper and Andrew B. Kahng).

Improved upper bounds (paper #261) on radius 1 cases by David Applegate, Eric Rains, and Neil Sloane

New upper bounds on code sizes by Geoff Exoo and Esa Seuranen

Improved density upper bound by Michael Krivelevich, Benny Sudakov, and Van Vu

Corresponding density of normal binary covering codes (arXiv) (R.B. Ellis)

4. Torus hitting times and Green's functions (html, images)

5. Hearing the shape of a graph via its spectrum (html, images, wav)

Copyright Disclaimer
The author(s) reserve all copyrights to the material posted here, except those which have been given to journals in the course of submission and publication. These preprints may be downloaded for personal academic use only and may not be distributed.

Home | Teaching