up previous
Up: Home

VITA:   Michelangelo Grigni
April 2017


Rank:

Associate Professor

Contact:

Dept. of Mathematics & Computer Science
400 Dowman Drive, W401
Emory University
Atlanta GA 30322, USA

Phone: 404-727-7922 (404-727-5611 fax)
Email: mic@mathcs.emory.edu
Web: http://mathcs.emory.edu/~mic/

Research Interests:

Theory of computation: approximate subgraph optimization problems (such as metric traveling salesman), graph decomposition algorithms (spanners and separators), metric approximation, bioinformatic algorithms.

Experience:

2001 to present: Associate Professor, Emory University

1995 to 2001: Assistant Professor, Emory University

1993 to 1995: NSF postdoctoral fellow and lecturer, U.C. San Diego

1992 to 1993: NSF postdoctoral fellow, Princeton University

1991 to 1992: postdoctoral fellow, University of British Columbia

Education:

Ph.D. (1991) Massachusetts Institute of Technology, Applied Math.

B.S. (1986) Duke University, Mathematics and Computer Science, summa cum laude.

Professional Memberships:

ACM (SIGACT).

Support:

Awarded:

2002-2004: NSF grant CCR-0208929, ``Light Spanners for Hard Metrical Optimization Problems'', sole PI ($125,712).

1999-2002: NSF grant CCR-9820931, ``Approximation Algorithms for Planar and Geometric Optimization Problems'', sole PI ($144,200).

1997, 1998: Emory UTF course development grants.

1996: Emory URC grant, ``Summer Travel and the TSP'' ($4000).

1992-1995: NSF Mathematical Sciences Postdoctoral Research Fellowship.

1986-1989: NSF Graduate Fellowship.

Teaching:
(2+2 load)

Spril 2017: Graduate Algorithms (CS526), Theory of Computing (CS424).

Fall 2016: Computing for Bioinformatics (CS153), Data Structures & Algorithms (CS323).

2015-2016: CS153, Theory of Computing (graduate, CS524). CS323, CS424.

2014-2015: CS524, CS153. Intro. C.S. II (CS171), CS526, Honors (CS495RW, Celis), Directed Study (CS597R, Jiang and Meng).

2013-2014: CS524, CS224, CS598R (Elser). CS323, CS424.

2012-2013: CS524, CS224, CS599R (Lou), CS526, CS153.

2011-2012: CS170, CS524, CS797R (Hung), CS153, CS323, CS597R (Lou), CS797R (Hung).

2010-2011: CS526, CS153, CS599R (Bonomi), CS797R (Hung). (Also supervised three sections of CS170.) CS171, CS524, CS598R (Bonomi).

2009-2010: CS171, CS524. CS526, CS153.

2008-2009: Topics in Comp. & Life Science (CS740R, new course), CS524. CS323, CS153, CS598R (Hung).

Previous years available on request.

Students:

C.S. Ph.D. program:
Hao-Hsiang Hung, left the program in summer 2012. We published a paper on light spanners.

Math. Ph.D. program:

Papa Amar Sissokho, co-advised with V. Rödl, Summer 2003, Light Spanners and Sparse Pseudorandom Graphs. (Associate Professor, Department of Mathematics, Illinois State University.)

Andre Berger, co-advised with Ojas Parekh, August 2006, Faster Minimum Weight Subgraph Algorithms. (Assistant Professor, Quantitative Economics, Maastricht University.)

C.S. M.S. program:

Keven Haynes, Spring 1998, The Feasibility of an Approximation Algorithm for the Traveling Salesman Problem. (Held technical positions at Georgia Tech and BellSouth, with Emory IT since Fall 2004.)

Andrzej Woloszyn, Summer 1998, A Weighted Planar Graph Separator.

Baiyu Pan, Spring 1999, Content-Sensitive Implicit X Compression. (Princeton real estate agent, and part-time instructor at Phoenix online.)

Malgorzata Malowinska, Summer 1999, Synchronizing Files over a Communication Link.

Benjamin Bradford (BS/MS), Fall 2000, An Algorithm for the Multiple Alignment of Protein Sequences. (Briefly a dot-bomb developer, now a Chicago IP law attorney.)

Tao Xu, Spring 2002, Data Structures for Extremal Optimization.

Adam Sherwood (BS/MS), Spring 2004, An Efficient Implementation of Suffix Trees Indexing the Human Genome. (Attending NYU medical school.)

Shufu Xu, Summer 2004, An Improvement to the BitTorrent Peer-to-peer Protocol. (Systems Analyst at Fred Hutchinson Cancer Research Center, building parallel simulators for national flu epidemics, which continues work started at Emory Biostatistics.)

Yogya Sharma, Fall 2005, A Well-Connected Separator for Planar Graphs. (A biotechnology software developer at St. Jude Children's Research Hospital.)

Siyuan Lou, Fall 2012, Analysis of Detour Gap Numbers.

Andres Celis, Honors/MS Spring 2015, A Stochastic Model for Networks that Arise from Conference Scheduling Problems. (Entered CS Ph.D. program at UCSD.)

Undergraduates:

Todd Arnold, 497R, a directed study of subliminal channels, Fall 1996.

Christan Blystone, Emory SURE program, a directed study of detour gap numbers, Summer 2000.

Andres Celis, Emory SURE program, directed study of scheduling problems in social networks, Summer 2014.

Service:

2013-present: undergraduate committee, member.

1997-2013: Graduate Committee (mostly CS).

1996-present (except 2002): each fall, coach and organizer for Emory students taking the Putnam exam (also the VTRMC since 2005).

2010-2012: chair of CS curriculum committee, reviewing the introductory CS sequence (especially CS170 to CS171).

2006-2009: CLS education committee.

2000-present: undergraduate majors advisor (mix of Math and CS).

2008-2013: each January, organized a small math tournament day for students from Fernbank elementary school.

2003-2006: C.S. development committee (chair 2004-2005).

1999-2001: INPACS committee.

1996-1999: Emory Academic Standards Committee.

Fall 1998: Emory freshman advising program (FAME), and subsequent service as a pre-major advisor.

1997-1998: PMACS Theory and Modeling Committee.

1995-1997: proposed and developed two new courses (CS124 and CS424/524) and revised CS major requirements.

Refereeing: Annals of Operations Research, PLOS ONE, ACM Transactions on Algorithms, J. Algorithms, Combinatorica, Comp. Complexity, Disc. Comp. Geometry, JCMCC, Inf. & Comp., IPL, ORSA J. Comput, JPDC, SICOMP, SIDMA (and quick reviews for various conferences).

Reviewed Sedgewick's Algorithms (4th edition), Spring 2009.

NSF panel reviewer, 2001.

Talks:

Invited participant at Dagstuhl Seminar 16221, ``Algorithms for Optimization Problems in Planar Graphs'', May-June 2016.

Invited participant at Dagstuhl Seminar 13421, ``Algorithms for Optimization Problems in Planar Graphs'', October 2013.

Invited lecture, ``Faster Approximations for TSP and 2-ECSS'', 21st Clemson mini-conference on Discrete Math and Algorithms, 12 October 2006.

Bibliography

Publications

This listing is roughly chronological. In cases where a conference article appears again as a journal article, I have listed the journal version immediately after the conference version, and I label the two versions with the suffixes `a' and `b', respectively. Links refer to large Postscript files; other formats may be available by browsing my papers directory.

1
Dimitris Bertsimas and Michelangelo Grigni.
On the space-filling curve heuristic for the Euclidean traveling salesman problem.
Operations Research Letters, 8:241-244, October 1989.

2a
Michelangelo Grigni and Michael Sipser.
Monotone separation of logspace from NC1 .
In Proceedings of the Sixth Annual Conference on Structure in Complexity Theory, pages 294-298. IEEE, 1991.
This contains the main technical result of my thesis: monotone circuits for a certain function in monotone logspace require depth (lg2n) .

2b
Michelangelo Grigni and Michael Sipser.
Monotone separation of logarithmic space from logarithmic depth.
Journal of Computer and System Sciences, 50:433-437, 1995.

3
Michelangelo Grigni and David Peleg.
Tight bounds on minimum broadcast networks.
SIAM Journal on Discrete Mathematics, pages 207-222, May 1991.

4
Michelangelo Grigni and Michael Sipser.
Monotone complexity.
In M. S. Paterson, editor, Boolean Function Complexity, volume 169 of Lecture Note Series, pages 57-75. London Mathematical Society, Cambridge University Press, 1992.
This presents the monotone computation framework from my thesis, including some results on monotone bounded-width branching programs.

5a
Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas Guibas, John Hershberger, Micha Sharir, and Jack Snoeyink.
Ray shooting in polygons using geodesic triangulations.
In Javier Leach Albert, Burkhard Monien, and Mario Rodríguez-Artalejo, editors, Automata, Languages and Programming: 18th International Colloquium, volume 510 of Lecture Notes in Computer Science, pages 661-673. Springer-Verlag, 1991.

5b
Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas Guibas, John Hershberger, Micha Sharir, and Jack Snoeyink.
Ray shooting in polygons using geodesic triangulations.
Algorithmica, 12(1):54-68, 1994.

6a
Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas Guibas, and Micha Sharir.
Improved bounds on weak -nets for convex sets.
In Proceedings of the Twenty Fifth Annual ACM Symposium on Theory of Computing, pages 495-504, 1993.

6b
Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas Guibas, Micha Sharir, and Emo Welzl.
Improved bounds on weak -nets for convex sets.
Discrete Computational Geometry, 13:1-15, 1995.

7
Michelangelo Grigni, Dimitris Papadias, and Christos Papadimitriou.
Topological inference.
In C. Mellish, editor, Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI), volume 1, pages 901-906. Morgan Kaufmann, 1995.
This paper led to our interest in planar map graphs [13].

8
Michelangelo Grigni, Elias Koutsoupias, and Christos Papadimitriou.
An approximation scheme for planar graph TSP.
In 36th Annual Symposium on Foundations of Computer Science, pages 640-646. IEEE, October 1995.
This was submitted to JCSS in 1995, but a report has not yet emerged.

9
Michelangelo Grigni and Fredrik Manne.
On the complexity of generalized block distribution.
In IRREGULAR: International Workshop on Parallel Algorithms for Irregularly Structured Problems, volume 1117 of Lecture Notes in Computer Science, pages 319-326, 1996.
This resulted from answering Manne's USENET query.

10a
Michelangelo Grigni, Vincent Mirelli, and Christos Papadimitriou.
On the difficulty of designing good classifiers.
In COCOON Proceedings, July 1996.

10b
Michelangelo Grigni, Vincent Mirelli, and Christos Papadimitriou.
On the difficulty of designing good classifiers.
SIAM Journal on Computing, 30(1):318-323, 2000.

11
Soeren P. Olesen, Sarah E. Chodrow, Michelangelo Grigni, and Vaidy S. Sunderam.
Distributed data management support for collaborative computing.
In Proceedings of High Performance Computing and Networking, April 1997.

12
Sanjeev Arora, Michelangelo Grigni, David Karger, Philip Klein, and Andrzej Woloszyn.
A polynomial-time approximation scheme for weighted planar graph TSP.
In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 33-41, 1998.

13
Zhi-Zhong Chen, Michelangelo Grigni, and Christos Papadimitriou.
Planar map graphs (abstract).
In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pages 514-523, 1998.
Papadimitriou also announced these results at WADS'97 (two pages). Two other papers [21,24] give more details.

14a
V. Sunderam, S. Y. Cheung, S. Chodrow, M. Grigni, A. Krantz, I. Rhee, P. Gray, S. Olesen, and P. Hutto.
CCF: Collaborative computing frameworks.
In SC'98: High Performance Networking and Computing: Proceedings of the 1998 ACM/IEEE SC98 Conference, November 1998.

14b
V. Sunderam, S. Cheung, S. Chodrow, P. Gray, M. Grigni, M. Hirsch, P. Hutto, A. Krantz, S. Olesen, I. Rhee, J. Sult, M. Migliardi, L. Marzilli, S. Ano, K. Williams, and S. Sullivan.
CCF: A framework for collaborative computing.
IEEE Network Computing, 4(1):16-24, Jan/Feb 2000.

15
Michelangelo Grigni.
Approximate TSP in graphs with forbidden minors.
In Automata, Languages and Programming: 27th International Colloquium, volume 510 of Lecture Notes in Computer Science, pages 869-877. Springer-Verlag, July 2000.
This paper extends the previous TSP methods [8,12] from planar graphs to more general graph families. It also introduces a new graph theoretic quantity (the `gap' number).

16
Michelangelo Grigni.
A Sperner lemma complete for PPA.
Information Processing Letters, 77(5-6):255-259, March 2001.

17
Stefan Boettcher, Allon Percus, and Michelangelo Grigni.
Optimizing through co-evolutionary avalanches.
In 6th International Conference on Parallel Problem Solving from Nature, volume 1917 of Lecture Notes in Computer Science, pages 447-456, 2000.

18a
Michelangelo Grigni, Leonard J. Schulman, Monica Vazirani, and Umesh Vazirani.
Quantum mechanical algorithms for the nonabelian hidden subgroup problem.
In Proceedings of the Thirty Third Annual ACM Symposium on Theory of Computing, 2001.

18b
Michelangelo Grigni, Leonard J. Schulman, Monica Vazirani, and Umesh Vazirani.
Quantum mechanical algorithms for the nonabelian hidden subgroup problem.
Combinatorica, 24(1):137-154, January 2004.

19
Michelangelo Grigni and Papa Amar Sissokho.
Light spanners and approximate TSP in weighted graphs with forbidden minors.
In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 852-857, 2002.

20
Stefan Boettcher and Michelangelo Grigni.
Jamming model for the extremal optimization heuristic.
J. Phys. A: Math. Gen., 35(5):1109-1123, 2002.

21
Zhi-Zhong Chen, Michelangelo Grigni, and Christos Papadimitriou.
Map graphs.
Journal of the ACM, 49(2):127-138, March 2002.

22
Artur Czumaj, Michelangelo Grigni, Papa Sissokho, and Hairong Zhao.
Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs.
In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 489-498, New Orleans, LA, 2004.
Based on an earlier 2EC manuscript with Papa.

23
André Berger, Artur Czumaj, Michelangelo Grigni, and Hairong Zhao.
Approximate schemes for minimum 2-connected spanning subgraphs in weighted planar graphs.
In Annual European Symposium on Algorithms (ESA). EATCS, October 2005.
Also available as Emory Math/CS TR-2004-025-A.

24
Zhi-Zhong Chen, Michelangelo Grigni, and Christos Papadimitriou.
Recognizing hole-free 4-map graphs in cubic time.
Algorithmica, 45:227-262, June 2006.
This is the full version of a result announced in [13,21].

25
André Berger and Michelangelo Grigni.
Minimum weight 2-edge-connected spanning subgraphs in planar graphs.
In Automata, Languages and Programming: 34th International Colloquium, Lecture Notes in Computer Science, pages 90-101. Springer-Verlag, July 2007.

26
Michelangelo Grigni and Hao-Hsiang Hung.
Light spanners in bounded pathwidth graphs.
In Branislav Rovan, Vladimiro Sassone, and Peter Widmayer, editors, MFCS, volume 7464 of Lecture Notes in Computer Science, pages 467-477. Springer, 2012.


up previous
Up: Home