Robert B. Ellis  
Associate Professor, Applied Mathematics, IIT  
Research Interests[spectral] graph theory, combinatorics,
coding theory, liar games methods, algorithm design & analysis 
Teaching, Fall 2019
Math 152 Calculus II 
Applied Mathematics RE Bldg., Rm. 208 Chicago, IL 60616
Office: E1 105C

Selected Research Papers (complete listing)1. Linearly bounded liars, adaptive covering codes, and deterministic random walks (arXiv, pdf, slides), J. Comb. 1 (2010), 307334 (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ősRényi graphs (pdf, slides), Discrete Appl. Math., 158 (2010), 649658 (w/J.P. Ferry). 3. The spectra of super line multigraphs (pdf), In: B.D. Acharya, G.O.H. Katona, and J. Nesetril, eds., Advances in Discrete Mathematics and Applications: Mysore, 2008 (Proc. Int. Conf. Discrete Math., ICDM2008, Mysore, India, 2008), pp.8189. Ramanujan Math. Soc. Lect. Notes Ser., No. 13. Ramanujan Math. Soc., Mysore, India, 2011 (with J. Bagga and D. Ferrero). 4. Twobatch liar games on a general bounded channel (pdf slides), J. Combin. Theory Ser. A 116 (2009), 12531270 (w/K. Nyman). 5. Monitoring Schedules for randomly deployed sensor networks, Proceedings of the DIALMPOMC Joint Workshop on Foundations of Mobile Computing (2008), 312 (w/G. Calinescu) 6. Random geometric graph diameter in the unit ball, Algorithmica 47 (2007), 421438 (arXiv pdf) (with J.L. Martin and C.H. Yan). The original publication is available at www.springerlink.com. 

Graduate StudentsGergely Balint (PhD S`14), Nonadaptive 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 qary hypercube, thesis errata, corrected thesis ) James Williamson (MS F`11) (Thesis: Analysis of the application of the liar machine to the qary pathological liar game with a focus on lower discrepancy bounds) 

Samples of Research Interests1. Errorcorrecting 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 

