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, Spring 2014

Math 230
Math 453
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)
567-5336

 


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 www.springerlink.com.


Graduate Students

Daniel Tietzer (MS F`11) (T hesis: 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