VITA:   Michelangelo Grigni
March 2008

Rank:

Associate Professor

Contact:

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

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

Research Interests:

Theory of computation: approximate subgraph optimization problems (such as traveling salesman), graph decomposition algorithms (separators and spanners), bioinformatic algorithms, quantum computing (hidden subgroups).

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), MAA.

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.

1982-1986: full-tuition scholarships (A.B. Duke, N.C. Math).

Teaching:

(2+2 load)

Spring 2008: Data Structures & Algorithms (CS323, previously CS253), Graduate Algorithms (CS524, previously CS584G).

Fall 2007: Intro. to C.S. II (CS171), Discrete Math. for C.S. (CS224).

Spring 2007: Computing for Bioinformatics (CS153, new course), CS253.

Fall 2006: CS171, CS224.

2005-2006: Freshman seminar (CS190, bioinformatics), Theory of Computing (CS424), CS224, CS584G, and proposal/development for CS153.

2004-2005: CS171, CS224, CS170, CS253 (new curriculum), and Math 578R with Skip Garibaldi (quantum algorithms for hidden subgroups).

2003-2004: CS584G, Multivariable Calculus (Math211), Graduate Theory (CS524), CS171 (new course).

2002-2003: extended sabbatical, Boston.

2001-2002: Discrete Math. for C.S. (CS124), CS253 (twice), CS524.

2000-2001: CS124, CS584G, CS424, CS524.

Spring 2000: CS170, CS524 (first time separated from CS424).

Fall 1999: sabbatical.

1998-1999: CS124, CS253 (twice, C⁺⁺ and Java), CS424/524.

1997-1998: CS170, CS424/524, CS124 (UTF funded pilot), CS584G.

1996-1997: CS170 (twice), pilot CS424/524, Algebra Seminar (Math227).

1995-1996: Math227, Math228, CS584G, CS253.

Students:

Math. Ph.D. program:

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

Andre Berger, co-advised with Ojas Parekh, August 2006, Faster Minimum Weight Subgraph Algorithms. (Postdoc at TU Berlin.)

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.)

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.

Service:

1997-present: Graduate Committee. handled dgs e-mail inquiries until Fall 2005.

1996-present: Putnam Exam coach and organizer (each Fall except 2002).

2006-present: CLS education committee.

2000-present: C.S. undergraduate majors advisor

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: ACM Transactions on Algorithms, J. Algorithms, Comp. Complexity, Disc. Comp. Geometry, JCMCC, Inf. & Comp., IPL, ORSA J. Comput, JPDC, SICOMP, SIDMA (and quick reviews for various conferences).

NSF panel reviewer, 2001.

Talks:

Invited lecture, ``Faster Approximations for TSP and 2-ECSS'', 21^st 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 NC¹ .
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 $\Theta$(lg²n) .

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 $\varepsilon$ -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 $\varepsilon$ -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 36^th 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 6^th 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 $\it 13^{th}$ 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.

Work in Progress

The following manuscripts are not yet accepted to conferences or journals.

26

André Berger, Michelangelo Grigni, and Hairong Zhao.
A well-connected separator for planar graphs.
Technical Report TR-2004-026-A, Emory Math/CS Dept., 2004.
13 pages, submitted to JGAA, November 2004. Update (4/2008): JGAA has not responded, so Berger and I are combining this with [25], and plan to resubmit it all to another journal.