Robert B. Ellis, Assistant 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

URL: http://math.iit.edu/~rellis/
updated 3/5/06

Research Interests / Degrees Awarded / Professional Experience / Awards&Grants / Publications&Preprints / Undergraduate Research Directed / Talks / Posters / Activities&Service / Teaching / Workshops&Conferences / References

Research Interests

Graph theory: random geometric graphs, spectral graph theory;
Combinatorics: probabilistic methods, coding theory, Renyi-Ulam games, combinatorial optimization, algorithm design & analysis


Education

June, 2002 

Ph.D., Mathematics, UC San Diego;  Advisor: Fan Chung Graham

July, 1996

M.S., Mathematics, Virginia Tech;     Advisor: Clara Chan

Dec., 1994

B.S., Mathematics, Virginia Tech


Professional Experience

8/05-present Assistant Professor, Illinois Institute of Technology Department of Applied Mathematics

9/02-7/05

NSF VIGRE Postdoctoral Fellow, Texas A&M Department of Mathematics
Research mentor: Catherine Yan

1996-2002

University of California San Diego Department of Mathematics
Research Assistant (6 quarters) for Fan Chung, T. C. Hu and A. B. Kahng
Teaching Assistant (15 quarters)
Co-founder and co-administrator, Graduate Mathematics Consulting Group

1995-96

Virginia Tech Department of Mathematics
Instructor (2 semesters)                 Teaching Assistant (2 semesters)


Awards/Grants

  1. National Security Agency Young Investigator Grant, 2007-2008

  2. Air Force Research Laboratory TANGRAM Grant, 2007-2009

  3. Project NExT 2005-6 Fellow (Sterling dot), sponsored by the AMS and IIT Applied Mathematics

  4. VIGRE Postdoctoral Fellowship, National Science Foundation, 2002-2005

  5. Support grants to attend DIMACS/DIMATIA/Renyi Combinatorial Challenges Conference, CBMS San Marcos 2004, Geometry Day 2003, Spectral Analysis in Geometry and Physics 2003, CombinaTexas 2003, IMA Mathematical Modeling workshops 1996 and 2000


Publications and Preprints

  1. Asymmetric binary covering codes (pdf), J. Combin. Theory Ser. A 100 (2002), 232--249 (with Joshua Cooper and Andrew Kahng).

  2. A chip-firing game and Dirichlet eigenvalues (pdf),  Discrete Mathematics 257 (2002), 341--355 (with Fan Chung Graham).

  3. Ulam's pathological liar game with one half-lie (pdf), Int. J. Math. Math. Sci. 29 (2004), 1523--1532 (with Catherine Yan).

  4. The Renyi-Ulam pathological liar game with a fixed number of lies (arXiv pdf), J. Combin. Theory Ser. A 112 (2005), 328-336 (with Vadim Ponomarenko and Catherine Yan).

  5. Random geometric graph diameter in the unit disk with lpmetric (extended abstract) (pdf), Lect. Notes Comput. Sc. 3383 (2005), 167--172 (with Jeremy Martin and Catherine Yan). © Springer-Verlag .

  6. Compression Algorithms for dummy fill layout data, Proc. SPIE, Vol. 5042, Design and Process Integration for Microelectronic Manufacturing, pp. 233--245, July 2003 (with Andrew B. Kahng and Yuhong Zheng).

  7. Random geometric graph diameter in the unit ball (arXiV, pdf), Algorithmica 47 (2007) 421-438 (with Jeremy Martin and Catherine Yan). The original publication is available at www.springerlink.com.

  8. On Random Points in the Unit Disk (pdf), Random Structures Algorithms, 29 (2006), 13-25 (with Xingde Jia and Catherine Yan).

  9. Density of normal binary covering codes (arXiv pdf), Discrete Math., 308 (2008) 4446-4459 (special Simonovits issue)

  10. How to Play the One-Lie Renyi-Ulam Game (pdf), to appear in Discrete Math. (with Vadim Ponomarenko and Catherine Yan).

  11. Monitoring Schedules for randomly deployed sensor networks, accepted by DialM-POMC'08, (with Gruia Calinescu).

  12. Two-batch liar games over a general bounded channel, submitted (with Kathryn Nyman).

  13. Variance of the subgraph count for Erdos-Renyi graphs, submitted (with James P. Ferry).

  14. Discrete Green's functions for products of regular graphs (arXiv, pdf),  preprint.

  15. Optimal packings within coverings for radius 1 adaptive block codes, in preparation.

  16. An exact algorithm for binary radius 1 adaptive asymmetric covering codes, in preparation (with Justin Wilson).

  17. Approximating the lp-metric by path distance in a random geometric graph, in preparation.

  18. The spectra of super-line multigraphs, in preparation (with Daniela Ferrero).

Theses

  1. Chip-firing games with Dirichlet eigenvalues and discrete Green's functions (pdf), Ph.D. Thesis, University of California at San Diego, June 2002.

  2. A Kruskal-Katona Theorem for Cubical Complexes (ps), Master's Thesis, Virginia Tech,  June 1996.

Reports

  1. JBIG Compression Algorithms for "Dummy Fill" VLSI Layout Data, (ps,pdf) CS2002-0709, June 2002 (with Andrew Kahng and Yuhong Zheng).

  2. A Network Diversion Vulnerability Problem (pdf), IMA Mathematical Modeling in Industry Summer 2000 Program for Graduate Students, University of Minnesota, Technical Report 1752, February 2001. (with Ariel Cintron-Arias, Norman Curet, Lisa Denogean, Corey Gonzalez, Shobha Oruganti, and Patrick Quillen)

  3. Examining Randomness of Certain Sequences, CRSC Industrial Mathematics Modeling Workshop for Graduate Students, North Carolina State University, Technical Report CRSC-TR97-8, 1997. (with Yssa DeWoody, Richard Klima, Michael Minic, Mark Sellers, and Juan-Ming Yuan)


Undergraduate Research Directed

  1. Justin Wilson, Renyi-Ulam liar games with 1 half-lie, Summer 2004-Summer 2005.

  2. Brian Worthen and David Mendoza, optimal strategies for the Renyi-Ulam pathological liar game with a fixed number of lies, Fall 2003-Spring 2004.


Talks

  1. "Multichannel liar games with a fixed number of lies," (slides) invited talk, Liar Games and Error-Correcting Codes Minisymposium, SIAM Conference on Discrete Mathematics, Victoria, June 2006; contributed talk, Sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Prague, July 2006.

  2. "Packings within coverings for adaptive radius 1 codes," contributed talk, DIMACS/DIMATIA/Renyi Combinatorial Challenges, Rutgers University, April 2006; CombinaTexas `06, Houston, February 2006; and AMS National Conference, San Antonio, January 2006.

  3. "Random geometric graph diameter threshold in the unit disk," contributed talk, Erdős Magic Workshop, Bertinoro, Italy, April 2005; invited talk, Metron Inc., January 2005; AMS Sectional Conference special session on Extremal Graph Theory and Combinatorics, Evanston, IL, October 2004.

  4. "The Renyi-Ulam pathological liar game with a fixed number of lies," AMS National Conference contributed paper session on Combinatorics, Atlanta, January 2005; invited talk, Univ. IL Urbana-Champaign combinatorics seminar and Illinois Inst. of Technology seminar, October 2004.

  5. "Discrete Green's functions for regular graphs," Mathematical Physics and Harmonic Analysis seminar, Texas A&M, November 2004.

  6. "A 2-player game for adaptive covering codes," Algebra/Combinatorics seminar, Texas A&M, November 2004.

  7. "Random geometric graph diameter in the unit disk with lp metric," 12th International Symposium on Graph Drawing, short paper session, CUNY, New York City, September 2004.

  8. "On Random Points in the Unit Disk," AMS National Conference special session on Probability and its application to Combinatorics and Algorithms, Phoenix, January 2004.

  9. "The Renyi-Ulam pathological liar game," AMS National Conference contributed session on Combinatorics, Phoenix, January 2004.

  10. Animal, Mineral or Vegetable, and other combinatorial games, invited talk, Majors' Seminar, Trinity University Department of Mathematics, October 2003.

  11. The Renyi-Ulam pathological liar game with one half-lie, Texas A&M postdoc review, October 2003.

  12. "Density of normal binary covering codes," contributed talk,
    Workshop on Extremal Graph Theory `03 (Rényi Institute), Csopak, Hungary, June 2003.

  13. "Ulam's pathological liar game with one half-lie," contributed talk,
    CombinaTexas `03, San Marcos, TX, April 2003.

  14. "Discrete Green's functions,"
    Texas A&M postdoc review, October 2002.

  15. "A Probabilistic Method for Coding Theory,"
    Texas A&M, September 2002.

  16. "Chip-firing games with Dirichlet Eigenvalues and Discrete Green's Functions,"
    (final defense), UC San Diego, May 2002.

  17. "Chip-firing games and discrete Green's functions,"
    UC San Diego, March 2002.

  18. "Discrete Green's functions for products of regular graphs," AMS National Conference special session on Graph Theory, San Diego, January 2002.

  19. "One-sided binary covering codes,"
    UC San Diego, November 2001.

  20. "Dummy fill as a reduction to chip-firing,"
    UC San Diego CSE Dept., June 2001.

  21. "A chip-firing game and Dirichlet eigenvalues,"
    UC San Diego, October 2000.

  22. "Network Diversion Attack" (presented with Patrick Quillen),
    IMA  Mathematical Modeling in Industry Summer 2000 Program for Graduate Students, University of Minnesota, July 2000.

  23. "Chip-firing games" (advancement to candidacy),
    UC San Diego, March 2000.


Posters

  1. Compression Schemes for "Dummy Fill" VLSI Layout Data, UC San Diego Jacobs School of Engineering 2002 Research Review (with Yuhong Zheng, Andrew Kahng and Joshua Cooper).


Professional Activities and Service

  1. Organizer/co-organizer, IIT Applied Math seminars and colloquia, Fall 2005-Fall 2006

  2. Co-organizer, CombinaTexas `04 and `05, Texas A&M and TSU-San Marcos; a regional NSF-supported combinatorics conference.

  3. Organizer, Texas A&M Algebra and Combinatorics Seminar, Fall 2003-Spring 2004; assistant organizer, Fall 2004.

  4. Referee of journal articles: Discrete Mathematics, Electronic Journal of Combinatorics (x2), European Journal of Combinatorics, Journal of Computer System Sciences, SIAM Journal of Applied Mathematics, SIAM Journal on Discrete Mathematics.

  5. Lead administrator, Graduate Mathematics Consulting Group, UC San Diego, April-July, 2002.

  6. Honorable Mention, graph drawing contest, 12th International Symposium on Graph Drawing, September 2004 (with Joshua Cooper and Reid Andersen).

  7. University Scholar selection panel interviewer, Office of Honors Programs and Academic Scholarships, Texas A&M, April 25, 2003, April 21, 2004 and April 20, 2005.

  8. Faculty Host, Davidson Young Scholars weekend, Texas A&M, March 8, 2003.

  9. 2003 Student Research Week poster competition judge, Humanities graduate division, Texas A&M, March 2003.

  10. Invited exam review lecturer, Texas A&M Leaders in Freshman Engineering, Fall 2002.

  11. Member, AMS.


Teaching (see full details)
  Illinois Institute of Technology
Fall 2005 Calculus II
Graph Theory (Undergraduate)

Texas A&M

Fall 2004

Engineering Calculus II (2 lectures)

Summer-Fall 2004

Honors directed undergraduate research in Renyi-Ulam games

Spring 2004

Honors Engineering Calculus II;
Directed undergraduate research in Renyi-Ulam games

Fall 2003

Honors Engineering Calculus II;
Directed undergraduate research in Renyi-Ulam games

Summer 2003

Algebraic Methods in Combinatorics and Graph Theory, VIGRE graduate course (developed and taught with Catherine Yan)

Spring 2003

Introduction to Proofs

Fall 2002

Engineering Calculus II

Virginia Tech (as instructor)

Summer 1996

Linear Algebra I

Fall 1995

Precalculus (2 lectures)


Workshops/Conferences Attended
Aug 2005 MathFest 2005 and Project NExT workshop
Apr 2005 Erdős Magic for Algorithms and Games Workshop, Bertinoro, Italy
Feb 2005 CombinaTexas `05, San Marcos, TX

Jan 2005

AMS/MAA National Joint Meeting, Atlanta, GA

Jan 2005

The mathematics of Persi Diaconis, San Diego, CA

Oct 2004

AMS Central Sectional meeting, Evanston, IL

Sep 2004

12th International Symposium on Graph Drawing, NY, NY.

Jun 2004

SIAM Conference on Discrete Mathematics `04, Nashville, TN

Jun 2004

NSF-CBMS: The Combinatorics of Large Sparse Graphs, San Marcos, CA

May 2004

AMS/MSS International Joint Meeting, Houston, TX

Apr 2004

CombinaTexas `04, College Station, TX

Jan 2004

AMS/MAA National Joint Meeting, Phoenix, AZ

Oct 2003

Geometry Day `03, University of North Texas, Denton, TX.

Jun 2003

Workshop on Extremal Graph Theory `03, Renyi Institute, Budapest

Apr 2003

CombinaTexas `03, San Marcos, TX

Mar 2003

AMS Southeastern Sectional Meeting, Baton Rouge, LA

Jan 2003

AMS/MAA National Joint Meeting, Baltimore, MD

Jan 2003

SAGP `03, Spectral Analysis in Geometry and Physics, UC San Diego

Jan 2002

AMS/MAA National Joint Meeting, San Diego, CA

Oct 2001

42nd Annual Symposium on Foundations of Computer Science (FOCS), Las Vegas, NV

Aug 2000

AMS Mathematical Challenges of the 21st Century, UC Los Angeles

Jul 2000

Institute for Mathematics and its Applications (IMA) Mathematical Modeling in Industry graduate student workshop, University of Minnesota

Jan 1997

AMS/MAA National Joint Meeting, San Diego, CA

Jul 1996

Center for Research in Scientific Computation (CRSC) Industrial Mathematics Modeling Workshop for graduate students, NC State


References

Fan Chung, Department of Mathematics, UCSD, San Diego, CA
Catherine Yan, Department of Mathematics, Texas A&M, College Station, TX
Joel Spencer, Courant Institute, New York University, NY, NY
Al Boggess, Department of Mathematics, Texas A&M, College Station, TX
Michael Pilant, Department of Mathematics, Texas A&M, College Station, TX
Jeffrey Remmel, Department of Mathematics, UCSD, San Diego, CA