@comment{
  This is a bibtex database of my publications, manuscripts,
  and related miscellany.  This file supports my cv, so
  there are a few non-standard fields for my cv.bst style:

   bibtag="XX"
	appears as \bibitem[XX]{...}

   abstract="some long text..."
	appears as a paragraph right after the bibitem.

   (AT)section{title="Short"[,note="Longer text..."]}
	starts a new bibliography subsection, with optional paragraph,
        all flush left.  Not a "real" citation.

   Assumes some journal name strings from strings.bib, and some
   crossrefs from proceedings.bib.
}

too-tricky-by-half-string{mic="{\relax Mic}helangelo Grigni"}
@string{mic="Michelangelo Grigni"}

@section{sec:publications,
title="Publications",
note="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 \htmladdnormallink{papers}{/~mic/papers/} directory.
"
}

@article{BertsimasGrigni89,
bibtag=1,
url="/~mic/papers/1.ps",
author={Dimitris Bertsimas and } # mic,
journal=orl,
title={On the Space-Filling Curve Heuristic for the {E}uclidean Traveling
Salesman Problem},
volume=8,
month=oct,
year=1989,
pages={241--244},
realabstract={Bartholdi and Platzman (1982) proposed the spacefilling curve
heuristic for the Euclidean traveling salesman problem and proved that
their heuristic returns a tour within an $O(\lg n)$ factor of optimal
length.  They conjectured that the worst-case ratio is in fact $O(1)$.
Here we exhibit counterexamples showing the $O(\lg n)$ upper bound is
tight.},
noabstract={We show that a certain TSP heuristic finds tours with length
$\Theta(\log n)$ times optimal.  A nice conjecture at the end would
generalize the result to any ``oblivious'' heuristic.
%% A discussion with Noga Alon has encouraged me to pursue it again.
}
}

@inproceedings{GrigniSi90,
bibtag="2a",
author=mic # { and Michael Sipser},
title={Monotone Separation of Logspace from {NC}$^1$},
year=1991,
crossref={SCTC6},
pages={294--298},
abstract={This contains the main technical result of my thesis:
monotone circuits for a certain function in monotone logspace require
depth $\Theta(\lg^2n)$.}
}

@article{GrigniSi95,
bibtag="2b",
url="/~mic/papers/2b.ps",
  author=	 mic # { and Michael Sipser},
  title=	 {Monotone Separation of Logarithmic Space from
		 Logarithmic Depth},
  year=		 1995,
  journal=	 jcss,
  volume=	 50,
  pages=	 {433--437},
  noabstract= {This contains the main technical result of my thesis.},
  realabstract=	 {We show that the monotone analogue of
                 logspace computation is more powerful than monotone
 		 log-depth circuits: monotone circuits for a
		 certain function in monotone logspace require depth
 		 $\Theta(\lg^2n)$.}
}

@article{GrigniPe91,
bibtag=3,
url="/~mic/papers/3.ps",
author=mic # { and David Peleg},
title={Tight Bounds on Minimum Broadcast Networks},
journal=siamjdm,
year=1991,
month=may,
pages={207--222},
realabstract={
 A {\em broadcast graph} is an $n$-vertex communication network that
supports a broadcast from any one vertex to all other vertices in
optimal time $\lceil{\lg n}\rceil$, given that each message
transmission takes one time unit and a vertex participates in at most
one transmission per time step.  This paper establishes tight bounds
for $B(n)$, the minimum number of edges of a broadcast graph, and
$D(n)$, the minimum maxdegree of a broadcast graph.  Let $L(n)$ denote
the number of consecutive leading 1's in the binary representation of
integer $n-1$.  We show $B(n) = \Theta (\L(n) \cdot n)$ and $D(n) =
\Theta (\lg\lg n + \L(n))$, and for every $n$ we give a construction
simultaneously within a constant factor of both lower bounds.  For all
$n$ we also construct graphs with $O(n)$ edges and $O(\lg\lg n)$
maxdegree requiring at most $\lceil{\lg n}\rceil+1$ time units to
broadcast.  Our broadcast protocols may be implemented with local
control and $O(\lg \lg n)$ bits overhead per message.  Both the upper
and lower bounds are based on generalized Fibonacci sequences.
 }}

@comment{NOT usually a CV bibitem, so it has an odd bibtag.}
@phdthesis{Grigni91,
bibtag="PhD",
author=mic,
title={Structure in Monotone Complexity},
year=1991,
month=jun,
school=mit,
note={Available as technical report MIT/LCS/TR-520},
noabstract={The main results of this also appear later in the two
articles co-authored with Sipser \cite{GrigniSi92,GrigniSi95}.}
}

@InProceedings{GrigniSi92,
bibtag=4,
url="/~mic/papers/4.ps",
author=mic # { and Michael Sipser},
title={Monotone Complexity},
  editor =	 "M. S. Paterson",
  volume =	 169,
  series =	 "Lecture Note Series",
  pages =	 "57--75",
  booktitle =	 "Boolean Function Complexity",
  year =	 1992,
  organization = "London Mathematical Society",
  publisher =	 "Cambridge University Press",
  history = "Submitted in 1990.",
abstract="This presents the monotone computation framework from my thesis,
  including some results on monotone bounded-width branching programs.",
realabstract={We give a general complexity classification scheme for
   monotone computation, including monotone space-bounded and Turing
   machine models not previously considered.  This provides a
   framework for stating existing results and asking new questions.
\par \def\cc#1{\mbox{\sl #1\/}} We show that $\cc{mNL}$ (monotone
   nondeterministic log-space) is not closed under complementation, in
   contrast to the result of Immerman and and Szelepcs\'enyi that
   $\cc{NL}=\cc{co-NL}$.
\par We also consider $\cc{mBWBP}$ (monotone bounded width branching
   programs) and study the question of whether $\cc{mBWBP}$ is
   properly contained in $\cc{mNC}^1$, motivated by Barrington's
   result that $\cc{BWBP}=\cc{NC}^1$.  We show no monotone analogue
   of Barrington's gadget exists.},
ignoredabstract={We show two preliminary results: every monotone
   branching program for majority has size $\Omega(n^2)$ even without
   width restriction, and no monotone analogue of Barrington's gadget
   exists.}
}

@InProceedings{cegghss-rspug-91,
bibtag="5a",
author = "Bernard Chazelle and Herbert Edelsbrunner and " # mic #
 " and Leonidas Guibas and John Hershberger and Micha Sharir
   and Jack Snoeyink",
title =	{Ray shooting in polygons using geodesic triangulations},
crossref={ICALP18},
pages={661--673},
noabstract={Let $\cal P$ be a simple polygon with $n$ vertices.
We present a simple decomposition scheme that partitions the interior
of $\cal P$ into $O(n)$ so-called geodesic triangles, such that any line
segment interior to $\cal P$ crosses at most $2 \lg n$ of these
triangles.  This decomposition can be used to preprocess $\cal P$ in
time $O(n \lg n)$ and storage $O(n)$, so that any ray shooting query
can be answered in time $O(\lg n)$.  The algorithms are fairly simple
and easy to implement.  We also extend this technique to the case of
ray shooting amidst $k$ polygonal obstacles of a total of $n$ edges,
so that a query can be answered in $O(\sqrt{k} \lg n)$ time.}
}

@article{cegghss-rspug-94,
bibtag="5b",
author =	"Bernard Chazelle and Herbert Edelsbrunner and " # mic #
		" and  Leonidas Guibas and John Hershberger
		 and Micha Sharir and Jack Snoeyink"
, title =	{Ray shooting in polygons using geodesic triangulations}
, journal =	"Algorithmica"
, volume =	12
, number =      1
, year =	1994
, pages =	"54--68"
, realabstract={Let $\cal P$ be a simple polygon with $n$ vertices. We
    present a simple decomposition scheme that partitions the interior
    of $\cal P$ into $O(n)$ so-called geodesic triangles, so that any
    line segment interior to $\cal P$ crosses at most $2 \log n$ of
    these triangles. This decomposition can be used to preprocess
    $\cal P$ in a very simple manner, so that any ray-shooting query
    can be answered in time $O(\log n)$. The data structure requires
    $O(n)$ storage and $O(n \log n)$ preprocessing time. By using more
    sophisticated techniques, we can reduce the preprocessing time to
    $O(n)$. We also extend our general technique to the case of ray
    shooting amidst $k$ polygonal obstacles with a total of $n$ edges,
    so that a query can be answered in $O(\sqrt{k} \log n)$ time.}
, succeeds =	"cegghss-rspub-91"
}

@inproceedings{ceggs-ibwen-93,
bibtag="6a",
author =	"Bernard Chazelle and Herbert Edelsbrunner and " # mic #
                " and Leonidas Guibas and Micha Sharir"
, title =	"Improved Bounds on Weak $\varepsilon$-Nets for Convex Sets"
, crossref = {STOC25}
, pages =	"495--504"
, noabstract={Let $S$ be a set of $n$ points in ${\bf R}^d$. A set $W$ is a
   {\em weak $\varepsilon$-net} for (convex ranges of) $S$ if for any
   $T \subseteq S$ containing $\varepsilon n$ points, the convex hull
   of $T$ intersects $W$.  We show the existence of weak
   $\varepsilon$-nets of size $O\left( {1 \over \varepsilon^d}
   \log^{\beta_d} {1 \over \varepsilon} \right)$, where $\beta_2=0$,
   $\beta_3=1$, and $\beta_d \approx 0.149\cdot 2^{d-1}(d-1)!$,
   improving a previous bound of Alon {\em et al}.}
, ignoredabstract={We present a deterministic algorithm for
   computing such a net in time $n (1/\varepsilon)^{O(1)}$.
   We also consider two special cases: when $S$ is in convex
   position, we prove the existence of a net of size
   $O({1 \over \varepsilon} \log^{1.6}{1 \over \varepsilon})$;
   for the case where $S$ consists of the vertices of a regular polygon,
   we use an argument from hyperbolic geometry to
   exhibit an optimal net of size $O(1/\varepsilon)$.}
}

@article{ceggsw-ibwen-95,
bibtag="6b",
url="/~mic/papers/6b.ps",
author = "Bernard Chazelle and Herbert Edelsbrunner and " # mic #
  " and Leonidas Guibas and Micha Sharir and Emo Welzl"
, title =	"Improved Bounds on Weak $\varepsilon$-Nets for Convex Sets"
, journal =	dcg
, volume =	13
, year =	1995
, pages =	"1--15"
}

@inproceedings{gpp-ti-95,
bibtag=7,
url="/~mic/papers/7.ps",
  author = 	 mic # " and Dimitris Papadias and Christos Papadimitriou",
  title = 	 "Topological Inference",
  booktitle= 	"Proceedings of the 14th International Joint Conference
		on Artificial Intelligence (IJCAI)",
  year =	 1995,
  pages =	{901--906},
  volume =	 1,
  publisher =	 "Morgan Kaufmann",
  editor = "C.\ Mellish",
  abstract={This paper led to our interest in planar
   map graphs~\cite{cgp-pmg-98}.},
  realabstract ={Geographical database systems deal with certain basic
topological relations such as ``A overlaps B'' and ``B contains C''
between simply connected regions in the plane. It is of great interest
to make sound inferences from elementary statements of this form.
This problem has been identified extensively in the recent literature,
but very limited progress has been made towards addressing the
considerable technical difficulties involved.  In this paper we study
the computational problems involved in developing such an inference
system.  We point out that the problem has two distinct components
that interact in rather complex ways: {\em constraint satisfaction},
and {\em planarity}.  We develop polynomial-time algorithms for
several important special cases, and prove almost all the others to be
NP-hard.}
}

@inproceedings{GrigniKoPa95,
bibtag=8,
url="/~mic/papers/8.ps",
author=mic # { and Elias Koutsoupias and Christos Papadimitriou},
title={An Approximation Scheme for Planar Graph {TSP}},
year=1995,
month=oct,
pages={640-646},
crossref={FOCS28},
realabstract={We consider the special
  case of the traveling salesman problem (TSP) in
  which the distance metric is the shortest-path metric of a planar unweighted
  graph.  We present a polynomial-time approximation scheme (PTAS)
  for this problem.},
abstract="This was submitted to JCSS in 1995,
 but a report has not yet emerged."
}

@Inproceedings{gm-cgbd-96,
bibtag=9,
url="/~mic/papers/9.ps",
author = mic # " and Fredrik Manne",
title = "On the Complexity of Generalized Block Distribution",
booktitle="IRREGULAR: International Workshop on Parallel
  Algorithms for Irregularly Structured Problems",
series=lncs,
volume=1117,
nomonth=aug,
pages="319--326",
year=1996,
abstract="This resulted from answering Manne's USENET query."
}

@Inproceedings{gmp-96,
bibtag="10a",
author = mic # " and Vincent Mirelli and Christos Papadimitriou",
title = "On the Difficulty of Designing Good Classifiers",
booktitle="COCOON Proceedings",
month= jul,
year = 1996
}

@Article{gmp-00,
bibtag="10b",
url="/~mic/papers/10b.ps",
author = mic # " and Vincent Mirelli and Christos Papadimitriou",
title = "On the Difficulty of Designing Good Classifiers",
journal = sicomp,
volume=30,
number=1,
pages="318--323",
year = 2000
}

@Inproceedings{ocgs-ddmscc-97,
bibtag=11,
url="/~mic/papers/11.ps",
author="Soeren P. Olesen and Sarah E. Chodrow and " # mic #
       " and Vaidy S. Sunderam",
title="Distributed Data Management Support for Collaborative Computing",
booktitle="Proceedings of High Performance Computing and Networking",
month=apr,
year=1997
}

@inproceedings{agkkw-wpgt-98,
bibtag="12",
url="/~mic/papers/12.ps",
author="Sanjeev Arora and " # mic #
       " and David Karger and Philip Klein and Andrzej Woloszyn",
title="A Polynomial-Time Approximation Scheme for Weighted Planar
       Graph {TSP}",
pages="33--41",
crossref={SODA9}
}

@InProceedings{cgp-pr-1997,
  bibtag="No!",
  author =       "Zhi-Zhong Chen and " # mic # " and Christos Papadimitriou",
  title =        "Planarity Revisited",
  pages = "472--3",
  crossref = {WADS5},
  noabstract = "An invited talk by Papadimitriou,
      announcing our results to appear in \cite{cgp-pmg-98}."
}
% AKA CheGriPap97, Chen:1998:PR

@inproceedings{cgp-pmg-98,
bibtag=13,
url="/~mic/papers/13.ps",
author="Zhi-Zhong Chen and " # mic # " and Christos Papadimitriou",
title="Planar Map Graphs (abstract)",
crossref={STOC30},
pages="514--523",
abstract="Papadimitriou also announced these results at WADS'97 (two pages).
Two other papers \cite{cgp-mg-02,cgp-rh4ct-02} give more details.",
}

@InProceedings{ccf-98,
bibtag="14a",
author="V. Sunderam and S. Y. Cheung and S. Chodrow
 and M. Grigni and A. Krantz and I. Rhee and P. Gray
 and S. Olesen and P. Hutto",
  title =        "{CCF}: Collaborative Computing Frameworks",
  booktitle =    "{SC}'98: High Performance Networking and Computing:
                 Proceedings of the 1998 {ACM}/{IEEE} {SC98}
                 Conference",
  nopublisher =    "ACM Press and IEEE Computer Society Press",
  noaddress =      "New York, NY 10036, USA and 1109 Spring Street, Suite
                 300, Silver Spring, MD 20910, USA",
  year =         1998,
  city = "Orlando, Florida",
  month = nov,
  notpagesbutdates = {7--13}
}

@article{ccf-00,
bibtag="14b",
author="V. Sunderam and S. Cheung and S. Chodrow and P. Gray
 and M. Grigni and M. Hirsch and P. Hutto and A. Krantz
 and S. Olesen and I. Rhee and J. Sult and M. Migliardi
 and L. Marzilli and S. Ano and K. Williams and S. Sullivan",
title="{CCF}: A Framework for Collaborative Computing",
journal = "{IEEE} Network Computing",
volume= 4,
number = 1,
pages="16--24",
month="Jan/Feb",
year=2000
}

@inproceedings{g-mintsp-00,
bibtag=15,
url="/~mic/papers/15.ps",
author=mic,
title="Approximate {TSP} in Graphs with Forbidden Minors",
crossref={ICALP27},
pages="869--877",
abstract="This paper extends the previous TSP methods
 \cite{GrigniKoPa95,agkkw-wpgt-98} from planar graphs
 to more general graph families.  It also introduces a new
 graph theoretic quantity (the `gap' number)."
}

@Article{g-slcp-00,
  bibtag = 16,
  url="/~mic/papers/16.ps",
  author = 	 mic,
  title = 	 "A {S}perner Lemma Complete for {PPA}",
  submonth = "submitted " # jan,
  accmonth= "accepted " # aug,
  accyear = 2000,
  year = 2001,
  month = mar,
  volume = 77,
  number = {5--6},
  pages = {255--259},
  journal = ipl,
  oldnote = "Accepted, to appear",
  realabstract = "The class PPA characterizes search problems whose solution
  is guaranteed by the lemma that ``every finite graph with an odd
  degree vertex has another.''  The class PPAD is defined similarly
  for directed graphs.  While PPAD has several natural complete
  problems corresponding to classical existence theorems in topology,
  such as Brouwer's fixed point theorem, no such complete problems
  were known for PPA.  Here we overcome the difficulty by considering
  non-orientable spaces: Sperner's lemma for non-orientable
  3-manifolds is complete for PPA.",
}

@inproceedings{bpg-00,
bibtag=17,
url="/~mic/papers/17.ps",
author="Stefan Boettcher and Allon Percus and " # mic,
title ="Optimizing through Co-Evolutionary Avalanches",
year=2000,
booktitle="$6^{th}$ International Conference on Parallel Problem
	Solving from Nature",
series= lncs,
volume = 1917,
pages="447--456",
oldurl="http://www-syntim.inria.fr/fractales/PPSN2000/program.html"
}

@inproceedings{gsvv-01,
bibtag="18a",
url="/~mic/papers/A1.ps",
author= mic # " and Leonard J. Schulman and
  Monica Vazirani and Umesh Vazirani",
title="Quantum Mechanical Algorithms for the Nonabelian Hidden
  Subgroup Problem",
crossref={STOC33}
}

@Unpublished{gsvv-02,
bibtag="18b",
oldurl="/~mic/papers/19.ps",
author= mic # " and Leonard J. Schulman
        and Monica Vazirani and Umesh Vazirani",
title="Quantum Mechanical Algorithms for the Nonabelian Hidden
  Subgroup Problem",
note="Accepted to appear in {\em Combinatorica}",
month=sep,
year=2002
}

@Unpublished{gsvv-03,
bibtag="18b",
oldurl="/~mic/papers/19.ps",
author= mic # " and Leonard J. Schulman
        and Monica Vazirani and Umesh Vazirani",
title="Quantum Mechanical Algorithms for the Nonabelian Hidden
  Subgroup Problem",
note="Accepted to appear in {\em Combinatorica}",
month=jan,
year=2003
}

@inproceedings{gs-lsatwgfm-02,
bibtag="19",
url="/~mic/papers/??.ps",
author= mic # " and Papa Amar Sissokho",
title="Light Spanners and Approximate {TSP} in Weighted Graphs
       with Forbidden Minors",
crossref={SODA13},
pages="852--857"
}

Jamming Model for the Extremal Optimization Heuristic,
S. Boettcher and M. Grigni,
Journal of Physics A: Math. Gen. 35, 1109-1123 (2002)

@article{bg-eojam-02,
bibtag=20,
url="http://xxx.lanl.gov/abs/cond-mat/0110165",
url2="http://www.iop.org/EJ/S/UNREG/PDB2MsqIrgaiSFkw1gcpbw/abstract/0305-4470/35/5/301",
author="Stefan Boettcher and " # mic,
title="Jamming Model for the Extremal Optimization Heuristic",
pages="1109--1123",
volume=35,
number=5,
journal="J.\ Phys.\ A: Math.\ Gen.",
longjournal="Journals of Physics A: Mathematical and General",
year=2002,
}

@Section{sec:toappear, title="To Appear"}

@unpublished{bg-eojam-01,
bibtag=20,
url="http://xxx.lanl.gov/abs/cond-mat/0110165",
author="Stefan Boettcher and " # mic,
title="Jamming Model for the Extremal Optimization Heuristic",
month=dec,
year=2001,
note="26 pages, accepted to {\em Journal of Physics A}"
}
@section{sec:submitted, title="Submitted"}

@unpublished{cgp-mg-99,
bibtag=21,
url="/~mic/papers/18.ps",
author="Zhi-Zhong Chen and " # mic # " and Christos Papadimitriou",
title="Map Graphs",
month=oct,
year=1999,
pages=46,
note="46 pages, submitted to {\em Journal of the ACM}",
abstract={To keep a reasonable length (compared to \cite{cgp-pmg-00}), the
 algorithm here only covers the ``no-holes'' case.  As recommended
 by initial reviewers, we have split this into two parts: a shorter introductory
 paper resubmitted to JACM, and a longer algorithmic paper for elsewhere.}
}

@article{cgp-mg-02,
bibtag=21,
author="Zhi-Zhong Chen and " # mic # " and Christos Papadimitriou",
title="Map Graphs",
month=mar,
year=2002,
journal=jacm,
volume=49,
number=2,
pages="127--138",
hidnote={This survey paper introduces map graphs, our harder algorithmic
  results are being submitted elsewhere.}
}

@Unpublished{gsv-00,
oldbibtag=22,
url="/~mic/papers/19.ps",
author= mic # " and Leonard J. Schulman and Umesh Vazirani",
title="Quantum Mechanical Algorithms for the Nonabelian Hidden
  Subgroup Problem",
note="11 pages, submitted to {\em Combinatorica} (accepted: July 2002).",
month=sep,
year=2000
}

@Unpublished{nature-00,
bibtag=??,
url="/~mic/papers/20.ps",
author = "Stefan Boettcher and " # mic #
	" and Gabriel Istrate and Allon Percus",
title = "Phase Transitions and Algorithmic Complexity",
note = "A 3-page letter to {\em Nature}, rejected.",
year=2000
}

@section{sec:inprogress,
 title="Work in Progress",
 note="The following manuscripts are not yet submitted to conferences
   or journals, but they represent substantial work."
}

@unpublished{gw-wpgs-00,
bibtag=22,
url="/~mic/papers/21.ps",
author=mic # " and Andrzej Woloszyn",
title="A Weighted Planar Graph Separator",
noyear=2000,
note="14 pages, to submit to
 {\em J.\ Graph Algorithms \&\ Applications}",
abstract="This is a revision of Woloszyn's Master's thesis.  We
  improve some of our earlier planar separator results
  \cite{GrigniKoPa95,agkkw-wpgt-98}.",
jgaaURL="http://www.cs.brown.edu/publications/jgaa/"
}

@Unpublished{ceeggs-awen-95,
bibtag=23,
url="/~mic/papers/22.ps",
  author = "Bernard Chazelle and Herbert Edelsbrunner and David Eppstein and "
	# mic # " and Leonidas Guibas and Micha Sharir and Emo Welzl",
  title = 	 "Algorithms for Weak $\varepsilon$-Nets",
  noyear =	 1995,
  pages = 14,
  note = "Manuscript, 14 pages",
  abstract={This gives more efficient algorithms for \cite{ceggsw-ibwen-95}.},
  shhh={It has some poor writing in the last technical section.},
  realabstract = {In the plane, we can find a weak $\varepsilon$-net for
  convex sets consisting of $O(\varepsilon^{-2})$ points, in time $O(n
  \varepsilon^{-2}\log^2(1/\varepsilon))$.  We can determine the
  smallest $\varepsilon$ for which a given planar set is an
  $\varepsilon$-net in time $O(n^3)$.
  \par
  In ${\bf R}^d$, we~\cite{ceggs-ibwen-93} can find weak
  $\varepsilon$-nets of size $O \left({1\over\varepsilon^d}
  \log^{O(1)}{1\over\varepsilon} \right)$ in time $n\;
  (1/\varepsilon)^{O(1)}$ (both exponents depending on $d$).}
}

@unpublished{cgp-pmg-00,
bibtag=24,
url="/~mic/papers/23.ps",
author="Zhi-Zhong Chen and " # mic # " and Christos Papadimitriou",
title="Planar Map Graphs",
nomonth=aug,
noyear=1997,
note="Manuscript, 56 pages (without figures)",
oldurl="http://www.mathcs.emory.edu/~mic/pmg/",
abstract="This is a very long case analysis, proving the main result
 in \cite{cgp-pmg-98}.  With the (hand-drawn) figures, it would probably
 exceed 70 pages.  We prefer to find some simplification before
 submitting this."
}

@unpublished{cgp-rh4ct-02,
bibtag=24,
url="/~mic/papers/23.ps",
author="Zhi-Zhong Chen and " # mic # " and Christos Papadimitriou",
title="Recognizing Hole-Free 4-Map Graphs in Cubic Time",
nomonth=mar,
noyear=2002,
note="44 pages",
abstract="This proves a result announced in \cite{cgp-pmg-98}."
}

@unpublished{gs-pmc2sspg-02,
bibtag=25,
url="/~mic/papers/25.ps",
author= mic # " and Papa Sissokho",
title="A {PTAS} for the Minimum Cost 2-edge-Connected Spanning Subgraph
	in Planar Graphs",
month=jul,
year=2002,
abstract="I am encouraging Papa to extend this in his thesis.",
note="Rejected from STOC (or was it SODA?), REPLACED by next."
}

@unpublished{gs-pmc2spg-03,
bibtag=25,
badurl="/~mic/papers/25.ps",
author= mic # " and Papa Sissokho",
title="A {PTAS} for Mincost 2-edge-Connected Subgraph in Planar Graphs",
month=apr,
year=2003,
abstract="Submitted to the FOCS 2003 conference."
}

@section{sec:recentadd,
 title="Recent Additions",
 note="These recent manuscripts are not yet worked into the above
  sequence."
}


True Miscellany (not part of my CV):

Student Theses:

@mastersthesis{Haynes98,
author={Keven S. Haynes},
title={The Feasibility of an Approximation Algorithm for
     the Traveling Salesman Problem},
school="Emory University",
year=1998,
month=apr,
note="Dept.\ of Mathematics and Computer Science"
}

@mastersthesis{Woloszyn98,
author={Andrzej P. Woloszyn},
title={Weighted Planar Graph Separator},
school={Emory University},
year=1998,
month=jun,
note="Dept. of Mathematics and Computer Science"
}

@mastersthesis{Pan99,
author={Baiyu Pan},
title={Content-sensitive Implicit {X} Compression},
school={Emory University},
year=1999,
month=feb,
note="Dept. of Mathematics and Computer Science"
}

@mastersthesis{Malowinska99,
author={Malgorata Malowinska},
title={An Implementation of a Multi-round Algorithm for
    Synchronizing Files over a Communication Link},
school={Emory University},
year=1999,
month=may,
note="Dept. of Mathematics and Computer Science"
}

Todo: Benjamin Bradford

@mastersthesis{Xu01,
author={Tao Xu},
title={Data Structures for Extremal Optimization},
school={Emory University},
year=2001,
month=dec,
note="Dept. of Mathematics and Computer Science"
}


@TechReport{gg-cg-91,
  author = 	 "Leonidas Guibas and " # mic,
  title = 	 "Geometric Algorithms: Lecture Notes for 6.891/18.409",
  institution =  "MIT Lab.\ for Computer Science",
  year = 	 1991,
  type =	 "Research Seminar Series",
  number =	 "MIT/LCS/RSS 13",
  month =	 may,
  note =	 "256 pages"
}