Mic's Research Interests

My general research area is the theory of computation. First I present a little history of my interests, and then I list some open problems. I welcome inquiries about the topics listed here.

History of Interests

• As a graduate student fishing around for problems, I wrote a nice paper with David Peleg (long distance) on constructing near-optimal broadcast graphs, based on generalized Fibonacci numbers. A remaining open problem is to reduce the large constant factors, especially in the bounded-degree case.
• I finished my thesis at MIT in 1991, supervised by Michael Sipser. The thesis gave a framework for studying monotone computation, and more specifically it proved a circuit depth lower bound for a problem in the monotone analogue of LOGSPACE. Although a few nice open problems remain in this area (see one below), interest has waned as it became clear that the methods appropriate for monotone circuits would not help with more general models of computation.
• I met Leo Guibas at MIT, and for a couple of years attended his (now defunct) DEC SRC summer workshops on computational geometry. I got a few papers from that, and also a nice bag of algorithmic tricks.
• Since my graduate days I have been interested in the Traveling Salesman Problem (TSP) and similar metrical optimzation problems. At MIT I worked with Dimitris Bertsimas analyzing a simple geometric heuristic.
  At UCSD I worked with Christos Papadimitriou and Elias Koutsoupias on a polynomial time approximation scheme for TSP in planar graphs (at first unweighted). I like to think that some of our ideas inspired Sanjeev Arora's geometric result.
• Also at UCSD I worked with Christos and Dimitris Papadias on topological constraint satisfaction problems. This led Christos and I to the problem of planar map graphs, which is a very thorny topic. After much effort we thought (through many case analyses) that we probably had a result, however nothing happened until Christos enlisted Zhizhong Chen (visiting UCB). Chen had the fortitude and skill to actually work out and write down the voluminous details for the case of four-planar maps.
  Recently (1998 FOCS), Mikkel Thorup found a much more managable approach to the general problem, using PQ-trees to encode constraints on subproblems.
• In my graduate days I studied symmetric group representations, and I soon realized a possible application of that machinery to the graph automorphism problem on quantum computers, basically by doing a fast group FFT, as done by Shor (and earlier Simon) over abelian groups.
  The transform step is indeed efficient on quantum machines, as already claimed by others. I have discussed the problem with various researchers, recently Leonard Schulman (nearby at GaTech), but the apparent result is that for this problem, the FFT does not give you enough information. That is, the "signal" remains exponentially small, at least for the tests we considered.
• I have pursued several interdisciplinary projects at Emory. I was involved in the design stage of the CCF Project (a CSCW framework for natural scientists), and also planning for the Theory side of Emory's PMACS program. I helped a physiologist with a computational cell-probe proposal, although that is currently on a back-burner.
• With the goal of extending the TSP PTAS results to further metrics (and to other optimization problems), I have been thinking about spanner and separator results for various kinds of graphical and geometric metrics. A few partial results motivate two of the open problems below.

Open Problems

Here are some open problems (of varying quality), I continue to put some effort into most of these.

• From my thesis: prove lower bounds on monotone bounded width branching programs. In particular, show they need superpolynomial size to compute majority. We know quadratic.
• Prove superlinear bounds for CAD formulae, for example for the parity or majority of n halfspaces in low dimensions (the plane or 3-space, for example). Some patterns like the checkerboard do have a linear size formula, so part of the problem is finding a difficult arrangement; a random arrangement is probably enough.
• Show that for any ordering of the vertices of an N by N grid, some subset S has an induced tour with length Omega(log N) times optimal. Even w(1) would be interesting. I can show this for orderings defined by a wide class of space-filling curves. I have some old partial results on this, and it feels "nearly proven".
• Given a connected planar graph G with positive edge weights, the shortest path lengths define a metric space on its vertices. Given a subset S of the vertices and positive parameter epsilon, I would like a subgraph H of G such that distances in H are within 1+epsilon of the original distances in G. The question is, can we bound the total weight of H by MST(S) f(epsilon), where f is some arbitrary function? Here MST(S) means the weight of a minimum spanning tree for set S.
• One may ask a very similar question in the plane with obstacles; that is, you have some polygonal obstacles which the shortest paths must avoid. Given S, you want to find some obstacle-avoiding graph H that spans S and has all distances in H at most 1+epsilon of the best possible. Again, can we bound the total edge length of H in terms of MST(S) and some function of epsilon? H may have many Steiner points, up to some polynomial number is ok.
• We have a separator theorem for planar graphs, where the separator is a subgraph (vertices and edges) rather than just a set of vertices, and we have a linear tradeoff between the weight of the separator and its number of connected components. Can this result be generalized to families of graphs with a forbidden minor (say K₅)?
• There is a superficial relationship between the Benes network and a factorization of the symmetric group; is there some way to exploit this to do faster convolution over that group? Via the symmetric group representation, this could say something asymptotic about matrix multiplication (but that's a long shot).

Home. Comments?    Last Modified: 1 Oct 1998