On the Difficulty of Designing Good Classifiers
It is a very interesting and well-studied problem, given two point sets W, B\(\subseteq\)ℜn, to design a linear decision tree that classifies them —that is, no leaf subdivision contains points from both B and W — and is as simple as possible, either in terms of the total number of nodes, or in terms of its depth. We show that, unless ZPP=NP, the depth of a classifier cannot be approximated within a factor smaller than 6/5, and that the total number of nodes cannot be approximated within a factor smaller than n1/5. Our proof relies on a simple connection between this problem and graph coloring, and uses recent nonapproximability results for graph coloring. We also study the problem of designing a classifier with a single inequality that involves as few variables as possible, and point out certain aspects of the difficulty of this problem.

title: Beyond Competitive Analysis
abstract: The competitive analysis of online algorithms has been criticized as being too crude and unrealistic. We propose refinements of competitive analysis in two directions: The first restricts the power of the adversary by allowing only certain input distributions, while the other allows for comparisons between information regimes for online decision-making. We illustrate the first with an application to the paging problem; as a byproduct we characterize completely the work functions of this important special case of the k-server problem. We use the second refinement to explore the power of lookahead in server and task systems.

title: On the approximability of trade-offs and optimal access of Web sources
abstract: We study problems in multiobjective optimization, in which solutions to a combinatorial optimization problem are evaluated with respect to several cost criteria, and we are interested in the trade-off between these objectives (the so-called Pareto curve). We point out that, under very general conditions, there is a polynomially succinct curve that /spl epsiv/-approximates the Pareto curve, for any /spl epsiv/>0. We give a necessary and sufficient condition under which this approximate Pareto curve can be constructed in time polynomial in the size of the instance and 1//spl epsiv/. In the case of multiple linear objectives, we distinguish between two cases: when the underlying feasible region is convex, then we show that approximating the multi-objective problem is equivalent to approximating the single-objective problem. If however the feasible region is discrete, then we point out that the question reduces to an old and recurrent one: how does the complexity of a combinatorial optimization problem change when its feasible region is intersected with a hyperplane with small coefficients; we report some interesting new findings in this domain. Finally, we apply these concepts and techniques to formulate and solve approximately a cost-time-quality trade-off for optimizing access to the World-Wide Web, in a model first studied by Etzioni et al. (1996) (which was actually the original motivation for this work).

title: Topological queries in spatial databases
abstract: Handling spatial information is required by many database applications, and each poses different requirements on query languages. In many cases the precise size of the regions is important, while in other applications we may only be interested in the TOPOLOGICAL relations- hips between regions — intuitively, those that pertain to adjacency and connectivity properties of the regions, and are therefore invariant under homeomorphisms. Such differences in scope and emphasis are crucial, as they affect the data model, the query language, and performance. This talk focuses on queries targeted towards topological information for two- dimensional spatial databases, where regions are specified by polynomial inequalities with integer coeficients. We focus on two main aspects: (i) languages for expressing topological queries, and (ii) the representation of topological information. In regard to (i), we study several languages geared towards topological queries, building upon well-known topologi- cal relationships between pairs of planar regions proposed by Egenhofer. In regard to (ii), we show that the topological information in a spatial database can be precisely summarized by a finite relational database which can be viewed as a topological annotation to the raw spatial data. All topological queries can be answered using this annotation, called to- pological invariant. This yields a potentially more economical evaluation strategy for such queries, since the topological invariant is generally much smaller than the raw data. We examine in detail the problem of transla- ting topological queries against the spatial database into queries against the topological invariant. The languages considered are first-order on the spatial database side, and fixpoint and first-order on the topological in- variant side. In particular, it is shown that fixpoint expresses precisely the PTIME queries on topological invariants. This suggests that topolo- gical invariants are particularly well-behaved with respect to descriptive complexity. (Based on joint work with C.H.Papadimitriou, D. Suciu and L. Segoufin.

title: The complexity of computing a Nash equilibrium
abstract: We resolve the question of the complexity of Nash equilibrium by showing that the problem of computing a Nash equilibrium in a game with 4 or more players is complete for the complexity class PPAD. Our proof uses ideas from the recently-established equivalence between polynomial time solvability of normal form games and graphical games, establishing that these kinds of games can simulate a PPAD-complete class of Brouwer functions.

title: Optimum Grip of a Polygon
abstract: It has been shown by Baker, Fortune and Grosse that any two-dimensional polygonal object can be prehended stably with three fingers, so that its weight (along the third dimension) is balanced. Besides, in this paper we show that form closure of a polygon object can be achieved by four fingers (previous proofs were not complete). We formulate and solve the problem of finding the optimum stable grip or form closure of any given polygon. For stable grip it is most natural to minimize the forces needed to balance through friction the object''s weight along the third dimension. For form closure, we minimize the worst-case forces needed to balance any unit force acting on the center of gravity of the object. The mathematical techniques used in the two instances are an interesting mix of Optimization and Euclidean geometry. Our results lead to algorithms for the efficient computation of the optimum grip in each case.

title: The complexity of recognizing polyhedral scenes
abstract: Given a drawing of straight lines on the plane, we wish to decide whether it is the projection of the visible part of a set of opaque polyhedra. Although there is an extensive literature and reports on empirically succesful algorithm: for this problem, there has been no definite result concerning its complexity. In this paper we show that, rather surprisingly, this problem is NP-complete. This is true even in the relatively simple case of trihedral scenes (no four planes share a point) without shadows or cracks. Despite this negative result, we present a fast algorithm for the important special case of orthohedral scenes (all planes are perpendicular to one of the three axes) with a fixed number of "possible" objects.